Здравствуйте, ch00k, Вы писали:

C>Здравствуйте,

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

C>Числа s1.. sN могут быть абсолютно любые 64-битные, т.е. нельзя просто добавлять числа в какую-то структуру данных типа хеша и потом почитать количество ключей — памяти не хватит (ее есть 2Гб).

Путь у нас есть 4 миллиарда 64-битных чисел и 2 ГБ оперативной памяти, тогда можно подсчитать количество различных чисел, если считывать данные много раз.
В 2 ГБ памяти помещается около 250 миллионов 8 байтных чисел (64-битных).
1. Находим минимальное и максимальное число в последовательности.
2. Ищем число х между минимальным и максимальным, такое, что количество чисел, которые больше, либо равно минимального, но меньше x составляет не более 250 миллионов (Число x можно искать дихотомией).
3. Еще раз проходим массив и все числа, которые больше минимального, но меньше x заносим в массив в оперативной памяти.
4. Массив в оперативной памяти сортируем и подсчитываем количество различных чисел.
5. Теперь в качестве минимального числа принимаем число x и повторяем с пункта 2, до тех пор, пока число x не достигнет
максимального числа.

Нужно продумать еще вариант, когда количество каких-либо одинаковых чисел достаточно велико или даже превышает 250 миллионов.