У меня есть динамический массив из 10 ^ 7 512-битных элементов, в которые можно добавлять, удалять и обмениваться элементами друг с другом. Каждый раз, когда пользователь манипулирует массивом, я хочу записать изменения экономически эффективным способом, чтобы я мог получить окончательную версию без необходимости оценивать все предыдущие версии. Какая структура данных лучше для этого?
Дорогой способ - хранить все версии массива:
[1,5,7,3,8,2]
[1,4,5,7,3,8,2]
[1,5,4,7,3,8,2]
[1,4,5,3,7,8,2]
[2,4,5,3,7,8,1]
Другой способ (для этого потребуется вычислить каждую версию, чтобы найти текущее состояние):
[1,5,7,3,8,2]
Add 4 between 1 and 5
Switch 4 with 5
Switch 3 with 7
Switch 1 with 2
Есть ли неэффективная по площади альтернатива, которая решает проблему?!
Спасибо!