У меня очень большой текстовый файл с десятками миллионов слов, по одному слову в строке. Мне нужно найти 10 самых распространенных слов в этом файле. Есть некоторые ограничения: использование только стандартной библиотеки и использование менее 1 КБ памяти.
Гарантируется, что любые 10 слов в этом файле будут достаточно короткими, чтобы уместиться в указанный предел памяти, и будет достаточно памяти для некоторых других переменных, таких как счетчики и т. д.
Единственное решение, с которым я пришел, - это использовать другой текстовый файл в качестве дополнительной памяти и буфера. Но, похоже, это плохой и медленный способ справиться с этой проблемой.
Есть ли лучшие и эффективные решения?
Ваш стек будет потреблять не менее 4 КБ ОЗУ, поэтому, даже если у вас вообще нет кода, вы никогда не сможете выполнить требование «использование памяти менее 1 КБ».
Вы можете сначала отсортировать этот файл (это возможно с ограниченной памятью, но, конечно, потребует дискового ввода-вывода - см. Как сортировать очень большие файлы в качестве стартера).
Затем вы сможете читать отсортированный файл построчно и вычислять частоту каждого слова по одному - сохранять их, после 10 слов - если частота выше, чем все, хранящиеся в вашем массиве - добавить во внутренний массив и удалить наименее встречающееся , таким образом, на этом этапе вы сохраните в памяти только 10 наиболее часто встречающихся слов.
Как упомянул @John Bollinger, если вам нужно напечатать все 10 лучших слов, если, например, все слова из файлов имеют одинаковую частоту, т. Е. Все они «верхние», то этот подход не будет работать, вам нужно рассчитать частоту для каждого слова сохранить в файле, отсортировать его, а затем вывести 10 лучших, включая все слова с той же частотой, что и 10-е.
Потенциальная проблема с этим подходом: многие слова занимают десятое место по частоте. Если требование в этом случае состоит в том, чтобы напечатать все слова, привязанные к этой частоте, то может оказаться невозможным удержать их все в памяти одновременно. Конечно, есть обходные пути.
@JohnBollinger не совсем, проверьте описание проблемы It is guaranteed that any 10 words in that file is short enough to fit into said memory limit
То, что любые 10 слов могут поместиться в памяти одновременно, не решает проблему. Дело не в длинных словах, а скорее в необходимости удерживать в памяти более десяти одновременно.
@JohnBollinger нет, для печати top 10 most common words
вам не нужно хранить все самые распространенные, если, например, все слова из файла имеют одинаковую частоту - вы все равно просто печатаете 10, в моем подходе это будут первые 10 по алфавиту
Ну это вопрос трактовки проблемы. Как я уже писал: «Если в этом случае требуется напечатать все слова, относящиеся к этой частоте», то это проблема для этого предложения. Мне ни в коем случае не ясно, какое поведение требуется, когда «10 самых распространенных слов» не характеризуют уникальный набор ровно из 10 слов.
@JohnBollinger понял, обновите мой ответ, чтобы охватить и этот случай.
Если вы можете создать файл новый, каким бы большим он ни был, вы можете создать простую базу данных дерево на основе диска, содержащую каждое слово и его частоту на данный момент. Это будет стоить вам O(log n) каждый раз, с n от 1 до N слов, плюс окончательное сканирование всего дерева размером N, что в сумме составляет O(N log N).
Если вы не можешь создадите новый файл, вам потребуется выполнить сортировку всего файла на месте, что будет стоить около O(N2). Это ближе к O((N/k)2), я думаю, что при k среднее количество слов, которое вы можете сохранить в памяти для простейшей пузырьковой сортировки, но это O(1/k2)O(N2) = K O(N2), который по-прежнему равен O(N2). В этот момент вы можете повторно отсканировать файл в последний раз, и после каждого запуска каждого слова вы будете знать, может ли это слово войти в вашу первую десятку и в какой позиции. Таким образом, вам нужно уместить в памяти всего двенадцать слов (первая десятка, текущее слово и слово, только что прочитанное из файла). 1к должно хватить.
Итак, вспомогательный файл на самом деле является опцией самый быстрый.
Если вы готовы принять чрезвычайно длительное время выполнения, существует очень тривиальная и простая реализация O (n ^ 2).