|
|
|||||
Ну файл-то может и попадает, а алгоритм - это просто порядок действий) Его можно понять и просто использовать у себя подобный ему.
Ну не может же не найтись людей, которые додумались бы до одного и того же порядка действий, самого оптимального?
__________________
There is no thing in this world that is not simple. |
|
|||||
Banned
[+4 24.02.14]
[+4 07.11.13] [+ 13.03.14] Регистрация: Mar 2013
Сообщений: 1,864
|
Цитата:
|
|
|||||
По-моему в процессе была потеряна задача. Задачей, насколько я понял, являлось обучение. Лучшее возможное обучение - это собственноручная реализация алгоритма по описанию или по псевдокоду (и то, и другое с википедии, например). Зачем в процессе писать самую быструю реализацию? - мне не ясно. Пишите ее когда она Вам нужна. В моем понимании "нужна" - это когда данных ооочень много или когда сортировок очень много за единицу времени. Во всех остальных случаях - не "нужна", а просто трата времени в отрыве от задачи. GTD. Getting Things Done. Ставьте цель. Добивайтесь. Идите дальше.
__________________
...вселенская грусть |
|
|||||
Статья мутная, тестов товарищ так и не привел, только результаты (непонятно как полученные). И есть подозрение, что тестировал он дебаговый swf (еще и в дебаговом плеере).
__________________
משיח לא בא משיח גם לא מטלפן |
|
|||||
Цитата:
|
|
|||||
Banned
[+4 24.02.14]
[+4 07.11.13] [+ 13.03.14] Регистрация: Mar 2013
Сообщений: 1,864
|
Цитата:
И вот какой момент, все говорят, что этот код фигня, но предположим, мне нужно отсортировать объекты по свойствам. Как это сделать? 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; } } } |
|
|||||
listener
|
Мои результаты таковы:
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; } } } Цитата:
Выводы предлагается сделать самостоятельно. Последний раз редактировалось alexcon314; 23.04.2014 в 22:34. |
|
|||||
Banned
[+4 24.02.14]
[+4 07.11.13] [+ 13.03.14] Регистрация: Mar 2013
Сообщений: 1,864
|
Цитата:
тем более, что он тоже Ваш. И вот какие результаты, только между тиками - Цитата:
как обратил внимание на одну маленькую деталь. У Вас метод test вызывается десять раз, который в свою очередь вызывает метод nativeTest или mergeTest, в которых в свою очередь в цикле вызывается сортируемый метод. И вот тут оно самое - в цикле вызывается тоже десять раз, а координаты задаются только для каждого десятого вызова из метода test. То есть получается, что методы сортирую девять раз из десяти уже отсортированные массивы. И в сортировки уже отсортированного, выигрывает нативный, а вот при сортировке не сортированного - с хабра. Добавлено через 4 минуты По этому, если я не ошибся, то алгоритм-то хороший, только, как Вы сказали, памяти в два раза больше берет. я не знаю как память мерить и было бы интересно узнать её объем при сортировке не отсортированного. Добавлено через 11 минут Вот правильный замер - Цитата:
В четыре раза быстрей. Если судить по времени сортировки не сортированного и сортированного, то складывается впечатление, что в Array есть либо флаг "меня не изменяли" либо "сомневаюсь, что меня изменяли и я перехожу на более быстрый алгорит для частично отсортированного массива". Последний раз редактировалось Akopalipsis; 23.04.2014 в 23:17. |
Часовой пояс GMT +4, время: 20:22. |
|
« Предыдущая тема | Следующая тема » |
|
|