Форум Flasher.ru - Оптимизация сортировок и выборок.

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

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

- - Оптимизация сортировок и выборок. (http://www.flasher.ru/forum/showthread.php?t=150297)

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

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

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

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

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

Код AS3:

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 );

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

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

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

Цитата:

Сообщение от shootkin (Сообщение 971978)

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

Код AS3:

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

Цитата:

Сообщение от artfabrique (Сообщение 971983)

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

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

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

Цитата:

Сообщение от shootkin (Сообщение 971988)

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

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

Цитата:

Сообщение от Psycho Tiger (Сообщение 971992)

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

Цитата:

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

Цитата:

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

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

Цитата:

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

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

Цитата:

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

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

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