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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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

[:0-1] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Кнут, Дональд Эрвин (1997). Искусство компьютерного программирования, том 3, сортировка и поиск . Ридинг, Массачусетс: Аддисон-Уэсли. стр. 527–528. ISBN 0-201-89683-4 . OCLC 36241708 .

[:1-2] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Бендер, Майкл А.; Кушмаул, Брэдли С.; Кушмаул, Уильям (февраль 2022 г.). «Возвращение к линейному зондированию: надгробия знаменуют упадок первичной кластеризации» . 62-й ежегодный симпозиум IEEE по основам информатики (FOCS) , 2021 г. IEEE. стр. 1171–1182. дои : 10.1109/focs52979.2021.00115 . ISBN 978-1-6654-2055-6 . S2CID 235731820 .

[3] Паг, Анна; Паг, Расмус; Ружич, Милан (11 июня 2007 г.). «Линейное зондирование с постоянной независимостью» . Материалы тридцать девятого ежегодного симпозиума ACM по теории вычислений . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 318–327. дои : 10.1145/1250790.1250839 . ISBN 9781595936318 . S2CID 7523004 .

[4] Торуп, Миккель; Чжан, Инь (январь 2012 г.). «5-независимое хеширование на основе таблиц с приложениями к линейному зондированию и оценке второго момента» . SIAM Journal по вычислительной технике . 41 (2): 293–331. дои : 10.1137/100800774 . ISSN 0097-5397 .

[5] Кормен, Томас Х. (2022). Введение в алгоритмы . Чарльз Эрик Лейзерсон, Рональд Л. Ривест, Клиффорд Стейн (Четвертое изд.). Кембридж, Массачусетс. ISBN 978-0-262-04630-5 . OCLC 1264174621 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[6] Дроздек, Адам (1995). Структуры данных в C. PWS Паб. компании ISBN 0-534-93495-1 . ОСЛК 31077222 .

[7] Крузе, Роберт Л. (1987). Структуры данных и проектирование программ (2-е изд.). Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. ISBN 0-13-195884-4 . OCLC 13823328 .

[8] Макмиллан, Майкл (2014). Структуры данных и алгоритмы с использованием JavaScript . Севастополь, Калифорния: О'Рейли. ISBN 978-1-4493-6493-9 . OCLC 876268837 .

[9] Смит, Питер, 1 февраля (2004 г.). Прикладные структуры данных с C++ . Садбери, Массачусетс: Издательство Jones and Bartlett. ISBN 0-7637-2562-5 . OCLC 53138521 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: числовые имена: список авторов ( ссылка )

[10] Трамбле, Жан-Поль (1976). Введение в структуры данных в приложениях . П.Г. Соренсон. Нью-Йорк: МакГроу-Хилл. ISBN 0-07-065150-7 . OCLC 1858301 .

[:2-11] Jump up to: Перейти обратно: ^а ^б Справочник по структурам данных и приложениям . [Sl]: CRC PRESS. 2020. ISBN 978-0-367-57200-6 . OCLC 1156995269 .

[12] Седжвик, Роберт (1998). Алгоритмы на C (Третье изд.). Ридинг, Массачусетс. ISBN 0-201-31452-5 . ОСЛК 37141168 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[13] Эмбл, Кнут (1974). «Упорядоченные хеш-таблицы» . Компьютерный журнал . 17 (2): 135–142. дои : 10.1093/comjnl/17.2.135 .

[14] Селис, Педро, Пер-Аке Ларсон и Дж. Ян Манро. «Робин Гуд перемешивает». 26-й ежегодный симпозиум по основам информатики (SFC, 1985) . ИИЭР, 1985.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]