Узкая функция сортировки

Question

Я пытаюсь отсортировать большой массив с помощью Actionscript 3.

Проблема в том, что мне приходится использовать пользовательскую функцию сортировки, которая мучительно медленная и приводит к краху флэш-плагина.

Ниже приведен пример кода для пользовательской функции, используемой для сортировки массива по длине его членов:

            private function sortByLength():int {
                var x:int = arguments[0].length;
                var y:int = arguments[1].length;
                if (x > y){
                    return 1;                       
                }else if (x < y){
                    return -1;
                }else{
                    return 0;
                }
             }

Что называется так:

    var txt:Array = ["abcde","ab","abc","a"];
    txt.sort(sortByLength);

---

Посоветуйте, пожалуйста, как это можно сделать быстрее?

Как изменить логику приложения, чтобы избежать сбоев плагина Flash во время сортировки?

Answer 1

старайтесь использовать строгую типизацию всякий раз, когда это возможно, здесь скажите вашей функции, что вы ждете две строки.

вы можете переписать вашу функцию двумя способами, один быстрее, чем другой, если вы знаете, что все ваши элементы не являютсяNULL:

function sortByLength(a:String, b:String):int {
    return a.length-b.length // fastest way not comparison
}

и если вы можете иметь нулевую проверку для этого (этот будет поставить NULL перед всем элементом):

 function sortByLengthWithNull(a:String, b:String):int {
     if (a==null) return -1
     if (b==null) return 1
     return a.length-b.length
 }

Answer 2

Если вам нужна супербыстрая сортировка, то, возможно, стоит вообще не использовать массив, а вместо этого использовать связанный список. Есть разные преимущества для каждого. Прежде всего, при использовании связанного списка доступ к индексу происходит медленно, хотя итерация по списку происходит быстро, а связанные списки не являются родными для AS3, поэтому вам придется свернуть свой собственный.

С другой стороны, вы можете использовать код Polygonal Labs: http://lab.polygonal.de/as3ds/.

Сортировка очень, очень быстрая для почти отсортированных данных со связанным списком, как обсуждается в этой статье: http://lab.polygonal.de/2007/11/26/data-structures-more-on-linked-lists/.

Это решение дает вам гораздо больше работы, но в конечном итоге также даст вам большую скорость сортировки.

Надеюсь, это поможет.

- дополнительно -

Я заметил ваш вопрос в комментариях к другому ответу о том, что "Один вопрос, однако, остается без ответа - как выполнять жадные вычисления во Flash, не вешая его?"

Для этого, по сути, ответ состоит в том, чтобы разбить ваши вычисления на несколько кадров, что-то вроде этого:

public function sort():void
{
    addEventListener(Event.ENTER_FRAME, iterateSort);
}

private function iterateSort():void
{
    var time:int = getTimer() + TARGET_MILLISECONDS_PER_FRAME;
    var isFinished:Boolean = false;

    while (!isFinished && getTimer() < time)
        isFinished = continueSort();

    if (isFinished)
        removeEventListener(Event.ENTER_FRAME, iterateSort);
}

function continueSort():Boolean
{
    ... implement an 'atom of sort' here, whatever that means ...
}

Answer 3

sortByLength должно иметь два параметра, не так ли?Я думаю, это то, что вы имеете в виду под массивом arguments ...

Это выглядит хорошо для меня, если arguments не локальная переменная, а переменная-член, а вы просто смотрите наего элементы [0] и [1] при каждом вызове функции.Это, по крайней мере, приведет к нежелательным результатам.