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

Question

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

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

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

Answer 1

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

stringList.sort(key=len) 

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

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

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

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

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

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

---

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