Pull to refresh

Merge sort и AS3. Обгоняем родной Vector.sort(Array.NUMERIC)

Reading time 4 min
Views 10K

Слева — 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мс


Теперь немного оптимизируем узкие места:
  • Math.min намного медленнее, чем простыми условиями.
  • Побитовый сдвиг быстрее умножения и деления на 2.
  • Еще можно вспомнить, что на самом деле делает &&, и избавится от него.

Получаем:
Код
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 можно наблюдать цифры чуть ли не в двое меньше.
Tags:
Hubs:
+5
Comments 12
Comments Comments 12

Articles