Я слышал, что этот вопрос задавался много раз, и я надеялся получить какое-то мнение о том, какие могут быть хорошие ответы: у вас большой файл размером более 10 ГБ, и вы хотите выяснить, какой элемент встречается чаще всего, какой способ лучше сделать это?
Итерация и отслеживание на карте, вероятно, не очень хорошая идея, поскольку вы используете много памяти, и отслеживание поступления записей не является наилучшим вариантом, поскольку, когда задается этот вопрос, файл обычно уже существует.
Другие мысли, которые я включил в разделение файла, который будет повторяться и обрабатываться несколькими потоками, а затем объединять эти результаты, но проблема с памятью для карт все еще остается.
algorithms
arrays
похлопывание
источник
источник
Ответы:
Когда у вас есть действительно большой файл и много элементов в нем, но самый распространенный элемент очень распространен - встречается доли времени - вы можете найти его в линейном времени с пробелом слов ( Константа в нотации очень мала, в основном 2, если вы не учитываете память для вспомогательных вещей, таких как хеширование). Более того, это прекрасно работает с внешним хранилищем, поскольку файл обрабатывается последовательно по одному элементу за раз, и алгоритм никогда не «оглядывается назад». Один из способов сделать это - использовать классический алгоритм Мисры и Гриса, см. Эти лекционные заметки . Проблема теперь известна как проблема тяжелых нападающих (частые элементы - тяжелые нападающие).O ( k ) O ( )>1/k O(k) O()
Предположение, что наиболее частый элемент появляется доли времени для небольшого числа, может показаться сильным, но это необходимо! Т.е., если у вас будет последовательный доступ к вашему файлу (и в случае, если файл огромен, произвольный доступ будет слишком дорогим), любой алгоритм, который всегда находит наиболее частый элемент за постоянное число проходов, будет использовать пространство, линейное по количеству элементов. , Поэтому, если вы не предполагаете что-то о вводе, вы не можете разбить хеш-таблицу. Предположение, что наиболее частый элемент является очень частым, возможно, является наиболее естественным способом обойти отрицательные результаты.к>1/k k
Вот набросок для , то есть когда есть один элемент, который встречается более половины времени. Этот особый случай известен как алгоритм большинства голосов и связан с Бойером и Муром. Мы будем хранить один элемент и один счет. Инициализируйте счетчик до 1 и сохраните первый элемент файла. Затем обработайте файл в последовательности:k=2
Немного подумав об этой процедуре, вы убедите вас в том, что если существует элемент «большинства», то есть тот, который встречается более половины времени, то этот элемент будет сохраненным элементом после обработки всего файла.
Общих , вы держите элементы и рассчитывает, и инициализировать элементы к первому различных элементам файла и рассчитывает на количество раз , каждый из этих элементов появляется , прежде чем вы видите -й отличный элемент. Затем вы запускаете, по сути, ту же процедуру: счетчик элемента увеличивается каждый раз, когда он встречается, все счетчики элементов уменьшаются, если встречается элемент, который не сохранен, и когда некоторое количество равно нулю, этот элемент исключается в пользу текущий элемент файла. Это алгоритм Мисры-Гриса.k - 1 k - 1 k kk k−1 k−1 k k
Конечно, вы можете использовать хеш-таблицу для индексации хранимых элементов. При завершении этот алгоритм гарантированно возвращает любой элемент, который встречается более чем в доле времени. По сути, это лучшее, что вы можете сделать с алгоритмом, который делает постоянное количество проходов по файлу и сохраняет только слов.1 / k O ( k )k−1 1/k O(k)
И последнее: после того, как вы нашли кандидатов в «сильные нападающие» (то есть частые элементы), вы можете сделать еще один проход по файлу для подсчета частоты каждого элемента. Таким образом, вы можете ранжировать элементы между собой и проверить, все ли они встречаются более чем в доле времени (если таких элементов меньше, чем , некоторые из элементов, возвращаемых алгоритмом, могут быть ложноположительными ).1k k - 11/k k−1
источник
Очевидный ответ, конечно, состоит в том, чтобы сохранить хэш-карту и сохранить счетчик появления элементов при перемещении по файлу, как уже предлагал Нейц. Это (с точки зрения сложности времени) оптимальное решение.
Однако, если ваши требования к пространству жесткие, вы можете выполнить внешнюю сортировку файла, а затем найти самый длинный последовательный прогон равных элементов. Следующее должно иметь постоянный объем памяти и может быть сделано вΘ(nlogn).
источник
Если наиболее распространенный элемент является более распространенным, чем следующий общий элемент с существенным запасом, и число различных элементов невелико по сравнению с размером файла, вы можете случайным образом выбрать пару элементов и вернуть наиболее распространенный элемент в выборке.
источник