Существует такая структура данных, которая сравнивает производительность доступа к массиву с необходимостью повторять его при очистке. Вы ведете счетчик поколений с каждой записью, а также глобальный счетчик поколений. «Очистка» увеличивает счетчик генерации. При каждом доступе вы сравниваете локальные и глобальные счетчики генерации; если они отличаются, значение считается «чистым».
Об этом недавно говорилось в ответе о переполнении стека , но я не помню, носит ли этот трюк официальное название. Является ли?
Одним из вариантов использования является алгоритм Дейкстры, если нужно ослабить только крошечное подмножество узлов, и если это нужно делать повторно.
algorithms
terminology
krlmlr
источник
источник
Ответы:
Вышеупомянутый подход требует, чтобы каждая ячейка могла содержать число, достаточно большое, чтобы удерживать количество повторных инициализаций массива, что является существенным штрафом пространства. Если слот способен содержать по крайней мере одно значение, которое никогда не будет записано законным образом, можно избежать любого другого (непостоянного) штрафа за пробел за счет добавления
O(Wlg(N))
штрафа по времени, гдеW
число отдельных интервалов массива, записанных между операции очистки иN
это размер массива. Например, предположим, что один будет хранить целые числа от -2 147 483 647 до 2 147 483 647 (но никогда не -2 147 483 648), а один хочет, чтобы пустые элементы массива читались как ноль. Начните с заполнения массива -2,147,483,648 (вызовите это значениеB
). При чтении слота массива для приложения укажите значениеB
ноль. Перед записью слота массиваI
, проверьте, удерживается ли он,B
и если да, тоI
больше ли он , сохраните нулевое значение в слотеI/4
после выполнения аналогичной проверки для этого местоположения (и, если оно удерживаетсяB
,I/16
и т. Д.).Чтобы очистить массив, начните с
I
0 или 1, в зависимости от базы массива (описанный алгоритм будет работать для любого из них). Затем повторите следующую процедуру: если itemI
isB
, incrementI
и, если при этом получается кратное четырем, разделите на четыре (прекратите, если в результате деления получится значение 1); если элементаI
нетB
, сохранитеB
его и умножьтеI
на четыре (еслиI
начинается с нуля, умножение на четыре оставит ноль, но, поскольку элемент 0 будет пустым,I
будет увеличен).Обратите внимание, что можно заменить константу «четыре» выше другими числами, с большими значениями, обычно требующими меньшего количества рабочих меток, но меньшими значениями, как правило, требующими меньшего количества очистки работы; поскольку помеченные слоты массивов должны быть очищены, значение три или четыре почти наверняка является оптимальным; поскольку значение четыре, безусловно, близко к оптимальному, лучше, чем два или восемь, и более удобно, чем любое другое число, это может показаться наиболее разумным выбором.
источник
Я бы назвал это «переинициализация ленивых ячеек массива», но у него, похоже, нет какого-либо установленного имени (то есть имя широко используется).
Алгоритм умный, но очень специализированный и применим в очень узкой области.
источник
Я полагаю, что это особый случай запоминания , за исключением того, что в этом случае «записки» неявно означают «возраст» с каждым шагом глобального счетчика. Я думаю, что-то вроде «запоминания в обратном направлении».
источник