Interview question

[Likenew]

<Python, what would you do if you need to get some info from 50000 websites?>
Просто интересно что надо читать

[mskmel]

Просто интересно что надо читать

https://docs.python.org/3/library/asyncio-task.html" onclick="window.open(this.href);return false;

[Likenew]

спасибо

[ystar]

Есть 3*10^10 китайцев и огромный csv с их телефонами. Сделать сервис который позволяет проверить есть ли такой номер

[Larsonsager]

фильтр Блума. Возможно, даже два фильтра: номер в списке и номер не в списке, чтобы избежать возни с ложноположительными срабатываниями.

[ALV00]

фильтр Блума. Возможно, даже два фильтра: номер в списке и номер не в списке, чтобы избежать возни с ложноположительными срабатываниями.

Так сейчас не модно. Сайчас так делают: ставят хадуп кластер и прямым перебором.

[M. Ridcully]

Есть 3*10^10 китайцев и огромный csv с их телефонами. Сделать сервис который позволяет проверить есть ли такой номер

Телефоны 11-значные, сталбыть?

Не понятно, что с хардварью. Если можно всё записать в память, то хэш таблицы, сколько-то разрядов указывают на сервер, оставшиеся используются как ключи в хэше.

Если столько серверов / памяти нет, то B tree на диске и кеш в памяти.

Кстати, а откуда столько китайцев взялось?

[M. Ridcully]

фильтр Блума.

Ну он же только как дополнение к хешу / или чему там ещё может быть, верно? Если память дефицит, то вряд ли поможет.

[mskmel]

Есть 3*10^10 китайцев и огромный csv с их телефонами. Сделать сервис который позволяет проверить есть ли такой номер

Поставить кластер мобильников, и по каждому запрошенному номеру звонить. Если пошёл гудок, то номер есть

[Larsonsager]

данных там на 130 гигабайт, если писать свовами по 37 бит, но не паковать. В память, получается, ничего записать нельзя.

Номер телефона сам себе хэш.

В принципе, вероятно, можно запихнуть данные в оперативку с упаковкой каким-нибудь энтропийным сжатием. Номера отсортировать и хранить не в виде самих чисел, а в виде дельт между ними, причем эти дельты кодировать, скажем, Голомбом-Райсом. Там в среднем дельты будут всего лишь 3, видимо (если телефоны 11-значные), то есть в среднем надо будет хранить всего несколько бит на дельту. Может, два-три бита. 3 бита на 3*10^10 китайцев - это всего 10 гигабайт. Но тут придется искать нужное число по цепочке дельт, да еще и раскодировать их на лету.

Фильтр Блума, по-моему, давал те же полбайта на одного китайца при приемлемой вероятности ошибки, но работать с ним быстрее.

[АццкоМото]

Может, я тупой, но я не понимаю, как фильтр блума помогает. Ну, в плане, как избежать false positive.

[M. Ridcully]

Может, я тупой, но я не понимаю, как фильтр блума помогает. Ну, в плане, как избежать false positive.

Вот и я так подумал.
_Теоретически_, 2 фильтра на присутствующие / отсутствующие номера могут работать, но я бы не стал такой огород городить.

[M. Ridcully]

В память, получается, ничего записать нельзя.

Почему? Мы же не знаем, сколько серверов и какая память.
Поэтому и предложил - если памяти хватает, то хэш таблицы на кластере серверов, если нет - то B-trees на диске с кэшированием.

[АццкоМото]

Может, я тупой, но я не понимаю, как фильтр блума помогает. Ну, в плане, как избежать false positive.

Вот и я так подумал.
_Теоретически_, 2 фильтра на присутствующие / отсутствующие номера могут работать, но я бы не стал такой огород городить.

ну вот эта идея как раз мне непонятна

и кстати этот вопрос я получал на интервью. обосрался. правильный ответ так и не нагуглил. наверняка он простой, как два рубля, но какой???

[АццкоМото]

В память, получается, ничего записать нельзя.

Почему? Мы же не знаем, сколько серверов и какая память.
Поэтому и предложил - если памяти хватает, то хэш таблицы на кластере серверов, если нет - то B-trees на диске с кэшированием.

в формулировке, что мне давали задачу, если я правильно помню, память должна быть константой. ну, условной. т.е. не зависить от населения Китая. и один процессор, никаких кластеров - brute force не канает

ЗЫ. самое очевидное - типа отсортировать спейсок номеров и дальше искать бинарным поиском. такой ответ приходит на третьей секунде размышления. но это неправильный ответ. строить хэш таблицы - ничем не лучше сортировки, плюс появляется зависимость по памяти.

все-таки я наверное тупой

[_reality]

Чтонить в стиле дерева блум фильтров наверное должно сработать. В случае срабатывания блум фильтра спускаемся по дереву и смотрим в следующие фильтры. Примерно по такой схеме индекс в Lucene строится (https://youtu.be/5444z-L2V2A?t=8m15s" onclick="window.open(this.href);return false;). Все это можно сделать за один проход по всем данным с константной памятью.

Code: Select all

1.

    b01 
/       \ 
[1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 0] 



2.
      
    b01    b02
/       \ /      \
[1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 0] 
   


3.    
        b11
     /       \
    b01    b02     b03
/       \ /      \ /       \
[1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 0]

[ALV00]

Аццки то прав. Идея с двумя фильтрами не будет работать. Допустим, оба фильтра дали позитивный результат. Кто-то из них соврал, кто-то сказал правду. Но как это узнать?

[M. Ridcully]

Аццки то прав. Идея с двумя фильтрами не будет работать. Допустим, оба фильтра дали позитивный результат. Кто-то из них соврал, кто-то сказал правду. Но как это узнать?

Да, точно.

[АццкоМото]

Хотелось бы заслушать ystar. Уже все помучались ничего не вышло. Правильный ответ в студию?

[John Smith]

а как задача то в точности звучит? а то что-то непонятно что оптимизируем

[Larsonsager]

действительно, экономии по объему не будет: при равном количестве подходящих и неподходящих значений два блумфильтра дают ту же ошибку, что один двойного размера.

Но. Пусть у нас один большой фильтр с ошибкой p^3. Тогда при несрабатывании мы точно знаем, что такого телефона нет, а при срабатывании (то есть в трети случаев) нам придется всё-таки пройтись по большому массиву.

А если у нас два маленьких фильтра, каждый с ошибкой p, с вероятностью p^2 мы получим неоднозначность: оба фильтра дадут положительный результат. Объем у них вместе такой же, как у одного большого фильтра, по ошибке мы даже потеряли, так? Но зато в трети случаев положительных срабатываний проверять придется не всю эту треть, а только ту малую долю p, когда оба фильтра дали положительный результат.

Итого, грубо говоря, мы имеем один фильтр в памяти на 10 гигабайт с подходящими номерами телефонов, один фильтр на 20 гигабайт в памяти с неподходящими номерами телефонов (этот фильтр можно разбить на десять и положить на диск) и один большой файл на диске гигов на 30 с упакованными телефонами, доступ к нему будет медленным.

В случае подходящего телефона, мы обратимся к первому фильтру, гарантированно получим положительный ответ, а дальше обратимся ко второму фильтру, и:
а) с вероятностью (1 - p) получим отрицательный ответ и будем точно знать, что номер подходящий;
б) с вероятностью p получим положительный ответ, и придется лезть в большой файл тупо искать телефон в списке.

Итого потратим на подходящий телефон t1 + (1 - p) * t2 + p * t3 времени в среднем, где t1 - время доступа к первому фильтру, t2 - ко второму, t3 - время поиска по полному списку.

В случае неподходящего телефона мы его:
а) с вероятностью (1-p) сразу отсеем, обратившись к первому фильтру
б) с вероятностью p первый фильтр даст ложноположительный результат, второй фильтр гарантированно даст положительный результат, и нам придется опять лезть в полный список.

Итого на неподходящий телефон уйдет в среднем t1 + p * (t2 + t3).

Для малых p имеем среднее время обработки примерно t1 + t2 + p * t3 для подходящих телефонов и t1 + p * (t2 + t3) для неподходящих, что, с учетом t3 >> t2 > t1, даёт в обоих случаях примерно p * t3.


А вот для единственного фильтра Блума пусть даже с ошибкой p^3 нам бы для неподоходящих телефонов пришлось тратить t1 + p^3 * t3, а для подходящих - t1 + t3.

[АццкоМото]

Чота мутно как-то. Непонятно, что за список неподходящих номеров. Типа для упрощения. Если подходящие - от 001 до 101 сплошняком, то неподходящие — от 102 до 999 что ли? Ничотаг оверхед. Хуже того, а как этот список создать? Ну и самое поганое — worst case scenario. Если хоть с какой-то вероятностью придется перебирать в лоб.... Фигня какая-то

[Larsonsager]

Чота мутно как-то. Непонятно, что за список неподходящих номеров. Типа для упрощения. Если подходящие - от 001 до 101 сплошняком, то неподходящие — от 102 до 999 что ли? Ничотаг оверхед. Хуже того, а как этот список создать? Ну и самое поганое — worst case scenario. Если хоть с какой-то вероятностью придется перебирать в лоб.... Фигня какая-то

заявлено, что 3*10^10 номеров подходят. Есть разумные основания ожидать, что номера там 11-значные (на самом деле, Википедия утверждает, что в целом так оно и есть, но не всегда). Это значит, что неподходящих номеров всего вдвое больше, чем подходящих.

[valchkou]

а решение типа загрузить файл в базу один раз, а затем работать с базой, а не файлом не подходит?
в реальной жизни, именно так бы и было сделанно в 99.9% случаев.

[АццкоМото]

Чота мутно как-то. Непонятно, что за список неподходящих номеров. Типа для упрощения. Если подходящие - от 001 до 101 сплошняком, то неподходящие — от 102 до 999 что ли? Ничотаг оверхед. Хуже того, а как этот список создать? Ну и самое поганое — worst case scenario. Если хоть с какой-то вероятностью придется перебирать в лоб.... Фигня какая-то

заявлено, что 3*10^10 номеров подходят. Есть разумные основания ожидать, что номера там 11-значные (на самом деле, Википедия утверждает, что в целом так оно и есть, но не всегда). Это значит, что неподходящих номеров всего вдвое больше, чем подходящих.

Пусть так. Как вы найдете список неподходящих номеров? Не замечаете, что эта задача опасно близка к исходной?