найти последний элемент, но N в потоке без хранения n элементов

Question

Предположим, что поступает поток данных, D (0), D (1), D (2), .... Когда приходит D (i), я хочу знать D (i - N).Самый простой способ - хранить самые последние N элементов и обновлять их по мере поступления новых данных.Но проблема в том, что N может быть большим, так что не хватает памяти для их хранения.Есть ли способ достичь этого, храня гораздо меньше предметов, чем N?Константа M << N пробелов предпочтительнее?Заранее спасибо. </p>

Answer 1

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

Вместо этого рассмотрим:

• Можете ли вы уменьшить N ?
• Можете ли вы хранить информацию на диске или (если выво встроенной среде) на более медленной и дешевой форме памяти?
• Есть ли какая-то закономерность в данных?Если есть, например, повторяющийся шаблон, вы можете использовать это, или если между числами существует некоторая математическая связь, возможно, некоторая формула может помочь в восстановлении одного числа из других.Даже если нет заметного шаблона, возможно, вы могли бы использовать какой-то алгоритм сжатия для уменьшения размера данных?
• Есть ли какие-то ограничения для данных, например, каждое число находится в диапазоне от 0 до 255?Если это так, вы могли бы, возможно, уменьшить требования к хранилищу.

(Кстати, как это можно применить?)