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

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

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

S>>Идея такова: ввести хэш-функцию во множество меньшего размера. Для значений хэш-функции пересчёт очевиден (отсортировать, пробежаться). Далее оценить вероятность коллизии и с учетом этого давать оценку числа уникальных значений для исходного множества.

C>не работает, коллилии будут в любом случае, т.к. потенциальное количество различных значений крайне велико в вполне равно длине массива, а памяти всего 2 Гб

Хочу заметить, что битовый массив на 4 миллиарда элементов занимает всего пол-гига. Так что даже пара хэшей поместится.

Но не зная исходной задачи и допустимых погрешностей, конечно, дискутировать трудно.

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

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

Но если действительно допустимо сделать несколько проходов по исходным данным, то могу предложить следующую идею:
1. Искомое кол-во уникальных значений = 0, нижняя граница = 0, верхняя граница = 2^64-1.
2. Заводим отсортированный массив* ( размером с доступную оперативную память) для хранения найденных уникальных 64-битных значений.
3. Проходим по исходным данным добавляя в массив уникальные значения, лежащие между нижней и верхней границами.
4. Если при добавлении очередного значения в массиве нет свободных мест, то:
4.1 удаляем из массива максимальный элемент
4.2 добавляем очередной элемент
4.3 верхняя граница = текущий максимальный элемент в массиве
5. После прохода по исходным данным:
5.1 добавляем кол-во элементов в массиве к общему кол-ву найденных уникальных элементов
5.2 очищаем массив
5.3 устанавливаем нижняя граница = верхняя граница, верхняя граница = 2^64-1.
6. Если из массива удалялись элементы (т.е. требуются еще проходы по исходным данным), то переходим к п. 2.

*Отсортированный массив используется для простоты описания и расчета кол-ва проходов.

Оценка количества необходимых проходов: за один проход при использовании 2Гб памяти (и массива в качестве структуры данных) можно найти до 2^28 уникальных 64-битных значений, соответственно в худшем случае (все 4 миллиарда исходных чисел различны) потребуется 4*10^9 / 2^28 ~= 15 проходов.