Fastest method to find a complex type in a list (Vector, Array, Dictionary, whatever is faster)_问答_开发者

Hail, Stack!

I need to know the best method to find an item inside a list (Vector, Array, Dictionary, whatever is faster) of complex type (extensions of Objects and Sprites).

I've used "Needle in Haystack" method, but it seems that it isn't fast enough.

E.g. Suppose that I have a collection of Sprites (a pool, in fact).

Each sprite will be added to the stage and perform some action. After that, it will die.

I don't want to pay the cost to dispose it (garbage collect) and create another (new) one every time so I'll keep the dead sprites in a collection.

Sometimes times I'll call a method that will add a sprite to the stage.

This sprite can be a old one, if it is already dead, or a new one, if the pool don't have any free sprite.

One of the scenarios that pushed me to this question was a Particle System.

A "head" particle leaving a "trail" of particles every frame and exploding into a flashy multitude of particles... Every frame...

Some times this counts up to 50.000 PNGs with motion, rotation, alpha, event dispatching, scale, etc...

But, this is JUST ONE scenario...

At the moment I'm trying to 开发者_StackOverflowuse a Object Pool with a Linked List...

Hopes that it will be faster that running a whole Array/Vector or create new instances every frame an let them dye with Garbage Collection.

Someone knows a better/faster way to do it?

I'm not sure about what you are searching and what you want to do with it. If you are trying to determine if a string is in a list, the fastest solution is the Dictionnary. I've done a little benchmark.

/**
* 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


    }
}

Cheers!

Based on your revised question, I don't see this as a search optimization issue unless we're talking about thousands of objects. When one of your objects from the pool "dies", it could notify your code that is managing the objects (by event or callback) and you then null out its entry in your Dictionary of active items (or splice it from Array, or kill it with a flag, more on this below**), and push it onto another Array, which is a stack of objects waiting to be reused. When you need a new object, you first check if there is anything in your recycle stack, and if there is, you pop one of those and re-initialize it. If the stack is empty, you construct a new one.

**The best choice of which data structure you use for holding your active objects list (Array/Vector/Dictionary) will probably depend on the nature of your list--I'd be willing to bet that the data structure that is quickest to loop over (for example if you need to do it every frame to update them) is not necessarily the one that is cheapest to delete from. Which one you go with should be whichever works best for the number of objects you've got and the frequency with which they get removed, re-added or updated. Just do a little benchmarking, it's easy enough to test them all. If you have relatively few objects, and don't need to loop over them continuously, I'd put my money on the Dictionary for the active pool.

The key point to get from this answer is that you should not be looping through all the items each time you need to find a dead one to re-use, you should pull them out when they die and keep that as a separate pool.

This is really going to depend on how you need to identify the object. Are you comparing some value of it or comparing references?

Assuming references, you should be using the built in methods found on both Array & Vector. Linear searches (like looping over the entire list) grow slower as the number of items in the list increases. The built in solutions will use faster non-linear search algorithms. For example:

myList.indexOf(myObject);

The fastest thing you can do is direct access. If you are using either an Object or Dictionary you can use the object or a unique id as the key, this gives you direct access. But this doesn't help if you need the objects position in the list. eg:

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

//then later
var myObject = map[THE KEY]

Do you have any sort of key that can be attributed to the objects?(or possibly use the object as a key)

I believe that a Dictionary look up would probably be the fastest since it is done similar to Java's HashMap.

In that case you could have the object as the key and just do
myDictionary[complexObject] != null (it will be null if there is no entry of that object)
Although if you could specify further what it is you need to lookup I might be able to offer further application of this

I'd say Vector, but there seems to be some mixed results.

Vector.<> vs array

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

If your sprites have unique IDs, and you can use a Dictionary, then what's the question? Dictionary is definitely faster.

The average search on a Vector or Array takes, at best, O(log(n)) time. Though you can only achieve that if your Vector is sorted, which means spending time elsewhere to ensure it stays sorted. If you don't sort it then you have to scan, which means O(n).

Dictionaries (variously known as hashtables, maps), when implemented right (and I can only assume that what Actionscript provides is implemented right) guarantee O(1) access time. You pay for that in more memory. The O(1) hides some constant times that are higher than those of Vector searches, so for small lists of items Vector would be more efficient. However, from the description of your problem it sounds like a no-brainer.