Оптимизация сортировок и выборок.

[artfabrique]

Народ а может кто нить кинуть ссылок на статьи по сравнительным скоростям сортировок и выборок в массивах и векторах?

Ситуация такая: Есть tiles:Vector.<Vector.<Tile>> , где Tile - это класс тайл игрового поля.
У каждого экземпляра Tile есть свойство state:uint (0-4)
Мне нужно выбрать из массива tiles выбрать все элементы Tile со state == 3, например.
При обычном поиске это сильно грузит процессор. Также пробовал переложить все содержимое в одномерный массив и делал sotrOn то тоже очень тормозит.
Основная проблема, что iles:Vector.<Vector.<Tile>> — это 2-мерный вектор 350*350 элементов и каждый весит около 2кб.

[gloomyBrain]

Я бы делал все таки одномерным вектором.
Для выборок можно создать несколько масивов, в которых хранить тайлы с одинаковым значением state
Сортировать можно QuickSort'ом, реализации есть в интернете
Насчет веса элемента - не совсем понятно, какое это имеет значение?

[shootkin]

Использовать Vector.filter, например:

var select_state : uint = 0;
var selectByState : Function = function( item:Tile, index:int, vector:Vector.<Tile> ):Boolean
{
    return item.state == select_state;
};
select_state = 3;
var filtered_tiles : Vector.<Tile> = tiles.filter( selectByState );

И массив сделать, конечно, одномерным. Это в первую очередь.

[artfabrique]

потому что при создании и добавлении элементов в массив создается его копия с новым элементом а потом удаляется старая, ибо память под массив резервируется и он является в ней неразрывным. И 350*350*2кб = 240mb памяти.

Добавлено через 2 минуты

Сообщение от shootkin

Использовать Vector.filter, например:

var select_state : uint = 0;
var selectByState : Function = function( item:Tile, index:int, vector:Vector.<Tile> ):Boolean
{
    return item.state == select_state;
};
select_state = 3;
var filtered_tiles : Vector.<Tile> = tiles.filter( selectByState );

И массив сделать, конечно, одномерным. Это в первую очередь.

Тааак.. ща проверю по скорости интересно, что быстрее sortOn или filter

[shootkin]

Сообщение от artfabrique

потому что при создании и добавлении элементов в массив создается его копия с новым элементом а потом удаляется старая, ибо память под массив резервируется и он является в ней неразрывным. И 350*350*2кб = 240mb памяти.

Нет. В массиве не сами элементы, а референсы на них. Сами элементы при операциях над массивом не уничтожаются и не создаются.

[Psycho Tiger]

Preprocessing, preprocessing, preprocessing (c), N-author`s.

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

[artfabrique]

Сообщение от shootkin

Нет. В массиве не сами элементы, а референсы на них. Сами элементы при операциях над массивом не уничтожаются и не создаются.

Я просто основывался на сведеньяю C++ разраба, друга. Он сказал, что в массиве хранятся сами данные. И подумалось, что плеер - это интерпретатор все таки и методы работы с массивами и векторами — зеркальные

Добавлено через 5 минут

Сообщение от Psycho Tiger

Preprocessing, preprocessing, preprocessing (c), N-author`s.

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

Количество тайлов не меняется, а вот состояние - да. По сути так щас и есть — генерится Vector.<Vector.<Tiles>> в самом начале. Нужен рандомный выбор из групп тайлов с разным состоянием. Для этого и требуется из двухмерного вектора получить одномерный вектор тайлов с одинаковым стейтом. И получить хотябы один раз, а потом изменять добавляя и удаляя элементы.

[gloomyBrain]

потому что при создании и добавлении элементов в массив создается его копия с новым элементом а потом удаляется старая, ибо память под массив резервируется и он является в ней неразрывным. И 350*350*2кб = 240mb памяти.

Эмм... с чего бы? Простые типы передаются по значению, остальное - по ссылке. Грубо говоря, почти любая переменная в AS3 - это указатель.

Тааак.. ща проверю по скорости интересно, что быстрее sortOn или filter

Уже проверено - самописные функции сортировки могут быть быстрее (для Vector'а почти не заметно, т.к. он типизирован, для Array разница ощутимая). Ну и, да, preprocessing

В массиве не сами элементы, а референсы на них

Кстати, в AS3 массивов, как таковых, нет. Есть только списки.

[alatar]

Простые типы передаются по значению

Для разработчика это выглядит именно так, но простые типы тоже передаются как ссылка (до определенного момента).

[gloomyBrain]

Интересно, спасибо. Только не понял - чем и где определяется момент?