Блог

Во время игры с 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;
    }
}
  

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

Я только что столкнулся с такой же проблемой: Vector.sort () из 50 000 объектов значений в поле с тремя различными значениями: ~ 2 минуты. Затем я вызываю почти точно такую же сортировку, с той лишь разницей, что я разрываю связь (когда x == y) для вторичного поля с уникальным значением (то есть для поля с 50 000 различными значениями): менее 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;
}
  

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

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

На самом деле это не происходит с 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 resu<
    }

    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 resu<
    }
}
}