- PVSM.RU - https://www.pvsm.ru -
Слева — mergeSort, справа — родная сортировка. PepperFlash и 75 миллионов элементов.
Что бы понять эту сортировку, нужно понять три принципа:
Процедура слияния вырезает наименьший из первых элементов двух входных массивов и вставляет в конец результирующего массива, пока один из входных массивов не станет пустым. После этого остатки непустого массива просто копируются в конец результирующего массива.
Что бы достаточно хорошо понять алгоритм — надо его реализовать.
У меня получилось так:
function mergeSort(array:Array):Array {
var chunkSize:int = array.length / 2;
if(chunkSize >= 1){
var left:Array = mergeSort(array.slice(0, chunkSize));
var right:Array = mergeSort(array.slice(chunkSize));
var result:Array = [];
while(left.length && right.length){
if(left[0] < right[0]){
result.push(left.shift());
} else{
result.push(right.shift());
}
}
return result.concat(left, right);
}
return array;
}
На самом деле, даже такая реализация быстрее некоторых, найденных мною во всяких блогах.
Рекурсивно, сортируются сначала первые элементы. То есть 0 и 1, потом 2 и 3, потом 0..1 и 2..3 сливаются в один массив 0..3, и только после 4 и 5.
(число перед открывающей скобкой — приоритет)
6{ _3_[ 1(1, 2), 2(3, 4) ], 5[ _4_(5, 6) ] }
Но можно отсортировать все подмассивы из одного элемента, и потом их сливать в подмассивы из 4 элементов.
6{ _4_[ 1(1, 2), 2(3, 4) ], 5[ _3_(5, 6) ] }
Это позволяет избавится от рекурсии.
Процедура слияния может работать напрямую с сортируемым массивом. Нет нужды передавать ей массивы, когда можно передать исходный массив и координаты сливаемых подмассивов. Но она не может записывать изменения сразу в исходный массив(например, если все элементы второго подмассива меньше всех элементов первого, то процедура попортит первый подмассив), ей нужен т.н. буфер, что бы запомнить изменения, не испортив при этом входные данные. По окончанию своей работы процедура копирует изменения из буфера в исходный массив.
Т.к. результат слияния размером равен сумме размеров двух входных подмассивов, можно записывать результат в буфер, начиная с индекса первого элемента первого массива. Это позволит выделить всего один буфер, размером с исходный массив, и не копировать каждый раз результат слияния в исходный массив.
Короче, рисуем сову:
function mergeSort(array:Vector.<int>):Vector.<int> {
var length:uint = array.length;
var buffer:Vector.<int> = new Vector.<int>(length, true);
for (var leftChunkSize:uint = 1; leftChunkSize < length; leftChunkSize *= 2) { // low
var bufferPointer:uint = 0;
var leftChunkStart:uint = 0;
for (; leftChunkStart < length; leftChunkStart += leftChunkSize * 2) { // mid
var rightChunkStart:uint = Math.min(leftChunkStart + leftChunkSize, length);
var rightChunkEnd:uint = Math.min(rightChunkStart + leftChunkSize, length);
var leftChunkEnd:uint = rightChunkStart;
var leftPointer:uint = leftChunkStart;
var rightPointer:uint = rightChunkStart;
while (leftPointer < leftChunkEnd && rightPointer < rightChunkEnd) { // hard
if (array[leftPointer] < array[rightPointer]) {
buffer[bufferPointer++] = array[leftPointer++];
}else {
buffer[bufferPointer++] = array[rightPointer++];
}
}
while (leftPointer < leftChunkEnd) { // hard
buffer[bufferPointer++] = array[leftPointer++];
}
while (rightPointer < rightChunkEnd) { // hard
buffer[bufferPointer++] = array[rightPointer++];
}
}
var temp:Vector.<int> = array;
array = buffer;
buffer = temp;
}
if (result !== array) {
for (var i:uint = 0; i < length; i++ ) {
result[i] = array[i];
}
}
return result;
}
В комментариях обозначены узкие места.
Конфигурация ПК: DDR3-1066 2GB, P6200 (2x2.13GHz).
(«FP» читать как «FlashPlayerDebugger 11.9.900.170», release)
FP | PepperFlash | |
200 000 элементов | ||
mergeSort | 160мс | 81мс |
Родная сортировка | 81мс | 90мс |
2 000 000 элементов | ||
mergeSort | 1800мс | 921мс |
Родная сортировка | 1378мс | 1425мс |
20 000 000 элементов | ||
mergeSort | 21374мс | 10267мс |
Родная сортировка | 20404мс | 21175мс |
Теперь немного оптимизируем узкие места:
Получаем:
function mergeSort(array:Vector.<int>, buffer:Vector.<int> = null):Vector.<int> {
var length:uint = array.length;
var result:Vector.<int> = array;
buffer = buffer ? buffer : new Vector.<int>(length, true);
for (var chunkSize:uint = 1; chunkSize < length; chunkSize <<= 1) {
var bufferPointer:uint = 0;
var leftChunkStart:uint = 0;
for (; leftChunkStart < length; leftChunkStart += chunkSize << 1) {
var rightChunkStart:uint = leftChunkStart + chunkSize;
var rightChunkEnd:uint = rightChunkStart + chunkSize;
if (length < rightChunkEnd) {
rightChunkEnd = length;
if (length < rightChunkStart) {
rightChunkStart = length;
}
}
var leftChunkEnd:uint = rightChunkStart;
var leftPointer:uint = leftChunkStart;
var rightPointer:uint = rightChunkStart;
while (leftPointer - leftChunkEnd & rightPointer - rightChunkEnd) {
if (array[leftPointer] < array[rightPointer]) {
buffer[bufferPointer++] = array[leftPointer++];
}else {
buffer[bufferPointer++] = array[rightPointer++];
}
}
while (leftPointer < leftChunkEnd) {
buffer[bufferPointer++] = array[leftPointer++];
}
while (rightPointer < rightChunkEnd) {
buffer[bufferPointer++] = array[rightPointer++];
}
}
var temp:Vector.<int> = array;
array = buffer;
buffer = temp;
}
if (result !== array) {
for (var i:uint = 0; i < length; i++ ) {
result[i] = array[i];
}
}
return result;
}
10^8 элементов такая реализация у меня сортирует за 47 секунд в PepperFlash.
FP | PepperFlash | |
200 000 элементов | ||
mergeSort | 130мс | 64мс |
Родная сортировка | 81мс | 90мс |
2 000 000 элементов | ||
mergeSort | 1462мс | 730мс |
Родная сортировка | 1378мс | 1425мс |
20 000 000 элементов | ||
mergeSort | 16937мс | 8435мс |
Родная сортировка | 20404мс | 21175мс |
200 элементов и 1000 сортировок |
||
mergeSort | 88мс | 38мс |
Родная сортировка | 70мс | 48мс |
Создание массива с случайными элементами |
36мс | 10мс |
2000 элементов и 10000 сортировок |
||
mergeSort | 10077мс | 4809мс |
Родная сортировка | 6885мс | 5912мс |
Создание массива с случайными элементами |
2178мс | 760мс |
в случае с полностью отсортированными массивами, обе сортировки работают быстрее(например, при 2 000 000 элементах примерно на 30% быстрее, обе).
Родная сортировка требует примерно n*1.5 дополнительной памяти, mergeSort — ровно n.
В итоге, в FP профита от этих телодвижений мало. А вот в PepperFlash можно наблюдать цифры чуть ли не в двое меньше.
Автор: nubideus
Источник [1]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/51850
Ссылки в тексте:
[1] Источник: http://habrahabr.ru/post/207784/
Нажмите здесь для печати.