Быстрый алгоритм сортировки.

[ZackMercury]

Ну файл-то может и попадает, а алгоритм - это просто порядок действий) Его можно понять и просто использовать у себя подобный ему.

Ну не может же не найтись людей, которые додумались бы до одного и того же порядка действий, самого оптимального?

[Akopalipsis]

Ради интереса, можно ли взглянуть, что за алгоритм такой необычный? Хотелось бы разобраться.

Merge sort.

[alexcon314]

В итоге, в FP профита от этих телодвижений мало. А вот в PepperFlash можно наблюдать цифры чуть ли не в двое меньше.

Однако. Есть за что биться.

[gloomyBrain]

По-моему в процессе была потеряна задача. Задачей, насколько я понял, являлось обучение. Лучшее возможное обучение - это собственноручная реализация алгоритма по описанию или по псевдокоду (и то, и другое с википедии, например). Зачем в процессе писать самую быструю реализацию? - мне не ясно. Пишите ее когда она Вам нужна. В моем понимании "нужна" - это когда данных ооочень много или когда сортировок очень много за единицу времени. Во всех остальных случаях - не "нужна", а просто трата времени в отрыве от задачи. GTD. Getting Things Done. Ставьте цель. Добивайтесь. Идите дальше.

[alatar]

Сообщение от alexcon314

Однако. Есть за что биться.

Статья мутная, тестов товарищ так и не привел, только результаты (непонятно как полученные). И есть подозрение, что тестировал он дебаговый swf (еще и в дебаговом плеере).

[alexcon314]

alatar, я о том же, это был хорошо замаскированный сарказм ).
Akopalipsis, меня вы уже традиционно не слушаете, так хоть людей послушайте.

[caseyryan]

Сообщение от Akopalipsis

Merge sort.

Вряд ли эта шняга когда-то пригодится в реальности

[Akopalipsis]

Akopalipsis, меня вы уже традиционно не слушаете, так хоть людей послушайте.

Вы не представляете, на сколько я дружелюбный человек и только по этому я повторюсь - у меня нет поводов Вас не слушать!! Хоть Вы меня и банили и почти в каждом сообщении говорите, что я после года обучения глупее Вас, который, как я понял из соседней ветки, в два раза старше меня... Нет! Это не в моей глупости дело и не в моём желании быстрее все узнать, это в Вас дело. Это Вы думаете, что все должно быть как у Вас. Так что я Вас внимательно слушаю и не пропускаю слов мимо. Бывает правда, что я не понимаю ответа и настаиваю. Вот как в этом случае - Вы несколько раз закрывали тему о коллекциях, в которых я хотел получить ответы на ВСЕ вопросы касающихся этой темы. я так и не понял, используют их или нет и по этому так и стал ковыряться в них дальше. И читал о всех алгоритмах на вики и на кодовики и на хабре и сидел и две с половиной недели экспериментировал. И вот пришло время, когда я попробовал и понял все из найденного и самое то, было бы выбрать лучшее. И вот я здесь.

И вот какой момент, все говорят, что этот код фигня, но предположим, мне нужно отсортировать объекты по свойствам. Как это сделать? sortOn делает это за 7500 секунд для 100000 объектов, а этот код за 600 с компаратором и 300 без. Тогда поделитесь пожалуйста, как Вы делаете сортировку свойств быстрее чем за 300 милисекунд?

Добавлено через 23 минуты
Жутко извиняюсь извиняюсь, провел тест не свойство..
Почти 1700 с компаратором и 1400 без. Но все равно не 7500.

Добавлено через 24 минуты

package 
{
	import flash.display.Sprite;
	import flash.events.TimerEvent;
	import flash.text.TextField;
	import flash.text.TextFieldAutoSize;
	import flash.utils.getTimer;
	import flash.utils.Timer;
 
	public class SpeedTest extends Sprite 
	{
		private const N:int = 10000000;
		private const D:int = 5000;
		private const C:int = 100;
 
		private var delay:int = 2;
		private var repeat:int = 5;
		private var runtime:Number;
		private static var _textField:TextField;
		private var _temer:Timer;
 
		public function SpeedTest() 
		{
			_textField = new TextField();
			_textField.autoSize = TextFieldAutoSize.LEFT;
			super.addChild(_textField);
			_temer = new Timer(delay, repeat);
			_temer.addEventListener(TimerEvent.TIMER, temer_timerHandler);
			_temer.start();
		}
 
		private function temer_timerHandler(event:TimerEvent):void 
		{
			this.speed();
			_textField.appendText("Прошло время - " + runtime + "\n");
		}
		public  var a:* = random();
		public var b:* = random()
		private function speed():void
		{
			var i:int;
			var t:Number;
 
			var array:Array = [];
			var sprite:Sprite
 
			for (var j:int = 0; j < 100000; j++) 
			{
				sprite = new Sprite();
				sprite.x = roundRandom();
				array[j] = sprite;
			}
 
			for (i = 0, t = getTimer(); i < 1; i++)
			{
				defaultSort(array, this.comparator);
				//array.sortOn('x', Array.NUMERIC);
			}
			runtime = getTimer();
			runtime -= t;
		}
		private function defaultSort(array:Array, companator:Function):void
		{
			var length:int = array.length;
 
			var result:Array = array;
			var buffer:Array = new Array(length);
			var temp:Array;
 
			var bufferPointer:uint;
			var leftPointer:int;
			var rightPointer:int;
 
			var sectionSize:int = 1;
 
			var leftSectionStart:uint;
			var leftSectionFinish:uint;
 
			var rightSectionStart:uint;
			var rightSectionFinish:uint;
 
			while (sectionSize < length)
			{
				bufferPointer = 0;
				leftSectionStart = 0;
 
				while (leftSectionStart < length)
				{
					rightSectionStart = leftSectionStart + sectionSize;
					rightSectionFinish = rightSectionStart + sectionSize;
 
					if (length < rightSectionFinish)
					{
						rightSectionFinish = length;
 
						if (length < rightSectionStart)
								rightSectionStart = length;
					}
 
					leftSectionFinish = rightSectionStart;
 
					leftPointer = leftSectionStart;
					rightPointer = rightSectionStart;
 
					while (leftPointer - leftSectionFinish & rightPointer - rightSectionFinish)
					{
						if (companator(array[leftPointer], array[rightPointer]) == -1)
								buffer[bufferPointer++] = array[leftPointer++];
						else
								buffer[bufferPointer++] = array[rightPointer++];
					}
 
					while (leftPointer < leftSectionFinish)
							buffer[bufferPointer++] = array[leftPointer++];
 
					while (rightPointer < rightSectionFinish)
							buffer[bufferPointer++] = array[rightPointer++];
 
					leftSectionStart += sectionSize << 1;
				}
 
				temp = array;
				array = buffer;
				buffer = temp;
 
				sectionSize <<= 1;
			}
 
			if (result !== array)
			{
				var i:int;
				while (i < length)
						result[i] = array[i++];
			}
		}
		private function comparator(a:Sprite, b:Sprite):int
		{
			if (a.x < b.x) return -1;
			if (a.x > b.x) return 1;
			return 0;
		}
		private function roundRandom():int
		{
			return Math.random() * 10;
		}
		private static function random():Number
		{
			return Math.random() * 10;
		}
 
	}
 
}

[alexcon314]

Мои результаты таковы:

package 
{
	import flash.display.Sprite;
	import flash.events.TimerEvent;
	import flash.text.TextField;
	import flash.text.TextFieldAutoSize;
	import flash.utils.getTimer;
	import flash.utils.Timer;
 
 
	public class Main extends Sprite 
	{
		private const N:int = 10;
		private const D:int = 1000;
		private const C:int = 1;
		private var timer:Timer;
		private var tf:TextField = new TextField();
		private var store:int = 0;
		private var array:Array = [];
		public function Main() 
		{
 
			var sprite:Sprite; 
			for (var j:int = 0; j < 100000; j++) 
			{
				sprite = new Sprite();
				array[j] = sprite;
			} 
			tf.autoSize = TextFieldAutoSize.LEFT;
			addChild(tf);
			timer = new Timer(D, C);
			timer.addEventListener(TimerEvent.TIMER, test);
			timer.addEventListener(TimerEvent.TIMER_COMPLETE, result);
			timer.start();
		}
 
		private function result(e:TimerEvent):void {	
			tf.appendText( "\ntime (avg): " + store / C);
			timer.stop();
		}
		private function test(e:TimerEvent):void 
		{	
			tf.text = "Current tick: " + timer.currentCount;
			//nativeTest();
			mergeTest();
		}
		private function shuffleArray():void
		{
			var sprite:Sprite; 
			for (var j:int = 0; j < 100000; j++) 
			{
				(array[j] as Sprite).x = roundRandom();
			} 
		}
		private function nativeTest():void
		{
			var i:int;
			var t:Number;
 
			for (i = 0, t = getTimer(); i < N; i++) { shuffleArray(); array.sortOn('x', Array.NUMERIC);}
			store += (getTimer() - t);
 
		}
 
		private function mergeTest():void
		{
 
			var i:int;
			var t:Number;
 
			for (i = 0, t = getTimer(); i < N; i++){ shuffleArray();defaultSort(array, comparator);}
			store += (getTimer() - t);
 
 
		} 
		private function defaultSort(array:Array, companator:Function):void
		{
			var length:int = array.length;
 
			var result:Array = array;
			var buffer:Array = new Array(length);
			var temp:Array;
 
			var bufferPointer:uint;
			var leftPointer:int;
			var rightPointer:int;
 
			var sectionSize:int = 1;
 
			var leftSectionStart:uint;
			var leftSectionFinish:uint;
 
			var rightSectionStart:uint;
			var rightSectionFinish:uint;
 
			while (sectionSize < length)
			{
				bufferPointer = 0;
				leftSectionStart = 0;
 
				while (leftSectionStart < length)
				{
					rightSectionStart = leftSectionStart + sectionSize;
					rightSectionFinish = rightSectionStart + sectionSize;
 
					if (length < rightSectionFinish)
					{
						rightSectionFinish = length;
 
						if (length < rightSectionStart)
								rightSectionStart = length;
					}
 
					leftSectionFinish = rightSectionStart;
 
					leftPointer = leftSectionStart;
					rightPointer = rightSectionStart;
 
					while (leftPointer - leftSectionFinish & rightPointer - rightSectionFinish)
					{
						if (companator(array[leftPointer], array[rightPointer]) == -1)
								buffer[bufferPointer++] = array[leftPointer++];
						else
								buffer[bufferPointer++] = array[rightPointer++];
					}
 
					while (leftPointer < leftSectionFinish)
							buffer[bufferPointer++] = array[leftPointer++];
 
					while (rightPointer < rightSectionFinish)
							buffer[bufferPointer++] = array[rightPointer++];
 
					leftSectionStart += sectionSize << 1;
				}
 
				temp = array;
				array = buffer;
				buffer = temp;
 
				sectionSize <<= 1;
			}
 
			if (result !== array)
			{
				var i:int;
				while (i < length)
						result[i] = array[i++];
			}
		}
		private function comparator(a:Sprite, b:Sprite):int
		{
			if (a.x < b.x) return -1;
			if (a.x > b.x) return 1;
			return 0;
		}
		private function roundRandom():int
		{
			return Math.random() * 10;
		}
		private static function random():Number
		{
			return Math.random() * 10;
		}
 
	}
}

//FP 11.7 release
//Flex 4.6 FD 4.4.3
//Build: Release
//Win 7 Pro x64 Core i3 6Gb
//N = 10, D = 1000, C = 10

//nativeTest (84 Mb )
Current tick: 10
time (avg): 20432.2

//mergeTest (132 Mb)
Current tick: 10
time (avg): 7483.9

Память взята в диспетчере задач после выполнения тестов.
Выводы предлагается сделать самостоятельно.

[Akopalipsis]

Слабый ноут -

//nativeTest
Current tick: 10
time (avg): 9423.6

//mergeTest
Current tick: 10
time (avg): 17794.5

И меня такие результаты, как холодной водой окатили и я начал делать опять свой тест,
тем более, что он тоже Ваш. И вот какие результаты, только между тиками -

//nativeTest
Прошло время - 7697
Прошло время - 7033
Прошло время - 7214
Прошло время - 8071
Прошло время - 7539
Прошло время - 6311
Прошло время - 6843
Прошло время - 7281
Прошло время - 6867
Прошло время - 7328

//mergeTest
Прошло время - 1880
Прошло время - 1880
Прошло время - 1877
Прошло время - 1860
Прошло время - 1894
Прошло время - 1870
Прошло время - 1860
Прошло время - 1854
Прошло время - 1860
Прошло время - 1859

И тут сразу вопрос - ну как же так!! И я только хотел искать у себя ошибку в классе,
как обратил внимание на одну маленькую деталь. У Вас метод test вызывается десять раз, который в свою очередь вызывает метод nativeTest или mergeTest, в которых в свою очередь в цикле вызывается сортируемый метод. И вот тут оно самое - в цикле вызывается тоже десять раз, а координаты задаются только для каждого десятого вызова из метода test. То есть получается, что методы сортирую девять раз из десяти уже отсортированные массивы. И в сортировки уже отсортированного, выигрывает нативный, а вот при сортировке не сортированного - с хабра.

Добавлено через 4 минуты
По этому, если я не ошибся, то алгоритм-то хороший, только, как Вы сказали, памяти в два раза больше берет. я не знаю как память мерить и было бы интересно узнать её объем при сортировке не отсортированного.

Добавлено через 11 минут
Вот правильный замер -

//nativeTest
Current tick: 10
time (avg): 8011.7
scout memory - 60 000 KB

//mergeTest
Current tick: 10
time (avg): 2271.3
scout memory - 65 000 KB

Добавлено через 12 минут
В четыре раза быстрей.
Если судить по времени сортировки не сортированного и сортированного, то складывается впечатление,
что в Array есть либо флаг "меня не изменяли" либо "сомневаюсь, что меня изменяли и я перехожу на более быстрый алгорит для частично отсортированного массива".