在列表中查找复杂类型的最快方法（向量、数组、字典，无论哪种更快）

Question

冰雹，斯塔克！

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

---

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

有时我会调用一个方法来将精灵添加到舞台上。
如果该精灵已经死亡，则该精灵可以是旧精灵；如果池中没有任何空闲精灵，则该精灵可以是新精灵。

---

促使我提出这个问题的场景之一是粒子系统。
一个“头部”粒子每帧都会留下一条粒子“踪迹”，然后爆炸成大量华丽的粒子...每一帧...

有时这会计算出多达 50.000 个 PNG，包括运动、旋转、Alpha、事件调度、缩放、等等...
但是，这只是一种情况...

---

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

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

Answer 1

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

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


    }
}

干杯!

Answer 2

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

**用于保存活动对象列表（数组/向量/字典）的数据结构的最佳选择可能取决于列表的性质 - 我愿意打赌最快的数据结构循环（例如，如果您需要每一帧都执行此操作来更新它们）不一定是删除成本最低的循环。您应该选择最适合您拥有的对象数量以及它们被删除、重新添加或更新的频率的那个。只需做一点基准测试，就很容易测试所有这些。如果你的对象相对较少，并且不需要连续循环它们，我会把钱花在活动池的字典上。

从这个答案中得到的关键点是，每次您需要找到一个死的物品来重复使用时，您不应该循环遍历所有物品，您应该在它们死后将它们拉出来并将其保留为一个单独的池。

Answer 3

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

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

myList.indexOf(myObject);

您能做的最快的事情就是直接访问。如果您使用对象或字典，则可以使用对象或唯一 ID 作为键，这样您就可以直接访问。但如果您需要列表中的对象位置，这并没有帮助。例如：

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

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

Answer 4

你有任何类型的键可以归因于对象吗？（或者可能使用对象作为键）

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

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

Answer 5

我会说向量，但似乎有一些混合的结果。

矢量。<> vs 数组

http://impossiblearts.com/blog /2008/06/fp10-向量与数组/

Answer 6

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

Vector 或 Array 上的平均搜索最多花费 O(log(n)) 时间。不过，只有在 Vector 已排序的情况下才能实现这一点，这意味着要花时间在其他地方以确保它保持排序。如果不排序就必须扫描，这意味着 O(n)。

字典（也称为哈希表、映射）在正确实现时（我只能假设 Actionscript 提供的内容实现正确）保证 O(1) 访问时间。你为此付出了更多内存的代价。 O(1) 隐藏了一些比向量搜索更高的常数时间，因此对于较小的项目列表，向量会更有效。然而，从你的问题描述来看，这听起来是理所当然的。