Возникла недавно задача: есть последовательность 64-битных чисел s1, s2, ... sN, где N — достаточно большое (для определенности пусть будет 4 миллиарда)
требуется, обработав эту последовательность, определить, сколько различных элементов нахождится в этой последовательности (т.е., посчитать количество элементов без повторений). Сама послеодвательность находится во внешней памяти, Ответ можно дать приблизительно, с указанным интервалом ошибки.
Числа s1.. sN могут быть абсолютно любые 64-битные, т.е. нельзя просто добавлять числа в какую-то структуру данных типа хеша и потом почитать количество ключей — памяти не хватит (ее есть 2Гб).
кто-нибдуь может подсказать, в какую сторону копать?
