Сортировка проксмап

Сортировка проксмап
	Insertion sorting into buckets during proxmap. Пример сортировки вставкой, сортирующей список случайных чисел.
Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность
Лучшая производительность
Средняя производительность
Наихудшая пространственная сложность

В отличие от сортировки сегментов, которая сортируется после того, как все сегменты заполнены, элементы сортируются вставкой по мере их вставки.

ProxmapSort или сортировка Proxmap — это алгоритм сортировки , который работает путем разделения массива элементов данных или ключей на несколько «подмассивов» (в аналогичных сортировках называемых сегментами). Это сокращение от вычисления «карты близости», которая указывает для каждого ключа K начало подмассива, где K будет находиться в окончательном отсортированном порядке. Ключи помещаются в каждый подмассив с помощью сортировки вставкой . Если ключи «хорошо распределены» по подмассивам, сортировка происходит за линейное время. Оценки вычислительной сложности включают количество подмассивов и используемую функцию отображения близости, «ключ карты». Это разновидность сегментной и поразрядной сортировки .

После завершения ProxmapSort ProxmapSearch можно использовать для поиска ключей в отсортированном массиве. $O(1)$ время, если ключи были хорошо распределены во время сортировки.

Оба алгоритма были изобретены в конце 1980-х годов профессором Томасом А. Стэндишем в Калифорнийском университете в Ирвайне .

Обзор

Базовая стратегия

В общем: Дан массив A с n ключами:

сопоставьте ключ с подмассивом целевого массива A2 , применив функцию ключа карты к каждому элементу массива
определить, сколько ключей будет отображаться в одном и том же подмассиве, используя массив «количеств попаданий», H
определить, где каждый подмассив будет начинаться в целевом массиве, чтобы каждый сегмент имел точно правильный размер для хранения всех ключей, которые будут отображаться в него, используя массив «proxmaps», P
для каждого ключа вычислите подмассив, которому он будет соответствовать, используя массив «местоположений» L
для каждого ключа найдите его местоположение и поместите его в эту ячейку A2 ; если он сталкивается с ключом, уже находящимся в этой позиции, вставка сортирует ключ на место, перемещая ключи, большие, чем этот ключ, вправо на один, чтобы освободить место для этого ключа. Поскольку подмассив достаточно велик, чтобы вместить все сопоставленные с ним ключи, такое перемещение никогда не приведет к переполнению ключей в следующий подмассив.

Упрощенная версия: Дан массив A с n ключами.

Инициализация : создайте и инициализируйте 2 массива размера n : hitCount , proxMap и 2 массива размера A.length : location и A2 .
Разделение : используя тщательно выбранную функцию MapKey , разделите A2 на подмассивы, используя ключи в A.
Рассредоточение : Прочитайте A , бросив каждый ключ в свое ведро в A2 ; сортировка вставками по мере необходимости.
Собрать : посетите подмассивы по порядку и поместите все элементы обратно в исходный массив или просто используйте A2 .

Примечание. «ключи» также могут содержать другие данные, например массив объектов Student, которые содержат ключ, а также идентификатор и имя учащегося. Это делает ProxMapSort подходящим для организации групп объектов, а не только самих ключей.

Пример

Рассмотрим полный массив: A [ от 0 до n-1 ] с n ключами. Пусть i будет индексом A. Сортируйте A ключи в массив A2 одинакового размера.

Функция ключа карты определяется как MapKey(key) = Floor(K).

Таблица массива
А	6.7	5.9	8.4	1.2	7.3	3.7	11.5	1.1	4.8	0.4	10.5	6.1	1.8
ЧАС	1	3	0	1	1	1	2	1	1	0	1	1
П	0	1	-9	4	5	6	7	9	10	-9	11	12
л	7	6	10	1	9	4	12	1	5	0	11	7	1
А2	0.4	1.1	1.2	1.8	3.7	4.8	5.9	6.1	6.7	7.3	8.4	10.5	11.5

Псевдокод

// compute hit counts
for i = 0 to 11 // where 11 is n
{
    H[i] = 0;
}
for i = 0 to 12 // where 12 is A.length
{
    pos = MapKey(A[i]);
    H[pos] = H[pos] + 1;
}

runningTotal = 0; // compute prox map – location of start of each subarray
for i = 0 to 11
    if H[i] = 0
        P[i] = -9;
    else
        P[i] = runningTotal;
        runningTotal = runningTotal + H[i];

for i = 0 to 12 // compute location – subarray – in A2 into which each item in A is to be placed
    L[i] = P[MapKey(A[i])];

for I = 0 to 12; // sort items
    A2[I] = <empty>;
for i = 0 to 12 // insert each item into subarray beginning at start, preserving order
{
    start = L[i]; // subarray for this item begins at this location
    insertion made = false;
    for j = start to (<the end of A2 is found, and insertion not made>)
    {
        if A2[j] == <empty> // if subarray empty, just put item in first position of subarray
            A2[j] = A[i];
            insertion made = true;
        else if A[i] < A2[j] // key belongs at A2[j]
            int end = j + 1; // find end of used part of subarray – where first <empty> is
            while (A2[end] != <empty>)
                end++;
            for k = end -1 to j // move larger keys to the right 1 cell
                A2[k+1] = A2[k];
                A2[j] = A[i];
            insertion made = true; // add in new key
    }
}

Здесь A — это массив, который нужно отсортировать, а функции MapKey определяют количество используемых подмассивов. Например, Floor(K) просто назначит столько подмассивов, сколько имеется целых чисел из данных A. в Деление ключа на константу уменьшает количество подмассивов; Для перевода диапазона элементов в A в подмассивы можно использовать различные функции, например преобразование букв A–Z в 0–25 или возврат первого символа (0–255) для сортировки строк. Подмассивы сортируются по мере поступления данных, а не после того, как все данные были помещены в подмассив, как это обычно бывает при сортировке сегментов .

Поиск по проксимапам

ProxmapSearch использует массив proxMap, сгенерированный ранее выполненным ProxmapSort, для поиска ключей в отсортированном массиве A2 за постоянное время.

Базовая стратегия

Сортируйте ключи с помощью ProxmapSort, сохраняя функцию MapKey и P и A2. массивы
Чтобы найти ключ, перейдите к P[MapKey(k)], началу подмассива, содержащего ключ, если этот ключ есть в наборе данных.
Последовательный поиск в подмассиве; если ключ найден, вернуть его (и связанную с ним информацию); если найти значение больше ключа, ключа нет в наборе данных
Вычисление P[MapKey(k)] занимает $O(1)$ время. Если во время сортировки использовался ключ карты, который дает хорошее распределение ключей, каждый подмассив ограничен сверху константой c , поэтому требуется не более сравнений , чтобы найти ключ или узнать, что он отсутствует; поэтому ProxmapSearch $O(1)$ . Если использовался худший ключ карты, все ключи находятся в одном подмассиве, поэтому ProxmapSearch в этом худшем случае потребует $O(n)$ сравнения.

Псевдокод

function mapKey(key) is
    return floor(key)

    proxMap ← previously generated proxmap array of size n
    A2 ← previously sorted array of size n
function proxmap-search(key) is
    for i = proxMap[mapKey(key)] to length(array) − 1 do
        if sortedArray[i].key == key then
            return sortedArray[i]

Анализ

Производительность

Вычисление H, P и L требует $O(n)$ время. Каждый из них вычисляется за один проход по массиву с постоянным временем, затрачиваемым на каждую позицию массива.

В худшем случае: MapKey помещает все элементы в один подмассив, что приводит к стандартной сортировке вставкой и времени $O(n^{2})$ .
В лучшем случае: MapKey доставляет одинаковое небольшое количество элементов в каждый подмассив в том порядке, в котором реализуется лучший случай сортировки вставкой. Каждая сортировка вставкой $O(c)$ , c размер подмассивов; существует p подмассивов, поэтому p * c = n , поэтому фаза вставки занимает O(n); таким образом, ProxmapSort $O(n)$ .
Средний случай: размер каждого подмассива не превышает c , константа; тогда сортировка вставкой для каждого подмассива составляет в худшем случае O(c^2) — константу. (Фактическое время может быть намного лучше, поскольку элементы c не сортируются до тех пор, пока последний элемент не будет помещен в корзину). Общее время — это количество сегментов, (n/c) , раз $O(c^{2})$ = $O(n)$ .

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

Оптимизации

Экономьте время: сохраните значения MapKey(i), чтобы их не приходилось пересчитывать (как в приведенном выше коде).
Экономия места: proxMaps можно хранить в массиве hitCount, поскольку счетчики попаданий не нужны после вычисления proxmap; данные можно отсортировать обратно в A вместо использования A2, если позаботиться о том, какие значения A уже отсортированы, а какие нет.

Реализация кода JavaScript:

Array.prototype.ProxmapSort = function()
{//-- Edit date: 2019/11/13 Taiwan --//
  var start = 0;
  var end = this.length;
  var A2 = new Array(end);
  var MapKey = new Array(end);
  var hitCount = new Array(end);
  
  for (var i = start; i < end; i++) { hitCount[i] = 0; }
  var min = this[start];
  var max = this[start];
  for (var i = start+1; i < end; i++) {
    if (this[i] < min) { min = this[i]; }
    else {if (this[i] > max) { max = this[i]; }}
  }
  //Optimization 1.Save the MapKey[i].
  for (var i = start; i < end; i++) {
    MapKey[i] = Math.floor(((this[i] - min ) / (max - min )) * (end - 1));
    hitCount[MapKey[i]]++;
  }
  //Optimization 2.ProxMaps store in the hitCount.
  hitCount[end-1] = end - hitCount[end-1];
  for (var i = end-1; i > start; i--){
    hitCount[i-1] = hitCount[i] - hitCount[i-1];
  }
  //insert A[i]=this[i] to A2 correct position
  var insertIndex = 0;
  var insertStart = 0;
  for (var i = start; i < end; i++) {
    insertIndex = hitCount[MapKey[i]];
    insertStart = insertIndex;
    while (A2[insertIndex] != null) { insertIndex++; }
    while (insertIndex > insertStart && this[i] < A2[insertIndex-1]) {
      A2[insertIndex] = A2[insertIndex-1];
      insertIndex--;
    }
    A2[insertIndex] = this[i];
  }
  for (var i = start; i < end; i++) { this[i] = A2[i]; }
};

Сравнение с другими алгоритмами сортировки

Поскольку ProxmapSort не является сортировкой сравнения , нижняя граница Ω( n log n ) неприменима. ^{[ нужна ссылка ]} Его скорость можно объяснить тем, что он не основан на сравнении и использует массивы вместо динамически выделяемых объектов и указателей, которым необходимо следовать, как это происходит при использовании двоичного дерева поиска .

ProxmapSort позволяет использовать ProxmapSearch. Несмотря на время сборки O(n), ProxMapSearch компенсирует это своим $O(1)$ среднее время доступа, что делает его очень привлекательным для больших баз данных. Если данные не требуют частого обновления, время доступа может сделать эту функцию более выгодной, чем другие сортировки, основанные на сортировке без сравнения .

Общая сортировка сегментов, связанная с ProxmapSort

Как и ProxmapSort, сегментная сортировка обычно работает со списком из n числовых входных данных между нулем и некоторым максимальным ключом или значением M и делит диапазон значений на n сегментов, каждый размером M / n . Если каждый сегмент сортируется с использованием сортировки вставками , можно показать, что ProxmapSort и сортировка сегментов выполняются в прогнозируемое линейное время. ^[1]^{[ оригинальное исследование? ]} Однако производительность такого рода снижается при кластеризации (или при слишком малом количестве сегментов со слишком большим количеством ключей); если много значений встречаются близко друг к другу, все они попадут в один блок, и производительность существенно снизится. Такое поведение справедливо и для ProxmapSort: если сегменты слишком велики, его производительность сильно ухудшится.

Ссылки

^ Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 8.4: Сортировка по сегментам, стр. 174–177.

Томас А. Стэндиш. Структуры данных в Java. Эддисон Уэсли Лонгман, 1998 год. ISBN 0-201-30564-X . Раздел 10.6, стр. 394–405.
Стэндиш, Т.А.; Джейкобсон, Н. (2005). «Использование $O (n)$ Proxmap Sort и $O (1)$ Proxmap Search для мотивации студентов CS2 (Часть I)». Бюллетень ACM SIGCSE . 37 (4). дои : 10.1145/1113847.1113874 .
Стэндиш, Т.А.; Джейкобсон, Н. (2006). «Использование $O (n)$ Proxmap Sort и $O (1)$ Proxmap Search для мотивации студентов CS2, Часть II». Бюллетень ACM SIGCSE . 38 (2). дои : 10.1145/1138403.1138427 .
Норман Джейкобсон «Краткий обзор ProxmapSort и ProxmapSearch» от факультета компьютерных наук Школы информатики и компьютерных наук Дональда Брена , Калифорнийский университет в Ирвине .

Внешние ссылки

[1] Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 8.4: Сортировка по сегментам, стр. 174–177.

[1]

v т и Алгоритмы сортировки
Теория	Теория сложности вычислений Обозначение большого О Общий заказ Списки Размещение Стабильность Сортировка сравнения Адаптивная сортировка Сортировочная сеть Целочисленная сортировка X + Y сортировка Трансдихотомическая модель Квантовая сортировка
Обмен сортами	Пузырьковая сортировка Сорт коктейльного шейкера Нечетно-четный сорт Гребенчатая сортировка Гном сортирует Пропорциональное расширение сортировки Быстрая сортировка
Сортировки выбора	Сортировка выбором пирамидальная сортировка Гладкая сортировка Декартова сортировка дерева Сортировка турниров Циклическая сортировка Слабая пирамидальная сортировка
Сортировки вставками	Сортировка вставкой Шеллсорт Сплейсорт Сортировка дерева Сортировка библиотеки Сортировка терпения
Объединить сортировки	Идет судьба Каскадная сортировка слиянием Осциллирующая сортировка слиянием Многофазная сортировка слиянием
Виды распределения	сорт американского флага Сортировка бисера Сортировка ведром Пакетная сортировка Подсчет сортировки Интерполяционная сортировка Сортировка по ячейкам Сортировка проксмап Поразрядная сортировка Флэш-сортировка
Параллельные сортировки	Битонический сортировщик Батчерная сортировка слиянием нечет-чет Попарная сортировочная сеть Выборочная сортировка
Гибридные сорта	Блокировать сортировку слиянием Сорт Киркпатрика – Райша Тимсорт Интросорт Спред-сортировка Сортировка слиянием-вставкой
Другой	Топологическая сортировка Предтопологический порядок Сортировка блинов Спагетти сорт
Непрактичные сорта	марионетка сортировка медленная сортировка Богосорт