Proxmap сортировка - Proxmap sort

Proxmap сортировка

Пример вставки сортировки списка случайных чисел.
Учебный класс	Алгоритм сортировки
Структура данных	Множество
Худший случай спектакль	${\displaystyle O(n^{2})}$
Лучший случай спектакль	${\displaystyle O(n)}$
Средний спектакль	${\displaystyle O(n)}$
Худший случай космическая сложность	${\displaystyle O(n)}$

Элементы распределяются по бункерам

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

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

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

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

Обзор

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

В общем: учитывая массив А с п ключи:

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

Упрощенная версия: задан массив А с п ключи

1. Инициализировать: Создать и инициализировать 2 массива п размер: hitCount, proxMapи 2 массива А.длина: место расположения, и A2.
2. Раздел: Использование тщательно подобранного mapKey функция, разделите A2 на подмассивы с помощью ключей в А
3. Рассеивать: Прочитать А, бросая каждый ключ в ведро в A2; вставка сортировки по мере необходимости.
4. Собирать: Посетить подмассивы по порядку и вернуть все элементы в исходный массив или просто использовать A2.

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

Пример

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

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

Таблица массивов

A1	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
L	7	6	10	1	9	4	12	1	5	0	11	7	1
A2	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

Псевдокод

// вычисляем количество обращенийза я = 0 к 11 // где 11 - n{    ЧАС[я] = 0;}за я = 0 к 12 // где 12 - A.length{    позиция = MapKey(А[я]);    ЧАС[позиция] = ЧАС[позиция] + 1;}runningTotal = 0; // вычисляем карту прокси - местоположение начала каждого подмассиваза я = 0 к 11    если ЧАС[я] = 0        п[я] = -9;    еще        п[я] = runningTotal;        runningTotal = runningTotal + ЧАС[я];за я = 0 к 12 // вычисляем местоположение - подмассив - в A2, в которое должен быть помещен каждый элемент в A    L[я] = п[MapKey(А[я])];за я = 0 к 12; // сортируем элементы    A2[я] = <пустой>;за я = 0 к 12 // вставляем каждый элемент в подмассив, начиная с начала, сохраняя порядок{    Начните = L[я]; // подмассив для этого элемента начинается в этом месте    вставка сделали = ложный;    за j = Начните к (<то конец из A2 является найденный, и вставка нет сделали>)    {        если A2[j] == <пустой> // если подмассив пуст, просто поместите элемент в первую позицию подмассива            A2[j] = А[я];            вставка сделали = истинный;        еще если А[я] < A2[j] // ключ принадлежит A2 [j]            int конец = j + 1; // находим конец использованной части подмассива - где первый <пустой>            пока (A2[конец] != <пустой>)                конец++;            за k = конец -1 к j // перемещаем большие клавиши вправо на 1 ячейку                A2[k+1] = A2[k];                A2[j] = А[я];            вставка сделали = истинный; // добавляем новый ключ    }}

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

Поиск в Proxmap

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

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

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

Псевдокод

функция mapKey (ключ) является    возвращаться этаж (ключ)

    proxMap ← ранее сгенерированный массив proxmap размера n A2 ← предварительно отсортированный массив размера nфункция proxmap-search (ключ) является    за i = proxMap [mapKey (ключ)] к длина (массив) - 1 делать        если sortedArray [i] .key == ключ тогда            возвращаться sortedArray [i]

Анализ

Спектакль

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

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

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

Оптимизация

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

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

Множество.прототип.ProxmapSort = функция(){// - Дата редактирования: 2019/11/13 Тайвань - //  вар Начните = 0;  вар конец = это.длина;  вар A2 = новый Множество(конец);  вар MapKey = новый Множество(конец);  вар hitCount = новый Множество(конец);    за (вар я = Начните; я < конец; я++) { hitCount[я] = 0; }  вар мин = это[Начните];  вар Максимум = это[Начните];  за (вар я = Начните+1; я < конец; я++) {    если (это[я] < мин) { мин = это[я]; }    еще {если (это[я] > Максимум) { Максимум = это[я]; }}  }  // Оптимизация 1. Сохраните MapKey [i].  за (вар я = Начните; я < конец; я++) {    MapKey[я] = Математика.этаж(((это[я] - мин ) / (Максимум - мин )) * (конец - 1));    hitCount[MapKey[я]]++;  }  // Оптимизация 2. Сохранение ProxMaps в hitCount.  hitCount[конец-1] = конец - hitCount[конец-1];  за (вар я = конец-1; я > Начните; я--){    hitCount[я-1] = hitCount[я] - hitCount[я-1];  }  // вставляем A [i] = this [i] в ​​правильную позицию A2  вар insertIndex = 0;  вар insertStart = 0;  за (вар я = Начните; я < конец; я++) {    insertIndex = hitCount[MapKey[я]];    insertStart = insertIndex;    пока (A2[insertIndex] != ноль) { insertIndex++; }    пока (insertIndex > insertStart && это[я] < A2[insertIndex-1]) {      A2[insertIndex] = A2[insertIndex-1];      insertIndex--;    }    A2[insertIndex] = это[я];  }  за (вар я = Начните; я < конец; я++) { это[я] = A2[я]; }};

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

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

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

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

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

Рекомендации

1. Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, и Клиффорд Штайн. Введение в алгоритмы, Второе издание. 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). "С помощью О(п) Proxmap Сортировать и О(1) Proxmap Поиск для мотивации студентов CS2 (Часть I) ». Бюллетень ACM SIGCSE. 37 (4). Дои:10.1145/1113847.1113874.
• Стэндиш, Т. А .; Якобсон, Н. (2006). "С помощью О(п) Proxmap Сортировать и О(1) Proxmap Поиск для мотивации студентов CS2, Часть II ». Бюллетень ACM SIGCSE. 38 (2). Дои:10.1145/1138403.1138427.
• Норман Джейкобсон "Краткий обзор ProxmapSort и ProxmapSearch" от Департамента компьютерных наук, Школа информации и компьютерных наук Дональда Брена, Калифорнийский университет в Ирвине.

внешняя ссылка

• http://www.cs.uah.edu/~rcoleman/CS221/Sorting/ProxMapSort.html
• https://web.archive.org/web/20120712094020/http://www.valdosta.edu/~sfares/cs330/cs3410.a.sorting.1998.fa.html
• https://web.archive.org/web/20120314220616/http://www.cs.uml.edu/~giam/91.102/Demos/ProxMapSort/ProxMapSort.c