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

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

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

кто-нибдуь может подсказать, в какую сторону копать?

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

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

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

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

C>кто-нибдуь может подсказать, в какую сторону копать?

Можно попробывать следующее (точной оценки временной сложности и расхода памяти не делал):
Нужна длинная арифметика то есть работа с большими числами. Каждое новое число последовательности являеться порядковым номером простого числа, то есть мы производим преобразование числа из последовательности в простое число. Далее в нужно производить умножение каждого последующего простого числа на то произведение всех предыдущих, предварительно проверив не встретилось ли такое число на уже раньше. Проверка осуществляеться делением — если на цело то это число у нас уже есть и его добавлять, то есть умножать на уже накопленное произведение не будем. Не трудно организовать счетчик различных чисел так как есть процедура проверки. Загвоздка может быть в формировании простых чисел, хранении конечного произведения (так как чисел всего 2^32 может и хватить — все ж таки не 2^64 как в случае с другой структоруой данных)

Вобщем можно попробывать, рекомендую просмотреть теорию чисел, арифметку по модулю (может удасться теряя точность повысить плотность хранения) и другие похожие темы.

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

C>кто-нибдуь может подсказать, в какую сторону копать?
В сторону внеших алгоритмов сортировки. Кнут, 3 том.

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

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

C>>кто-нибдуь может подсказать, в какую сторону копать?
Mab>В сторону внеших алгоритмов сортировки. Кнут, 3 том.

не получится обращаться к внешней памяти интенсивно — последовательность идет в иде потока, считывать можно ограниченное число раз и подряд

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

DG>Можно попробывать следующее (точной оценки временной сложности и расхода памяти не делал):
DG>Нужна длинная арифметика то есть работа с большими числами. Каждое новое число последовательности являеться порядковым номером простого числа, то есть мы производим преобразование числа из последовательности в простое число. Далее в нужно производить умножение каждого последующего простого числа на то произведение всех предыдущих, предварительно проверив не встретилось ли такое число на уже раньше. Проверка осуществляеться делением — если на цело то это число у нас уже есть и его добавлять, то есть умножать на уже накопленное произведение не будем. Не трудно организовать счетчик различных чисел так как есть процедура проверки. Загвоздка может быть в формировании простых чисел, хранении конечного произведения (так как чисел всего 2^32 может и хватить — все ж таки не 2^64 как в случае с другой структоруой данных)

DG>Вобщем можно попробывать, рекомендую просмотреть теорию чисел, арифметку по модулю (может удасться теряя точность повысить плотность хранения) и другие похожие темы.

Насчет ограничений по памяти — это будет произведение из 4 миллиардов простых чисел (в худшем случае). Занимать оно будет по самой грубой оценке (log P) * (4 миллиарда), бит где P — максимальное число. Памяти явно не хватит. Но идея интересная, попробую посмотреть.

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

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

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

Здравствуйте, Андрей Тарасевич, Вы писали:

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

точно распределение чисел неизвестно и оно вполне может быть равномерным. То, что точное решение при таких ограичениях получить нельзя, понятно. Может, есть какие-то вероятностные алгоритмы, в которых как-то можно привязать максимальную ошибку к фукнции распределения чисел и количеству используемой памяти?

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

C>точно распределение чисел неизвестно и оно вполне может быть равномерным. То, что точное решение при таких ограичениях получить нельзя, понятно. Может, есть какие-то вероятностные алгоритмы, в которых как-то можно привязать максимальную ошибку к фукнции распределения чисел и количеству используемой памяти?
А может опишешь задачу полностью? Возможно можно срезать углы в других местах.

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

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

Ну раз во внешней памяти, то почему бы не построить базу данных, способную вместить в себя такой объём? Удобнее всего, наверное, использовать Б-деревья.

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

C>не получится обращаться к внешней памяти интенсивно — последовательность идет в иде потока, считывать можно ограниченное число раз и подряд
Алгоритмов, основанных на последовательном доступе, завались. Тот же самый merge sort. Или radix sort.

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

C>кто-нибдуь может подсказать, в какую сторону копать?

Вариант:

Заводим массив, в котором будем хранить интервалы, в которых лежат входные данные: A[N], где A[j]={A[j].min, A[j].max}, N-выбираем исходя из количества памяти, которое не жалко. Чем больше N, тем больше будет интервалов и соответственно выше точность.

Для каждого числа X из входного потока выполняем следующие действия:
Если это число входит в один из уже существующих интервалов, то никаких действий не производим.
Иначе, если существует интервал, граничащий с этим числом, то расширяем его до этого числа. Если таких интервала два (число оказалось между ними), то объединяем эти интервалы, освобождая место под новый интервал.
Если число не граничит ни с одним интервалом и в массиве есть свободное место, то добавляем в него интервал {X,X}, если свободного места нет, то сначала ищем два наиболее близких друг к другу интервала (учитывая интервал {X,X}) и объединяем их.

В итоге получим набор интервалов, в которых лежат входные данные.

Если необходимы не сами интервалы, а только количество различных чисел, то при каждом объединении двух не смежных интервалов увеличиваем счётчик погрешности P на число равное расстоянию между этими интервалами.

Искомое количество различных чисел будет лежать между S и S-P, где S – сумма размеров всех полученных интервалов.

Комментарии:
1. Массив A[N] конечно же отсортированный
2. Вместо массива можно использовать дерево, это ускорит операции с интервалами, но увеличит требования к памяти
3. Вместо A[j].max можно хранить A[j].len

Пойдет?

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

KK>Пойдет?

Спасибо, очень интересно, попробую. Есть какие-нибудь публикации, где этот алгоритм (и подобные) бы описывался, давались бы оценки по зависимости памяти/размера массив/точности результата?

Здравствуйте, 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 миллионов.

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

C>кто-нибдуь может подсказать, в какую сторону копать?

Если распределение близко к равномерному и допустима некоторая ошибка, то можно взять небольшой кусок последовательности (который гарантированно влезет в память) и отсортировать его. Повторяем для других кусков и усредняем результат. Метод даст большую погрешность в случае существенно неравномерного распределения.

Если нужен точный результат, то без внешней памяти в файлах не обойтись. В этом случае сортируем куски, влезающие в память и пишем их в файлы. После чего, в один проход (синхронно по всем файлам) выполняем процедуру, напоминающую merge sort, но без записи результата, а подсчитываем количество неуникальных элементов.

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

KK>Заводим массив, в котором будем хранить интервалы, в которых лежат входные данные: A[N], где A[j]={A[j].min, A[j].max}, N-выбираем исходя из количества памяти, которое не жалко. Чем больше N, тем больше будет интервалов и соответственно выше точность.

KK>Для каждого числа X из входного потока выполняем следующие действия:
KK>Если это число входит в один из уже существующих интервалов, то никаких действий не производим.
KK>Иначе, если существует интервал, граничащий с этим числом, то расширяем его до этого числа. Если таких интервала два (число оказалось между ними), то объединяем эти интервалы, освобождая место под новый интервал.
KK>Если число не граничит ни с одним интервалом и в массиве есть свободное место, то добавляем в него интервал {X,X}, если свободного места нет, то сначала ищем два наиболее близких друг к другу интервала (учитывая интервал {X,X}) и объединяем их.

Для любого наперёд заданного N могу предложить входную последовательность с колоссальной потерей точности.
Скормим сперва числа вида 2k, где k = [1..N] — тем самым выберем всю доступную память.
Затем скормим число m — максимум последовательности. Очевидно, что оно вынужденно попадёт в последний интервал, превратив его в {2N,m}
Вот, собственно, и всё

Кодт wrote:
> KK>Если число не граничит ни с одним интервалом и в массиве есть
> свободное место, то добавляем в него интервал {X,X}, если свободного
> места нет, то сначала ищем два наиболее близких друг к другу интервала
> (учитывая интервал {X,X}) и объединяем их.
>
> Для любого наперёд заданного N могу предложить входную
> последовательность с колоссальной потерей точности.
> Скормим сперва числа вида 2k, где k = [1..N] — тем самым выберем всю
> доступную память.
> Затем скормим число m — максимум последовательности. Очевидно, что оно
> вынужденно попадёт в последний интервал, превратив его в {2N,m}
> Вот, собственно, и всё

Я на эти грабли чуть не наступил. Он же сказал — ищем ближайшие. Найдём
2 и 4. Потеря точности в данном примере будет 1.

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

R>Я на эти грабли чуть не наступил. Он же сказал — ищем ближайшие. Найдём
R>2 и 4. Потеря точности в данном примере будет 1.

Не 1!
Множество интервалов [2;2], [4;4], ..., [2N-2;2N-2], [2N;m] сообщает нам, что встретились Umin..Umax уникальных чисел,
— Umin = 1+1+...+1+2 = N+1
— Umax = 1+1+...+1+m-2N = N-1+m-2N = m-N-1

Пример: N=3.
Последовательности
2 4 6 1000 и далее
— 1000 1000 1000 1000 1000 ... (993 раза)
— 7 8 9 ... 999

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

R>>Он же сказал — ищем ближайшие.
Я же сказал — ищем ближайшие.

К>Не 1!
К>Множество интервалов [2;2], [4;4], ..., [2N-2;2N-2], [2N;m] сообщает нам, что встретились Umin..Umax уникальных чисел,
К>- Umin = 1+1+...+1+2 = N+1
К>- Umax = 1+1+...+1+m-2N = N-1+m-2N = m-N-1

К>Пример: N=3.
К>Последовательности
К>2 4 6 1000 и далее
К>- 1000 1000 1000 1000 1000 ... (993 раза)
К>- 7 8 9 ... 999

Число m не объеденится с интервалом {2N-2;2N-2}. Объединятся интервалы {2;2} и {4;4} и добавится интервал {m;m}. Погрешность = 1.

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

Зато алгоритм работает в один проход и при любой длине входной последовательности.

Если длина входной последовательности не сильно большая, есть возможность сделать несколько проходов и это не сильно накладно, то стоит присмотреться к алгоритму предложенному Rft.

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

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

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

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

C>кто-нибдуь может подсказать, в какую сторону копать?

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

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

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

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

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

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

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

Спасибо. Есть алгоритм Count-Sketch (http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/CharikarCF.pdf), где эта идея развивается, но я пока не видел его обоснования для решения моей задачи.

Здравствуйте, 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 проходов.