как найти первый повтор в потоке?

[Димаsick]

Для конечного массива есть много разных методов определения, есть ли в массиве повторы, сколько их и т.п. НО если у нас бесконечный (или оооочень большой) входящий поток чисел (каждое из которых, например, это какое-то натуральное число от 1 до 10^1000), то как не сохраняя все входящие числа, отследить в этом входящем потоке первый повтор?

[CAB]

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

[Димаsick]

Вероятность - это хорошо, но у этой задачи должно быть красивое решение, со слов преподавателя ;)
Я так подозреваю, что нужно от всех просмотренных чисел сохранять какой-то интегральный показатель (сумму? произведение?), по которому потом можно узнать, является ли новое число уникальным, или такое уже было ранее. Ну и ясно, что этот показатель должен расти не так быстро, как растет массив уже просмотренных чисел, т.к. иначе теряется смысл.

[mustitz]

Скорее всего задача немного другая: есть односвязный список, необходимо за $O(1)$ памяти определить, зацикливается он или нет. Тут есть красивое решение: один указатель двигать на один элемент, другой на два. Если указатели совпадут, то список зацикливается. В худшем случае зацикливание списка можно определить после $3n$ итераций, где $n$ количество уникальных элементов в списке.

[Димаsick]

Нет, это не список и не массив, а именно поток.

[Nemiroff]

Хеш, а лучше фильтр Блума. Не 100%, но эффективно.

Цитата:

mustitz в сообщении #1192037 писал(а):

Скорее всего задача немного другая: есть односвязный список, необходимо за $O(1)$ памяти определить, зацикливается он или нет.

"Немного" другая?

[Legioner93]

Задача конечно интересная. Но давайте формализуем, так будет ещё интереснее.

У нас есть бесконечный поток натуральных чисел диапазона $[0, N]$. Есть какой-то алгоритм, который ищет первый повтор в потоке. В общем случае номер первого повтора $= O(N)$. Исходя из этого, мы можем оценить занимаемую память и количество операций (у нас будет поиск и вставка $O(N)$ раз)

Что для обычного массива, что для ассоциативного, память получается $O(N \log {N})$ (логарифм вылез из-за того, что у нас $N$ много больше машинного слова).

Под "не сохраняя все просмотренные числа" тогда можно понимать требование занимать меньше памяти, чем $O(N \log {N})$. Будет интересно, если такой алгоритм найдётся, но надо ещё будет посмотреть, что там по числу операций.

[fractalon]

Раз уж раздел математический, то скажу математично: пусть у вас после прихода из потока $n$ чисел (каждое по $m$ бит) занято $k$ битов памяти. Чтобы ваша программа корректно отвечала в этот момент на любое число, она должна различать любые возможные множества введённых до этого чисел, которых есть ровно $C_{2^m}^{n} + C_{2^m}^{n-1} + \dots + C_{2^m}^{0} > C_{2^m}^{n} > \frac{(2^m-n)^n}{n!} > \frac{2^{(m-1)n}}{n!} > \frac{1}{\sqrt{4 \pi n}} \frac{2^{(m-1)n} e^n}{n^n} = \Theta(2^{(m-1)n+\frac{n}{2}-\frac{n \ln n}{\ln{2}}}) > 2^{(m-1)n-\frac{n \ln n}{\ln{2}}} > 2^{(m-1)n/2}$ (я тут предполагаю, что $n<2^{m/2}$, так как вы сказали об очень больших чисел). И это, если приглядеться, очень грубые оценки. Но даже по ним вам нужно обязательно $\frac{(m-1)n}{2}$ битов, иначе будут два вариантов входящей последовательности, для которой у вас память встанет в одно положение, и чтобы выявить ошибку в вашей программе, останется изучить, какое именно множество она мнит введённым перед переходом памяти в это состояние.

[Dmitriy40]

Хранить номер $N$ и битовый массив встреченных чисел $[0..M]$, $M$ - максимальное по величине обработанное число. Если бит в массиве для текущего числа уже равен 1 - встретили повтор. Если нет, то при необходимости расширить массив и установить бит для текущего числа в 1. Всё, цикл по входному потоку.
Затраты времени $O(N)$, затраты памяти $O(M)$. Для сильно разреженного потока затраты памяти можно оптимизировать хранив вместо линейного массива битов дерево неполных интервалов (полностью пустые и полностью полные не хранить).

[fractalon]

А если по делу, то в таких задачах обычно предполагается, что введённые числа из диапазона $[0;N]$ выбираются более-менее равновероятно. Ну и в этом случае можно применять какое угодно хэширование - например. разбить ваше число на блоки по $t$ битов (с каким-то маленьким $t$, типа $t=20$) и взять их всеобщий побитовый xor. И его сохранить вместо самого числа. xor-ы в этом случае тоже будут распределены равновероятно. И тут нужен такой (не очень порядочный) трюк постановки задачи, чтобы входящий поток был какой-то адекватной длины и искомый повтор-то как раз вводился не случайно.
То есть если вы наткнулись на число с тем же xor-ом, что и одно из предыдущих, то вероятность случиться так на $n$-ом шаге случайно, равна $1-\left({1-\frac{1}{2^t}}\right)^n \sim 1 - e^\frac{n}{2^t}$. Поэтому можно делать вывод что его туда ввёл кто-то разумный

-- 12.02.2017, 20:51 --

Dmitriy40
В том-то и загвоздка, что обрабатываемые числа могут быть порядка $10^{1000}$. Массив на такое количество элементов не заведёшь. И как там ни храни интервалы, по памяти это выйдет не меньше (асимптотически), чем хранить напрямую все числа, а это делать как раз нельзя.

[MetaMorphy]

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