ActionScript 3 Vector сортировка вдруг очень медленно?

Question

Играя с as 'vector.sort (), я обнаружил, что он ведет себя нормально в каждом случае, кроме случаев, когда ему нужно отсортировать вектор только с 2 или 3 отличительными значениями. Если это так, функция sort () работает крайне медленно. Вот мой код:

var test:Vector.<int>=new Vector.<int>  ;
for (var i:int=0; i<6000; i++) {
    test.push(Math.floor(Math.random()*2));
}
var timer:Number
var timer2:Number
timer=new Date().getTime();
test.sort(compare)
timer2=new Date().getTime();
trace(timer2-timer)
function compare(x:int,y:int):Number {
    if (x>y) {
        return 1;
    } else if (x<y) {
        return -1;
    } else {
        return 0;
    }
}

просто скопируйте этот код. В чем может быть проблема здесь? спасибо.

Answer 1

Я только что столкнулся с этой же проблемой: Vector.sort () из 50000 объектов-значений в поле с тремя различными значениями: ~ 2 минуты.Затем я вызываю почти точно такую ​​же сортировку, с той лишь разницей, что я разрываю связь (когда x == y) для вторичного поля с уникальным значением (то есть для поля с 50000 различными значениями): меньшечем 1 сек!Вот код функции сортировки, чтобы проиллюстрировать, что я имею в виду:

private function vastlyImprovedVectorSortFunc(x:MyVO, y:MyVO):Number
{
    if(x.fieldWithThreeValues > y.fieldWithThreeValues)
        return 1;
    else
        if(x.fieldWithThreeValues < y.fieldWithThreeValues )
            return -1;
        else
            if(x.uniqueFieldWithManyValues > y.uniqueFieldWithManyValues)
                return 1;
            else
                if(x.uniqueFieldWithManyValues < y.uniqueFieldWithManyValues )
                    return -1;
                else
                    return 0;
}

Мир Bizarro, верно ?!Похоже, я прошу функцию проделать гораздо больше работы, применяя вторичную сортировку к очень уникальному полю - но, очевидно, производительность функции сортировки Vector ухудшается с меньшим количеством отдельных «корзин» сортировки, в которые можно помещать вещи.Я обнаружил это, когда сортировал свой вектор на fieldWithAboutTwentyValues, и производительность по-прежнему была плохой (~ 20 секунд), но значительно улучшилась.Тогда было еще лучше на поле WithAboutAHundredValues;поэтому я подумал, почему бы не пойти на все и просто сделать окончательную сортировку по (уникальному) первичному ключу.

Изменит правила игры для меня!Надеюсь, это поможет кому-то еще.Удивил, что это не где-то в документах.

Answer 2

На самом деле это не происходит с 2 или 3 значениями, точнее, эффект тем заметнее, чем меньше различных значений в векторе. У каждого алгоритма сортировки есть свои плюсы и минусы. Встроенный (я думаю, это пузырьковая сортировка) будет работать почти в худшем случае, когда существует несколько различных значений. Вы можете попробовать эту простую альтернативу (сортировку по основанию), но обратите внимание, что она будет иметь больший объем памяти, и чем больше, тем более отчетливыми будут значения в векторе.

package examples 
{
import flash.display.Sprite;

/**
 * An example for stackoverflow.com
 * @author wvxvw
 */
public class KindOfRadixSort extends Sprite
{

    public function KindOfRadixSort() 
    {
        super();
        this.test();
    }

    private function test():void
    {
        var test:Vector.<int> = new <int>[];
        var timer:Number;
        var timer2:Number;

        for (var i:int; i < 6000; i++) test.push(Math.random() * 5);

        timer = new Date().getTime();
        test.sort(compare);
        timer2 = new Date().getTime();
        trace(timer2 - timer); // 2488

        timer = new Date().getTime();
        this.kindOfRadixSort(test);
        timer2 = new Date().getTime();
        trace(timer2 - timer); // 3
    }

    private function compare(x:int, y:int):int
    {
        var result:int;
        if (x > y) result = 1;
        else if (x < y) result = -1;
        return result;
    }

    private function kindOfRadixSort(vector:Vector.<int>):Vector.<int>
    {
        // Arrays are sparse, therefore we don't allocate memory when having
        // gaps between filled indices as we would have we used vector.
        var cache:Array = [];
        var result:Vector.<int> = new <int>[];
        var i:int;

        for each (i in vector)
        {
            if (cache[i]) (cache[i] as Vector.<int>).push(i);
            else cache[i] = new <int>[i];
        }
        // A for-each loop could be better here, and, in fact, for-each on
        // arrays usually provides elements in order 0..length, however,
        // the specs say the order is undefined.
        for (i = cache.length - 1; i >= 0; i--)
        {
            if (cache[i] is Vector.<int>)
                result = (cache[i] as Vector.<int>).concat(result);
        }
        return result;
    }
}
}