Дает ли функция секционирования быструю сортировку своего местоположения ссылки?
Дает ли функция секционирования быструю сортировку своего местоположения ссылки? Если да, то как?
Я имею в виду то, что есть в быстрой сортировке, которая дает ему местоположение ссылки по сравнению с другими алгоритмами, такими как сортировка слиянием или сортировка кучи?
Я также читал, что
"Шаг разделения в быстрой сортировке обычно имеет отличную локализацию, поскольку он обращается к последовательным элементам массива около передней и задней частей".
я не понял?
2 ответа
В целом, код имеет хорошее месторасположение, если доступ к памяти, который он делает, имеет тенденцию последовательно располагаться вокруг небольшого количества областей памяти. Например, линейный поиск по массиву имеет отличную локализацию ссылок, потому что все элементы отображаются смежно в памяти, но линейный поиск по связанному списку имеет плохую локализацию, потому что ячейки связанного списка не обязательно появляются последовательно в памяти.
Давайте посмотрим на быструю сортировку. "Мясо" алгоритма быстрой сортировки - это шаг разделения, когда элементы переставляются вокруг оси. Существует несколько стратегий реализации алгоритма разбиения, большинство из которых имеют отличную локальность. Один общий подход работает путем сканирования внутрь от концов массива к центру, меняя местами элементы, когда они относительно неуместны. Этот алгоритм ограничивает доступ к большинству массивов в двух областях - концах массива и последовательно обращается к элементам, поэтому он имеет большую локальность.
Другая стратегия разделения работает путем сканирования слева от массива вправо, сохраняя два указателя, ограничивающих области, содержащие меньшие значения и большие значения. Опять же, доступ к массиву все последовательные, так что локальность действительно хорошая.
Теперь сопоставьте это с heapsort. В heapsort операции кучи требуют многократного сравнения элементов в одной позиции с элементами, индекс которых в два раза или вдвое меньше индекса этого элемента. Это означает, что обращения к массиву разбросаны по всему массиву, а не последовательно, поэтому общая локальность намного хуже.
Mergesort на самом деле имеет довольно приличную локализацию из-за того, как работает шаг слияния. Однако, поскольку он поддерживает вспомогательный буферный массив, который так же велик, как входной массив, он должен оплачивать стоимость дополнительной памяти, и поэтому его доступы немного разбросаны, чем доступы быстрой сортировки.
"Ссылочная местность" относится к часто используемой памяти (временная локальность) или к смежным областям памяти (пространственная местность), как в массиве. По сути, это означает, что машине (точнее, кеш-памяти) легче и, следовательно, быстрее получить доступ к этим ячейкам памяти.
Рассмотрим алгоритм сортировки слиянием.
Сначала (виртуально) он делит массив на половину до наименьшей единицы, то есть на единичные элементы (функцияразбиения). Затем он сравнивает массивы по два за раз и объединяет их отсортированным образом (функцияслияния). Рассмотрим пример слияния ч / б двух массивов длиной n, скажем, arr[0]...arr[n-1] и arr[n]...arr[2n-1]. Процессор должен получить первые элементы обоих массивов, то есть arr [0] и arr [n]. Поскольку они не локализованы, это будет менее эффективно.
Сравните это с алгоритмом быстрой сортировки.
Каждое сравнение в функции секционирования происходит среди соседних, то есть локализованных областей памяти, поэтому оно будет эффективно кешировать.
Надеюсь это поможет!