1

冰雹，堆栈！

我需要知道在复杂类型（对象和精灵的扩展）的列表（向量、数组、字典，任何更快的）中查找项目的最佳方法。
我使用了“干草堆中的针”方法，但似乎速度不够快。

例如，假设我有一组Sprite（实际上是一个池）。
每个精灵都会被添加到舞台并执行一些动作。在那之后，它会死去。
我不想支付处理它（垃圾收集）并每次创建另一个（新）的成本，所以我会将死去的精灵保存在一个集合中。

有时我会调用一个将精灵添加到舞台的方法。
这个 sprite 可以是旧的，如果它已经死了，或者是一个新的，如果池中没有任何空闲的 sprite。

将我推向这个问题的场景之一是粒子系统。
一个“头”粒子在每一帧留下一个粒子“轨迹”，然后爆炸成一大堆闪闪发光的粒子……每一帧……

有时，这需要多达 50.000 个 PNG，包括运动、旋转、alpha、事件调度、缩放等……
但是，这只是一个场景……

目前我正在尝试使用带有链接列表的对象池......
希望运行整个数组/向量或每帧创建新实例并让它们用垃圾收集染色会更快。

有人知道更好/更快的方法吗？

4

6 回答 6

2

我不确定你在搜索什么以及你想用它做什么。如果您试图确定一个字符串是否在列表中，最快的解决方案是字典。我做了一个小基准测试。

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


    }
}

干杯!

于 2011-04-12T16:36:52.697 回答
1

这实际上取决于您需要如何识别对象。你是在比较它的一些价值还是比较参考文献？

假设引用，您应该使用 Array 和 Vector 上的内置方法。随着列表中项目数量的增加，线性搜索（如遍历整个列表）会变慢。内置解决方案将使用更快的非线性搜索算法。例如：

myList.indexOf(myObject);

您可以做的最快的事情是直接访问。如果您使用对象或字典，则可以使用对象或唯一 ID 作为键，这使您可以直接访问。但是，如果您需要列表中的对象位置，这将无济于事。例如：

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

//then later
var myObject = map[THE KEY]
于 2011-04-12T16:25:51.990 回答
1

您是否有任何可以归因于对象的键？（或者可能将对象用作键）

我相信字典查找可能是最快的，因为它类似于 Java 的 HashMap。

在这种情况下，您可以将对象作为键并执行
myDictionary[complexObject] != null （如果没有该对象的条目，它将为空）
尽管如果您可以进一步指定您需要查找的内容，我可能会提供进一步的应用这个

于 2011-04-12T17:22:46.800 回答
1

根据您修改后的问题，除非我们谈论数千个对象，否则我不认为这是搜索优化问题。当池中的一个对象“死亡”时，它可以通知管理对象的代码（通过事件或回调），然后您将其在活动项目字典中的条目清空（或从数组拼接，或杀死它带有一个标志，更多内容见下文**），然后将其推送到另一个数组，该数组是一堆等待重用的对象。当您需要一个新对象时，您首先检查回收堆栈中是否有任何内容，如果有，则弹出其中一个并重新初始化它。如果堆栈为空，则构建一个新堆栈。

**用于保存活动对象列表（数组/向量/字典）的数据结构的最佳选择可能取决于列表的性质——我敢打赌，最快的数据结构循环（例如，如果您需要在每一帧都更新它们）不一定是最便宜的删除。你应该选择哪一个最适合你拥有的对象的数量以及它们被删除、重新添加或更新的频率。只需进行一些基准测试，就可以轻松测试所有这些。如果你有相对较少的对象，并且不需要连续循环它们，我会把钱放在活动池的 Dictionary 上。

从这个答案中得到的关键点是，你不应该在每次需要找到一个死掉的项目来重新使用时循环遍历所有项目，你应该在它们死掉时将它们拉出来并将其作为一个单独的池保存。

于 2011-04-15T13:14:18.427 回答
0

如果您的精灵有唯一的 ID，并且您可以使用字典，那么问题是什么？字典肯定更快。

对向量或数组的平均搜索最多需要 O(log(n)) 时间。尽管只有对 Vector 进行了排序才能实现这一点，这意味着要花时间在其他地方确保它保持排序。如果您不对其进行排序，则必须进行扫描，这意味着 O(n)。

字典（也称为哈希表、地图）在正确实施时（我只能假设 Actionscript 提供的内容是正确实施的）保证 O(1) 访问时间。您需要在更多内存中为此付出代价。O(1) 隐藏了一些高于 Vector 搜索的常数时间，因此对于小型项目列表，Vector 会更有效。但是，从您对问题的描述来看，这听起来很简单。

于 2011-04-15T05:41:48.830 回答
0

我会说 Vector，但似乎有一些好坏参半的结果。

向量.<> vs 数组

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

于 2011-04-12T16:07:47.090 回答