Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Регистрация Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Блоги > Aquahawk

Рейтинг: 5.00. Голосов: 2.

Сортируем 300 000 Number быстро, ещё быстрее.

Запись от Aquahawk размещена 11.06.2011 в 14:57
Обновил(-а) Aquahawk 11.06.2011 в 15:32

Стандартный sort у Vector весьма тормозен, также осуществляет вызов функции на каждом сравнении, что не есть гуд. Эту сортировку можно оптимизировать как алгоритмически, так и просто ускорить итерацию. Тов. geser опубликовал заметку о том как можно сделать не только быструю сортировку слиянием, но и вынести самые последние часты итерации в шейдер. Почитать можно у нас, на someideas.ru там же есть исходники и проект FD. На моей машине(C2D@3.6Ghz, GTS250) стандартная сортировка занимает 2389 миллисекунд, ручная реализация слияния без шейдера 137 и с шейдером 121 соответственно. При этом прирост наблюдается и на атомном нетбуке.
Всего комментариев 10

Комментарии

Старый 12.06.2011 11:31 i.o. вне форума
i.o.
 
Аватар для i.o.
Зато Array.sort не такой уж медленный:
Цитата:
this._srcAsArray.length: 300000
bubble: 2282
without shader: 199
with shader: 185
shader time: 7
Array.NUMERIC time: 282
Код AS3:
private function onEnterFrame(e:Event):void 
{
	if ((mySort.Ready)&&(mySortopt.Ready))
	{
		t1 = getTimer();
		dst = mySort.Sort();
		t2 = getTimer();
		myTime = t2 - t1;
		trace ("my sort = ", myTime);
 
		t1 = getTimer();
		dst = mySortopt.Sort();
		t2 = getTimer();
		trace ("my sort opt = ", t2 - t1);
 
		stage.removeEventListener(Event.ENTER_FRAME, onEnterFrame);
		addChild(text);
		text.width = 300;
		text.height = 300;
		text.appendText("\n bubble: " + bubble.toString());
		text.appendText("\n without shader: " + myTime.toString());
		text.appendText("\n with shader: " + (t2 - t1).toString());
		text.appendText("\n shader time: " + mySortopt.time.toString());
 
		t1 = getTimer();
		this._srcAsArray.sort(Array.NUMERIC);
		t2 = getTimer();
		myTime = t2 - t1;
		text.appendText("\n Array.NUMERIC time: " + myTime.toString());
	}
}
Старый 12.06.2011 13:00 Aquahawk вне форума
Aquahawk
 
Аватар для Aquahawk
Никогда не смотрел на array в качастве коллекции и думал что vector его везде рвёт. В документации к Array указано
Цитата:
The default behavior of the sort() function is to handle each entity as a string. If you use the Array.NUMERIC argument, the Flash runtime attempts to convert any non-numeric values to integers for sorting purposes.
Однако сортирует при этом верно. Проверил на числах из диапазона [0;1].
Старый 12.06.2011 13:51 f.g.programmer вне форума
f.g.programmer
 
Аватар для f.g.programmer
Стандартная сортировка работает гораздо быстрее, если использовать нормальный метод, а не замыкание
Код AS3:
src.sort(compareNumbers);
private function compareNumbers(x:Number, y:Number):Number { 
	return (x <= y) ? -1 : 1;
}
Но всё равно медленнее шейдерной сортировки, и сортировки на Array.NUMERIC
Старый 12.06.2011 15:12 alatar вне форума
alatar
 
Аватар для alatar
А если сделать совсем нормально и возвращать еще и 0, то будет еще быстрее.
Старый 12.06.2011 16:08 Aquahawk вне форума
Aquahawk
 
Аватар для Aquahawk
Потестил, вот такая конструкция ускорилась против замыкания почти в 4 раза.
Код AS3:
private function comp(x:Number, y:Number):int{
	if (x < y){
		return -1;
	}else{
		if (x == y){
			return 0;
		}else{
			return 1;
		}
	}
}
На моей машине стало 580 а было 2389
Старый 12.06.2011 17:32 i.o. вне форума
i.o.
 
Аватар для i.o.
Цитата:
bubble
Кстати, нативная сортировка не пузырьком. Там используется QuickSort.
Старый 12.06.2011 18:07 fish_r вне форума
fish_r
 
Аватар для fish_r
@Aquahawk. Добавьте ещё один знак "=" в сравнение (чтобы получилось "===") будет ещё быстрее
Старый 12.06.2011 19:01 Aquahawk вне форума
Aquahawk
 
Аватар для Aquahawk
действительно, очень небольшой но прирост есть.
Старый 12.06.2011 19:06 fish_r вне форума
fish_r
 
Аватар для fish_r
да, тут на форуме уже тестили это момент (со знаком сравнения), поэтому всегда стараюсь ставить "===" вместо "==", когда это возможно, конечно.
Старый 17.06.2011 12:45 nuToH вне форума
nuToH
 
Аватар для nuToH
мой вариант реализации сортировки:

Код AS3:
var a:Vector.<Number> = new Vector.<Number>();
 
for (var i:int = 0; i < 300000; i++) {
	a.push(Math.random());
}
 
 
function sort(left:int, right:int):void {
	var i:int = left;
	var j:int = right;
	var middle:int = i + j >> 1;
	var x:Number = a[middle];
	while (i <= j) {
		var ai:Number = a[i];
		var aj:Number = a[j];
		while (ai < x) ai = a[++i];
		while (aj > x) aj = a[--j];
		if (i <= j) {
			a[i++] = aj;
			a[j--] = ai;
		}
	}
	if (left < j) sort(left, j);
	if (i < right) sort(i, right);
}
 
function comp(x:Number, y:Number):int{
	if (x < y){
		return -1;
	}else{
		if (x === y){
			return 0;
		}else{
			return 1;
		}
	}
}
 
var t:Number = new Date() .time;
sort(0, a.length - 1);// 101 ms
//a.sort(comp);//525
trace(String(new Date() .time - t));
Обновил(-а) nuToH 17.06.2011 в 14:58
 

 


Часовой пояс GMT +4, время: 16:25.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2020, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.