Какая структура данных наиболее эффективна для хранения временных рядов частично изменяющегося массива?

Question

Моя проблема в том, что у меня есть массив объектов размера N. после каждого времени (t + 1) некоторые значения массива могут изменяться или не изменяться.так скажем, t + 1 index 15 изменяется, но все остальное остается прежним.

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

Скажем, для 4 массивов

время 1 ноль нольnull xyz

time 2 null null abc xyz

(обратите внимание, что здесь изменился только abc), но мы сохраняем значения последнего индекса со времени 1.

Answer 1

То, что вы запрашиваете, известно в академической области CS как «частично постоянные массивы». Для получения дополнительной информации о стойкости см. опрос Каплана .

Одним из простых решений является использование поисковых деревьев вместо массивов. Вы можете использовать чисто функциональные сбалансированные деревья поиска, чтобы гарантировать, что для каждого чтения или записи требуется время O (lg n) наихудшего случая (где n - размер массива) вместо времени O (1). (Если вы храните версии с метками времени в расширяемом массиве, добавление новой версии будет O (1) амортизироваться, а доступ к старой версии будет O (1) в худшем случае.)

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

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