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

[semenyakinVS]

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

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. Можно ли реализовать вообще фиксированный вектор, чтобы обращение по индексу к элементам шло не итератором или ещё чёртичем для списка, а по смещению?

[maxkar]

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

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

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

[semenyakinVS]

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

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

[maxkar]

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

[alatar]

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

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
И это в дебаг версии.

[semenyakinVS]

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

P.S.:

if (!a && !b)

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

[i.o.]

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

[gloomyBrain]

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

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