Как искать наиболее распространенные слова в очень большом файле (более 1 Гб), используя 1 Кб или меньше памяти?

У меня очень большой текстовый файл с десятками миллионов слов, по одному слову в строке. Мне нужно найти 10 самых распространенных слов в этом файле. Есть некоторые ограничения: использование только стандартной библиотеки и использование менее 1 КБ памяти.

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

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

Есть ли лучшие и эффективные решения?

Если вы готовы принять чрезвычайно длительное время выполнения, существует очень тривиальная и простая реализация O (n ^ 2).

abelenky 14.05.2022 16:20

Ваш стек будет потреблять не менее 4 КБ ОЗУ, поэтому, даже если у вас вообще нет кода, вы никогда не сможете выполнить требование «использование памяти менее 1 КБ».

Brendan 16.05.2022 10:03
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
2
62
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

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

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

Как упомянул @John Bollinger, если вам нужно напечатать все 10 лучших слов, если, например, все слова из файлов имеют одинаковую частоту, т. Е. Все они «верхние», то этот подход не будет работать, вам нужно рассчитать частоту для каждого слова сохранить в файле, отсортировать его, а затем вывести 10 лучших, включая все слова с той же частотой, что и 10-е.

Потенциальная проблема с этим подходом: многие слова занимают десятое место по частоте. Если требование в этом случае состоит в том, чтобы напечатать все слова, привязанные к этой частоте, то может оказаться невозможным удержать их все в памяти одновременно. Конечно, есть обходные пути.

John Bollinger 14.05.2022 16:44

@JohnBollinger не совсем, проверьте описание проблемы It is guaranteed that any 10 words in that file is short enough to fit into said memory limit

Iłya Bursov 14.05.2022 16:46

То, что любые 10 слов могут поместиться в памяти одновременно, не решает проблему. Дело не в длинных словах, а скорее в необходимости удерживать в памяти более десяти одновременно.

John Bollinger 14.05.2022 16:49

@JohnBollinger нет, для печати top 10 most common words вам не нужно хранить все самые распространенные, если, например, все слова из файла имеют одинаковую частоту - вы все равно просто печатаете 10, в моем подходе это будут первые 10 по алфавиту

Iłya Bursov 14.05.2022 16:55

Ну это вопрос трактовки проблемы. Как я уже писал: «Если в этом случае требуется напечатать все слова, относящиеся к этой частоте», то это проблема для этого предложения. Мне ни в коем случае не ясно, какое поведение требуется, когда «10 самых распространенных слов» не характеризуют уникальный набор ровно из 10 слов.

John Bollinger 14.05.2022 17:06

@JohnBollinger понял, обновите мой ответ, чтобы охватить и этот случай.

Iłya Bursov 14.05.2022 17:10
Ответ принят как подходящий

Если вы можете создать файл новый, каким бы большим он ни был, вы можете создать простую базу данных дерево на основе диска, содержащую каждое слово и его частоту на данный момент. Это будет стоить вам 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к должно хватить.

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

Другие вопросы по теме