Инициализировать массив в амортизированном постоянном времени - как называется этот трюк?

13

Существует такая структура данных, которая сравнивает производительность доступа к массиву с необходимостью повторять его при очистке. Вы ведете счетчик поколений с каждой записью, а также глобальный счетчик поколений. «Очистка» увеличивает счетчик генерации. При каждом доступе вы сравниваете локальные и глобальные счетчики генерации; если они отличаются, значение считается «чистым».

Об этом недавно говорилось в ответе о переполнении стека , но я не помню, носит ли этот трюк официальное название. Является ли?

Одним из вариантов использования является алгоритм Дейкстры, если нужно ослабить только крошечное подмножество узлов, и если это нужно делать повторно.

krlmlr
источник
2
Интересный трюк, но у него довольно накладные расходы. Поэтому мне интересно, в каких случаях очистка массива является такой распространенной операцией, за которую платит цена? (Искренний вопрос!)
Иоахим Зауэр
@JoachimSauer: отредактировано.
krlmlr
Звучит очень дорого в общем случае как для использования памяти, так и для стоимости доступа. Вариант использования этой техники должен быть очень конкретным.
Мартин Йорк,
3
@Joachim: он используется для быстрой очистки буферов для рендеринга - примерно. У них просто есть "чистый бит" на 64 КБ или что-то подобное.
DeadMG
3
@ user946850 «amortized» означает, что вы можете доказать, что дорогая операция происходит в общей картине достаточно редко, что она не дает больше, чем, например, O (1)

Ответы:

2

Вышеупомянутый подход требует, чтобы каждая ячейка могла содержать число, достаточно большое, чтобы удерживать количество повторных инициализаций массива, что является существенным штрафом пространства. Если слот способен содержать по крайней мере одно значение, которое никогда не будет записано законным образом, можно избежать любого другого (непостоянного) штрафа за пробел за счет добавления 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и т. Д.).

Чтобы очистить массив, начните с I0 или 1, в зависимости от базы массива (описанный алгоритм будет работать для любого из них). Затем повторите следующую процедуру: если item Iis B, increment Iи, если при этом получается кратное четырем, разделите на четыре (прекратите, если в результате деления получится значение 1); если элемента Iнет B, сохраните Bего и умножьте Iна четыре (если Iначинается с нуля, умножение на четыре оставит ноль, но, поскольку элемент 0 будет пустым, Iбудет увеличен).

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

Supercat
источник
Достаточно иметь счетчик версий, способный вместить достаточно последовательных сбросов, прежде чем все ячейки будут обновлены новыми значениями. На практике может быть достаточно байта или даже меньше в более узких циклах.
9000
@ 9000: код, основанный на таком поведении, склонен быть хрупким, особенно учитывая, что единственной причиной для использования такого «псевдо-чистого» подхода (в отличие от простого очищения массива) является наличие набора элементов, которые могут потребоваться подлежащий очистке, как правило, был небольшим и изменчивым - пара условий, которые способствуют увеличению вероятности того, что предмет может быть использован, «очищен», а затем останется нетронутым в течение сколь угодно длительного времени. Можно рассмотреть сканирование массива и физическую очистку любых старых слотов, когда счетчик собирается обернуться, но ...
суперкат
1
... если значение обтекания счетчика является постоянным, средний объем работы для каждой операции очистки массива будет O (N), где N - это размер массива. Не то чтобы такая вещь могла быть бесполезной на практике, поскольку реализация O (N), которая ускоряется в 65 536 раз, все равно будет O (N), но также будет в 65 536 раз быстрее, чем не улучшенная , Между прочим, случаи, когда эти подходы были бы полезны, могут также выиграть от использования структуры данных разреженного массива, которая может использовать пространство O (AlgN) для хранения массива с массивом размера N с непустыми элементами A.
суперкат
1

Я бы назвал это «переинициализация ленивых ячеек массива», но у него, похоже, нет какого-либо установленного имени (то есть имя широко используется).

Алгоритм умный, но очень специализированный и применим в очень узкой области.

Александр Адамовский
источник
1

Я полагаю, что это особый случай запоминания , за исключением того, что в этом случае «записки» неявно означают «возраст» с каждым шагом глобального счетчика. Я думаю, что-то вроде «запоминания в обратном направлении».

defube
источник