Первичная кластеризация

Явление, наблюдаемое в хэш-таблицах

В программировании первичная кластеризация — это явление, которое вызывает снижение производительности в хэш -таблицах с линейным зондированием . Это явление заключается в том, что по мере добавления элементов в хэш-таблицу с линейным зондированием они имеют тенденцию группироваться в длинные прогоны (т. е. длинные смежные области хэш-таблицы, не содержащие свободных слотов). Если хэш-таблица имеет коэффициент загрузки для некоторого параметра , то ожидаемая длина прогона, содержащего заданный элемент, составляет . Это приводит к тому, что вставки и отрицательные запросы занимают ожидаемое время в хэш-таблице с линейным зондированием. ${\displaystyle 1-1/x}$ ${\displaystyle x\geq 2}$ ${\displaystyle u}$ ${\displaystyle \Theta (x^{2})}$ ${\displaystyle \Theta (x^{2})}$

Причины первичной кластеризации

Первичная кластеризация имеет две причины:

• Победитель продолжает побеждать: чем длиннее становится серия, тем больше вероятность накопления дополнительных элементов. Это вызывает положительную обратную связь, которая способствует эффекту кластеризации. Однако это само по себе не вызвало бы квадратичного взрыва. ^{[1] [2]}
• Объединение серий: одна вставка может не только увеличить длину серии, в которой она находится, на единицу, но и вместо этого может соединить вместе две серии, которые уже были относительно длинными. Это то, что вызывает квадратичное увеличение ожидаемой длины серии. ^[1]

Другой способ понять первичную кластеризацию — изучить стандартное отклонение количества элементов, которые хэшируются в заданную область в хэш-таблице. ^[2] Рассмотрим подобласть хэш-таблицы размером . Ожидаемое количество элементов, которые хэшируются в область, равно . С другой стороны, стандартное отклонение количества таких элементов равно . Из этого следует, что с вероятностью количество элементов, которые хэшируются в область, превысит размер области. Интуитивно это означает, что области размером часто будут переполняться, в то время как более крупные области, как правило, этого не делают. Эта интуиция часто используется в качестве отправной точки для формального анализа первичной кластеризации. ^{[2] [3] [4]} ${\displaystyle x^{2}}$ ${\displaystyle (1-1/x)x^{2}=x^{2}-x}$ ${\displaystyle \Theta (x)}$ ${\displaystyle \Omega (1)}$ ${\displaystyle x^{2}}$ ${\displaystyle \Theta (x^{2})}$

Влияние на производительность

Первичная кластеризация приводит к снижению производительности как для вставок, так и для запросов в линейной хэш-таблице зондирования. Вставки должны перемещаться в конец прогона и, следовательно, занимать ожидаемое время . ^[1] Отрицательные запросы (т. е. запросы, которые ищут элемент, который оказывается отсутствующим) также должны перемещаться в конец прогона и, следовательно, также занимать ожидаемое время . ^[1] Положительные запросы могут быть завершены, как только они найдут элемент, который они ищут. В результате ожидаемое время запроса случайного элемента в хэш-таблице составляет . ^[1] Однако положительные запросы к недавно вставленным элементам (например, элементу, который был только что вставлен) занимают ожидаемое время . ^[1] ${\displaystyle \Theta (x^{2})}$ ${\displaystyle \Theta (x^{2})}$ ${\displaystyle \Theta (x)}$ ${\displaystyle \Theta (x^{2})}$

Эти границы также справедливы для линейного зондирования с ленивыми удалениями (т.е. с использованием надгробий для удалений), пока хэш-таблица перестраивается (и надгробия очищаются) получасто. Достаточно выполнять такую ​​перестройку по крайней мере один раз за каждую вставку. ^[2] ${\displaystyle n/(2x)}$

Распространенные заблуждения

Во многих учебниках эффект «победитель сохраняет победу» (при котором чем длиннее становится серия, тем больше вероятность накопления дополнительных элементов) описывается как единственная причина первичной кластеризации. ^{[5] [6] [7] [8] [9] [10] [11]} Однако, как отметил Кнут, ^[1] это не главная причина первичной кластеризации.

В некоторых учебниках указано, что ожидаемое время для положительного запроса составляет , ^{[11] [12]} обычно ссылаясь на Кнута. ^[1] Это справедливо для запроса к случайному элементу. Однако некоторые положительные запросы могут иметь гораздо большее ожидаемое время выполнения. Например, если вставить элемент, а затем немедленно запросить этот элемент, запрос займет столько же времени, сколько и вставка, что и ожидается. ${\displaystyle \Theta (x)}$ ${\displaystyle \Theta (x^{2})}$

Методы избежания первичной кластеризации

Упорядоченное линейное зондирование ^[13] (часто называемое хэшированием Робин Гуда ^[14] ) — это метод снижения влияния первичной кластеризации на запросы. Упорядоченное линейное зондирование сортирует элементы в каждом запуске по их хэшу. Таким образом, запрос может быть завершен, как только он встретит любой элемент, хэш которого больше, чем у запрашиваемого элемента. Это приводит к тому, что как положительные, так и отрицательные запросы занимают ожидаемое время . ${\displaystyle O(x)}$

Хеширование кладбища — это вариант упорядоченного линейного зондирования, который устраняет асимптотические эффекты первичной кластеризации для всех операций. ^[2] Хеширование кладбища стратегически оставляет пробелы в запусках, которые могут быть использованы будущими вставками. Эти пробелы, которые можно рассматривать как надгробия (подобно тем, которые создаются ленивыми удалениями ), вставляются в таблицу во время полурегулярных перестроек. Затем пробелы ускоряют вставки, которые происходят до тех пор, пока не произойдет следующая полурегулярная перестройка. Каждая операция в хеш-таблице кладбища занимает ожидаемое время . ${\displaystyle O(x)}$

Многие источники рекомендуют использовать квадратичное зондирование в качестве альтернативы линейному зондированию, которое эмпирически позволяет избежать эффектов первичной кластеризации.

Ссылки

1. Кнут, Дональд Эрвин (1997). Искусство программирования, том 3, сортировка и поиск. Reading, Массачусетс: Addison-Wesley. С. 527–528. ISBN 0-201-89683-4. OCLC  36241708.
2. Бендер, Майкл А.; Кушмаул, Брэдли К.; Кушмаул, Уильям (февраль 2022 г.). «Пересмотр линейного зондирования: надгробные плиты знаменуют конец первичной кластеризации». 62-й ежегодный симпозиум IEEE по основам компьютерной науки (FOCS) 2021 г. IEEE. стр. 1171–1182. doi :10.1109/focs52979.2021.00115. ISBN 978-1-6654-2055-6. S2CID  235731820.
3. Pagh, Anna; Pagh, Rasmus; Ruzic, Milan (2007-06-11). "Линейное зондирование с постоянной независимостью". Труды тридцать девятого ежегодного симпозиума ACM по теории вычислений . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 318–327. doi :10.1145/1250790.1250839. ISBN 9781595936318. S2CID  7523004.
4. Торуп, Миккель; Чжан, Инь (январь 2012 г.). «Табулированное хеширование 5-независимых элементов с применением к линейному зондированию и оценке второго момента». Журнал SIAM по вычислениям . 41 (2): 293–331. doi :10.1137/100800774. ISSN  0097-5397.
5. Кормен, Томас Х. (2022). Введение в алгоритмы. Чарльз Эрик Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн (Четвертое изд.). Кембридж, Массачусетс. ISBN 978-0-262-04630-5. OCLC  1264174621.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
6. Дроздек, Адам (1995). Структуры данных в C. PWS Pub. Co. ISBN 0-534-93495-1. OCLC  31077222.
7. Круз, Роберт Л. (1987). Структуры данных и проектирование программ (2-е изд.). Энглвуд Клиффс, Нью-Джерси: Prentice-Hall. ISBN 0-13-195884-4. OCLC  13823328.
8. Макмиллан, Майкл (2014). Структуры данных и алгоритмы с JavaScript. Севастополь, Калифорния: O'Reilly. ISBN 978-1-4493-6493-9. OCLC  876268837.
9. Смит, Питер, 1 февраля (2004). Прикладные структуры данных с C++. Садбери, Массачусетс: Jones and Bartlett Publishers. ISBN 0-7637-2562-5. OCLC  53138521.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: числовые имена: список авторов ( ссылка )
10. Трембле, Жан-Поль (1976). Введение в структуры данных с приложениями. PG Sorenson. Нью-Йорк: McGraw-Hill. ISBN 0-07-065150-7. OCLC  1858301.
11. Справочник по структурам данных и приложениям. [Sl]: CRC PRESS. 2020. ISBN 978-0-367-57200-6. OCLC  1156995269.
12. Седжвик, Роберт (1998). Алгоритмы на языке C (третье изд.). Рединг, Массачусетс. ISBN 0-201-31452-5. OCLC  37141168.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
13. Эмбл, Кнут (1974). «Упорядоченные хэш-таблицы». The Computer Journal . 17 (2): 135–142. doi : 10.1093/comjnl/17.2.135 .
14. Селис, Педро, Пер-Аке Ларсон и Дж. Ян Манро. «Хеширование Робин Гуда». 26-й ежегодный симпозиум по основам компьютерной науки (sfcs 1985) . IEEE, 1985.