Проверка надежности потока путем выявления пробелов в последовательности

Question

Я работаю над проблемой, которая, по моему мнению, сводится к следующему и надеялась найти структуры данных или алгоритмы, которые могут решить эту проблему с помощью памяти.

Скажите, что вы читаете из (бесконечного) пара порядковых номеров. Некоторый производитель испускает числа в этот поток последовательно без повторения, и вы читаете их с другого конца. Однако есть пара проблем.

1.) Есть что-то об этой системе по своей сути ненадежной. Либо поток, либо производитель или что-то промежуточное может отбросить часть данных, чтобы номера не отображались у потребителя, и в целом существует (неизвестная) вероятность p, что любое заданное число может быть потеряно.

2.) Поток не гарантирует безупречный заказ. Для аргумента предположим, что существует некоторая (известная) константа N, так что если вы читаете номер x из потока, вы можете быть уверены, что после этого момента вы никогда не увидите число y < x - N.

То есть, последовательность чисел может быть только N значения «не в порядке» в любое время.

В этом случае я бы действительно хотел идентифицировать p. Или разумная оценка p - это все, что имеет значение.

Буду признателен за любые ссылки на соответствующие структуры данных или алгоритмы, которые помогли бы решить эту проблему с помощью памяти. Некоторый короткий псевдокод был бы полезен. Благодаря!

EDIT: По соображениям памяти Я имею в виду, что я надеюсь, что смогу решить эту проблему без использования памяти O (N), где N - количество записей, которые я прочитал из потока.

Answer 1

Простой подход может быть следующим.

Предположим, что вы слушаете поток в течение достаточно длительного времени, а последний номер, который вы прочитали, - x. Тогда вы знаете, что все числа меньше, чем x-N, либо уже получены либо потеряны. Если вы сохраните все полученные цифры, вы можете легко узнать, сколько цифр меньше x-N у вас уже есть Фактически получено; допустим, вы действительно получили A номеров. И вы определенно знаете ^*, сколько цифр меньше x-N Вы были ожидали, чтобы получить, предположим, что вы ожидали получить B номеров. Соотношение этих двух значений, A/B, даст вам хорошую оценку p.

^* Это зависит от того, знаете ли вы первое число, которое вы должны были получить. Если, например, вы знаете, что последовательность начинается с 0, тогда вы должны были ожидать B=x-N номеров. Если вы не знаете стартовый номер, вы можете ограничить его аналогично тому, что я описал выше, взяв первый полученный номер, z и рассматривая только цифры между z+N и x-N.

---

Для поиска A вы можете использовать многие структуры данных. Двоичное дерево поиска является очевидным выбором.Или вы можете сохранить только общее количество полученных и N самых больших чисел, когда-либо полученных, для этого BST также является хорошим вариантом.