Форум Flasher.ru - Сортировка в векторе с элементами null

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

- - Сортировка в векторе с элементами null (http://www.flasher.ru/forum/showthread.php?t=156222)

Сортировка в векторе с элементами null

Обнаружил достаточно забавный факт.
Есть, например, вот такой код:

Код AS3:

var valVect:Vector.<ListEl> = new Vector.<ListEl>();

 

var findCount:int = 500; // Задаём количество не null элементов из общего количества 3000

 

for(i = 0 ; i < findCount ; i++)

{

        valVect.push(new ListEl(Math.random()*8)); // Параметр просто инициализирует значение param:Number

}

for( ; i < 3000 ; i++)

{

        valVect.push(null);

}

 

time = getTimer();

 

valVect.sort(function(a:ListEl,b:ListEl)

{

        if(a == null)

        {

                return -1;

        }

        else if(b == null)

        {

                return 1;

        }

        else

        {                                                        

        return (a.param == b.param) ? 0 : ((a.param > b.param) ? 1 : -1);                                                                

        }

});

 

trace(getTimer() - time);

Этот код работает тем дольше, чем больше null-элементов в векторе. Думал, это связанно с особенностями quick sort, он, кажется, плохо работает с уже сортированными структурами данных, но нет. Заменял null на конструкторы с единицами - всё становилось хорошо, работало моментально.

При всех null - 800 мс против 2 мс при полном отсутствии null в векторе.

P.S.: Ещё, раз уж зайдёт речь про вектора, задам несколько глупых вопросов.

1. Какая польза от использования свойства fixed = true? Понимаю, по ходу прирост скорости, но за счёт чего, что при этом происходит в самом векторе?

2. Можно ли реализовать вообще фиксированный вектор, чтобы обращение по индексу к элементам шло не итератором или ещё чёртичем для списка, а по смещению?

Тормоза кода связаны с тем, что ваш компаратор генерирует полную фигню на выходе. От него вообще-то ожидается, что если a < b, то b > a. А у вас если a == null и b == null указанное не выполняется. Поэтому можно даже и корректности сортировки не получить.

1. В первую очередь из-за того, что его размер не меняется, экономятся перераспределения памяти. Вполне может быть, что просто отсутствие изменения размера массива (с fixed == false) по быстродействию окажется таким же, что и при fixed == true.

2. А почему вы решили, что обращение идет итератором или по списку? Вектор то (в отличие от массива) плотная (dense) структура, на ней эффективно реализуется индексный доступ. В том числе и для resizeable vector, с амортизированной сложностью добавления и удаления в конец списка O(1).

Ничего подобного. Компаратор правильно написан. Я проверил.
Единственное - он сортирует null-элементы в начало вектора, но это не влияет на время выполнения (это я тоже проверил).

Добавлено через 3 минуты
За ответы на вопросы спасибо.

Как же правильно то? Он почему-то считает, что null < null вместо того, что null == null. Компаратор не сортирует. Он сравнивает. И компаратор, игнорирующий при одном из сценариев выполнения второе значение правильным быть не может.

Код AS3:

valVect.sort(function(a:Object,b:Object):int

{

    if(!a)

    {

        return -1;

    }

    else if(!b)

    {

        return 1;

    }

    else

    {                                                        

        return (a.param == b.param) ? 0 : ((a.param > b.param) ? 1 : -1);                                                                

    }

});

~1400-1850 ms

Код AS3:

valVect.sort(function(a:Object,b:Object):int

{

    if (!a && !b)

    {

        return 0;

    }

    else if(!a)

    {

        return -1;

    }

    else if(!b)

    {

        return 1;

    }

    else

    {                                                        

        return (a.param == b.param) ? 0 : ((a.param > b.param) ? 1 : -1);                                                                

    }

});

~50-200 ms
И это в дебаг версии.

Аааа!.. Да, всё! Понял!
Был не прав. Тему можно закрывать.

P.S.:

Цитата:

if (!a && !b)

Круто! Не знал, что в AS так можно.

а если функцию сделать не анонимной, да еще и тип ей задать, то еще быстрее станет)

Цитата:

а если функцию сделать не анонимной, да еще и тип ей задать, то еще быстрее станет

А если еще и !(a && b) написать, так оно вообще взлетит =)