Мы получаем эти файлы данных размером ~ 50 ГБ, состоящие из 16-байтовых кодов, и я хочу найти любой код, который встречается в 1/2% или более раз. Есть ли способ сделать это за один проход данных?
Изменить: Есть тонны кодов - возможно, что каждый код отличается.
ЭПИЛОГ: Я выбрал Дариуса Бэкона как лучший ответ, потому что я думаю, что лучший алгоритм - это модификация элемента большинства, с которым он связан. Алгоритм большинства должен быть изменяемым, чтобы использовать только небольшой объем памяти - например, 201 код, чтобы получить 1/2%, я думаю. В основном вы просто идете по потоку, считая до 201 различных кодов. Как только вы найдете 201 отдельный код, вы сбрасываете по одному на каждый код (вычтите 1 из счетчиков, забыв обо всем, что станет 0). В конце концов, вы отбрасываете самое большее N / 201 раз, поэтому любой код, встречающийся больше раз, должен все еще быть.
Но это алгоритм двух проходов, а не один. Вам нужен второй проход, чтобы подсчитать количество кандидатов. На самом деле легко понять, что любое решение этой проблемы должно использовать как минимум 2 прохода (первая партия загружаемых вами элементов может отличаться, и один из этих кодов может в итоге составлять ровно 1/2%)
Спасибо за помощь!