Алгоритм расчесывания журнала
Мы получаем эти файлы данных размером 50 ГБ, состоящие из 16 байтовых кодов, и я хочу найти какой-либо код, который имеет значение 1/2% времени или больше. Есть ли способ сделать это за один проход по данным?
Изменить: существует множество кодов - возможно, что каждый код отличается.
ЭПИЛОГ. Я выбрал Дариуса Бэкона как лучший ответ, потому что я считаю, что лучший алгоритм - это модификация элемента большинства, с которым он связан. Алгоритм большинства должен быть модифицируемым, чтобы использовать только крошечный объем памяти - например, 201 код, чтобы получить 1/2%, я думаю. В основном вы просто проводите поток, подсчитывая до 201 различных кодов. Как только вы найдете 201 отдельный код, вы бросаете один из каждого кода (вычитаете 1 из счетчиков, забывая все, что становится 0). В конце вы сбросили максимум N/201 раз, поэтому любой код, который появляется больше времени, чем все еще должен быть.
Но это двухпроходный алгоритм, а не один. Вам понадобится второй проход, чтобы подсчитать количество кандидатов. На самом деле легко убедиться, что любое решение этой проблемы должно использовать как минимум 2 прохода (первая партия элементов, которые вы загружаете, может быть различной, и один из этих кодов может составлять ровно 1/2%)
Спасибо за помощь!
Ответы
Ответ 1
Metwally et al., Эффективное вычисление частотных и верхних элементов в потоках данных (2005). Были некоторые другие важные документы, которые я читал для своей работы в Yahoo, которую я не могу найти сейчас; но это похоже на хорошее начало.
Изменить: А, см. статью статья Брайана Хейса. Он набросает точный алгоритм из-за Demaine и др. Со ссылками. Он делает это за один проход с очень маленькой памятью, получая набор предметов, включая те, которые вы ищете, если они существуют. Получение точных отсчетов занимает второй (второй) проход.
Ответ 2
это будет зависеть от распределения кодов. если имеется достаточно небольшое количество отдельных кодов, вы можете создать http://en.wikipedia.org/wiki/Frequency_distribution в ядре с картой. иначе вам, вероятно, придется построить http://en.wikipedia.org/wiki/Histogram, а затем сделать несколько проходов над данными, изучающими частоты кодов в каждом ковше.
Ответ 3
Сортируйте куски файла в памяти, как если бы вы выполняли внешний вид. Однако, вместо того, чтобы записывать все отсортированные коды в каждом фрагменте, вы можете просто написать каждый отдельный код и количество вхождений в этом фрагменте. Наконец, объедините эти краткие записи, чтобы найти количество вхождений каждого кода.
Этот процесс масштабируется до данных любого размера, и он только пропускает входные данные. Может потребоваться несколько проходов слияния, в зависимости от того, сколько сводных файлов вы хотите открыть сразу.
Сортировка файла позволяет подсчитывать количество вхождений каждого кода с использованием фиксированного объема памяти независимо от размера ввода.
Вы также знаете общее количество кодов (либо путем деления размера ввода на фиксированный размер кода, либо путем подсчета количества кодов переменной длины во время сортировки в более общей проблеме).
Итак, вы знаете пропорцию ввода, связанного с каждым кодом.
Это в основном конвейер sort * | uniq -c
Если каждый код появляется только один раз, это не проблема; вам просто нужно уметь их подсчитывать.
Ответ 4
Это зависит от того, сколько разных кодов существует и сколько памяти у вас есть.
Моя первая идея заключалась бы в создании хеш-таблицы счетчиков с кодами в виде ключей. Прокрутите весь файл, увеличив счетчик соответствующего кода и подсчитав общее число. Наконец, отфильтруйте все клавиши со счетчиками, которые превышают (* счетчик 1/200).
Ответ 5
Если файлы состоят исключительно из 16-байтовых кодов, и вы знаете, насколько велики каждый файл, вы можете рассчитать количество кодов в каждом файле. Затем вы можете найти порог 0,5% и следовать любым другим предложениям, чтобы подсчитать вхождения каждого кода, записывая каждый, частота которого пересекает порог.
Ответ 6
Содержат ли содержимое каждого файла единый набор данных или существует ли какое-либо ограничение между файлами? В последнем случае, предполагая довольно постоянное распределение кодов с течением времени, вы можете сделать вашу жизнь проще, разделив каждый файл на более мелкие и более управляемые фрагменты. В качестве бонуса вы будете получать предварительные результаты быстрее и позже можете выполнить конвейер в следующий процесс.
