Коллекции: как найти 10 самых длинных строк в списке из миллиарда строк?

Недавно мне задали вопрос в интервью. Как найти 10 самых длинных строк в списке из миллиарда строк? Мой ответ заключался в том, что нам нужно написать компаратор, который сравнивает длины двух строк, а затем использовать конструктор TreeSet (компаратор). Как только вы начнете добавлять строки в Treeset, они будут сортироваться в соответствии с порядком сортировки, определенным компаратором. Затем просто выберите 10 лучших элементов набора деревьев.

Интервьюера это не устроило. Аргумент состоял в том, что для хранения миллиардов строк мне придется использовать суперкомпьютер.

Есть ли какая-либо другая структура данных, чем может обрабатывать такие данные?


string collections data-structures comparator treeset
person Andy    schedule 09.09.2016    source источник
comment
Прочитайте об этой структуре данных trie   -  person Prateek Gupta    schedule 09.09.2016
comment
Интервьюер хотел услышать об очереди приоритетов (мин-куча, хранящая десять самых длинных строк).   -  person MBo    schedule 09.09.2016

Ответы (4)


arrow_upward
2
arrow_downward

Учитывая то, что вы сказали о том, что интервьюер сказал, что вам понадобится суперкомпьютер, я собираюсь предположить, что строки будут приходить потоком по одной строке за раз.

Учитывая огромный размер из-за отсутствия знаний о том, насколько велики отдельные строки (они могут быть целыми книгами), я бы читал их по одной из потока. Затем я бы сравнил текущую строку с упорядоченным списком первых десяти самых длинных строк, найденных до нее, и соответствующим образом поместил бы ее в упорядоченный список. Затем я удалял наименьшую длину из списка и переходил к чтению следующей строки. Это означало бы, что одновременно сохранялось только 11 строк: 10 текущих и обрабатываемая.

person D. Law.    schedule 09.09.2016

arrow_upward
0
arrow_downward

Большинство языков имеют встроенную сортировку, которая работает довольно быстро.

stringList.sort(key=len)

в питоне будет работать. Затем просто возьмите первые 10 элементов.

Также ваш интервьюер звучит несовременно. Один миллиард строк в наши дни довольно мал

person Joey Wood    schedule 09.09.2016

arrow_upward
0
arrow_downward

Я помню, как изучал аналогичную структуру данных для таких сценариев, называемых Trie.

height из tree всегда будет давать самую длинную строку.

Для индексации всех суффиксов в тексте можно использовать особый тип дерева, называемый деревом суффиксов. для быстрого полнотекстового поиска.

person Prateek Gupta    schedule 09.09.2016

arrow_upward
0
arrow_downward

Дело в том, что вам не нужно хранить все строки.

Давайте подумаем об упрощенной версии: найдите самую длинную 2 строки (при условии отсутствия галстука)

Вы всегда можете выполнить онлайн-алгоритм, например, используя 2 переменные s1 и s2, где s1 — самая длинная строка, с которой вы столкнулись до сих пор, s2 — вторая по длине.

Затем вы используете O(N) для чтения строк одну за другой, заменяя s1 или s2, когда это возможно. Это использование O(2N) = O(N)

Для топ-10 строк это так же глупо, как и для топ-2. Вы все еще можете сделать это в O(10N) = O(N) и сохранить только 10 строк.

Существует более быстрый способ, описанный ниже, но для заданной константы, такой как 2 или 10, он вам может не понадобиться.

Для строк top-K в целом вы можете использовать структуру, подобную set в C++ (с более длинным, имеющим более высокий приоритет), для хранения строк top-K, когда появляется новая строка, вы просто вставляете ее и удаляете последнюю, обе используют O(lg K). Таким образом, вы можете сделать это в O(N lg K) с O(K) пространством.

person shole    schedule 09.09.2016