Самый быстрый способ найти сложный тип в списке (Vector, Array, Dictionary, что бы ни было быстрее) - PullRequest
Новая
       22

Самый быстрый способ найти сложный тип в списке (Vector, Array, Dictionary, что бы ни было быстрее)

1 голос
/ 12 апреля 2011

Град, Стек!

Мне нужно знать лучший способ найти элемент внутри списка (Vector, Array, Dictionary, что бы ни было быстрее) сложного типа (расширения объектов и спрайтов).
Я использовал метод «Игла в стоге сена», но, похоже, он недостаточно быстр.

например. Предположим, у меня есть коллекция Спрайтов (пул, на самом деле).
Каждый спрайт будет добавлен на сцену и выполнит какое-то действие. После этого он умрет.
Я не хочу платить за его утилизацию (сборщик мусора) и каждый раз создаю новый (новый), поэтому я буду хранить мертвые спрайты в коллекции.

Иногда я буду вызывать метод, который добавит спрайт на сцену.
Этот спрайт может быть старым, если он уже мертв, или новым, если в пуле нет свободного спрайта.

Одним из сценариев, который подтолкнул меня к этому вопросу, была Система частиц.
«Головная» частица, оставляющая «след» частиц в каждом кадре и взрывающаяся во множество ярких частиц ... Каждый кадр ...

В некоторых случаях это до 50 000 PNG с движением, вращением, альфа, диспетчеризацией событий, масштабированием и т. Д. *
Но это только один сценарий ...

В данный момент я пытаюсь использовать пул объектов со связанным списком ...
Надеется, что это будет быстрее, чем запуск целого массива / вектора или создание новых экземпляров в каждом кадре, и пусть они окрашиваются с помощью Garbage Collection.

Кто-то знает лучший / более быстрый способ сделать это?

Ответы [ 6 ]

2 голосов
/ 12 апреля 2011

Я не уверен, что вы ищете и что вы хотите с этим делать.Если вы пытаетесь определить, есть ли строка в списке, самым быстрым решением является словарь.Я сделал небольшой тест. 

/**
* Determine which is the fastest to find a key between array, object, vector and dictionnary
**/
public class FlashTest extends Sprite {
    public function FlashTest() {
        var array:Array = new Array();
        var object:Object = new Object();
        var dictionary:Dictionary = new Dictionary();
        var vector:Vector.<String> = new Vector.<String>();

        for (var i:int=0; i < 10000; i++)
        {
            array.push(i.toString());
            object[i.toString()] = 1;
            vector.push(i.toString());
            dictionary[i.toString()] = 1;
        }

        var time:uint = getTimer();
        for (i=0; i < 10000; i++)
        {
            array.indexOf(i.toString());
        }

        trace("array"+(getTimer()-time)); //2855

        time = getTimer();
        for (i=0; i < 10000; i++)
        {
            vector.indexOf(i.toString());
        }

        trace("vector"+(getTimer()-time)); //3644


        time = getTimer();
        for (i=0; i < 10000; i++)
        {
            object.hasOwnProperty(i.toString());
        }

        trace("object"+(getTimer()-time)); //48


        time = getTimer();
        for (i=0; i < 10000; i++)
        {
            dictionary.hasOwnProperty(i.toString());
        }

        trace("dictionary"+(getTimer()-time)); //35


    }
}

Ура!

1 голос
/ 15 апреля 2011

Исходя из вашего пересмотренного вопроса, я не рассматриваю это как проблему оптимизации поиска, если мы не говорим о тысячах объектов.Когда один из ваших объектов из пула «умирает», он может уведомить ваш код, управляющий объектами (по событию или обратному вызову), и вы затем обнуляете его запись в своем словаре активных элементов (или склеиваете его из массива, или уничтожаете).с флагом, подробнее об этом ниже **), и поместите его в другой массив, представляющий собой стек объектов, ожидающих повторного использования.Когда вам нужен новый объект, вы сначала проверяете, есть ли что-нибудь в вашем стеке утилизации, и, если он есть, вы получаете один из них и повторно инициализируете его.Если стек пуст, вы создаете новый.

** Лучший выбор структуры данных, которую вы используете для хранения списка активных объектов (Array / Vector / Dictionary), вероятно, будет зависеть от характера вашегоlist - я бы поспорил, что структура данных, которую быстрее всего зациклить (например, если вам нужно делать это каждый кадр для их обновления), не обязательно та, из которой дешевле всего удалять.Какой из них вы выбираете, должен работать в зависимости от количества объектов, которые вы получили, и частоты, с которой они удаляются, повторно добавляются или обновляются.Просто сделайте небольшой тест, достаточно просто протестировать их все.Если у вас относительно мало объектов и вам не нужно их циклически перебирать, я бы положил деньги в Словарь для активного пула.

Ключевой момент, который нужно получить из этого ответа, заключается в том, что вы должныне просматривайте все предметы каждый раз, когда вам нужно найти мертвый для повторного использования, вы должны вытащить их, когда они умрут, и сохранить их как отдельный пул.

1 голос
/ 12 апреля 2011

Есть ли у вас какой-либо ключ, который можно отнести к объектам? (Или, возможно, использовать объект в качестве ключа)

Я считаю, что поиск по словарю, вероятно, будет самым быстрым, поскольку это сделанопохож на хэш-карту Java.

В этом случае вы могли бы использовать объект в качестве ключа и просто сделать
myDictionary[complexObject] != null (будет нулевым, если нет записи этого объекта)
Хотя, если вы могли бы указать далее, чтоэто вам нужно искать, я мог бы предложить дальнейшее применение этого

1 голос
/ 12 апреля 2011

Это действительно будет зависеть от того, как вам нужно идентифицировать объект.Вы сравниваете какое-то его значение или сравниваете ссылки?

Предполагая, что вы используете ссылки, вы должны использовать встроенные методы, имеющиеся как в массиве, так и в векторе.Линейные поиски (например, циклы по всему списку) растут медленнее с увеличением количества элементов в списке.Встроенные решения будут использовать более быстрые алгоритмы нелинейного поиска.Например: 

myList.indexOf(myObject);

Самое быстрое, что вы можете сделать, это прямой доступ.Если вы используете объект или словарь, вы можете использовать объект или уникальный идентификатор в качестве ключа, это дает вам прямой доступ.Но это не поможет, если вам нужно положение объектов в списке.например: 

//when setting it
var map = {};
map[myObject] = myObject;
//or
map[myObject.id] = myObject;

//then later
var myObject = map[THE KEY]
0 голосов
/ 15 апреля 2011

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

Средний поиск по вектору или массиву занимает в лучшем случае O (log (n)) время. Хотя вы можете достичь этого только в том случае, если ваш вектор отсортирован, что означает, что вы должны проводить время в другом месте, чтобы гарантировать его сортировку. Если вы не сортируете его, вам придется сканировать, что означает O (n).

Словари (иначе известные как хеш-таблицы, карты), при правильной реализации (и я могу только предположить, что то, что обеспечивает ActionScript, реализовано правильно) гарантируют O (1) время доступа. Вы платите за это в большей памяти. O (1) скрывает некоторые постоянные времена, которые выше, чем при поиске Vector, поэтому для небольших списков элементов Vector будет более эффективным. Тем не менее, из описания вашей проблемы это звучит как ежу понятно.

0 голосов
/ 12 апреля 2011

Я бы сказал, Вектор, но, похоже, есть некоторые смешанные результаты.

Vector. <> Vs array

http://impossiblearts.com/blog/2008/06/fp10-vector-vs-array/

...