在列表中找到复杂类型的最快方法（向量，数组，字典，等等）

| 冰雹，堆栈！我需要知道在复杂类型（对象和子对象的扩展名）的列表（向量，数组，字典，等等，更快的东西）中找到项的最佳方法。我曾经使用过“干草堆中的针”方法，但似乎速度不够快。例如。假设我有一个Sprites集合（实际上是一个池）。每个精灵都会添加到舞台上并执行一些操作。之后，它将死亡。我不想支付处理（垃圾收集）并每次创建另一个（新）的费用，因此我将死掉的精灵保留在一个集合中。有时我会调用将在舞台上添加精灵的方法。如果该精灵已经失效，它可以是旧的，如果池中没有可用的精灵，则可以是新的。将我引向这个问题的场景之一是粒子系统。一个“头部”粒子在每帧中留下一个“轨迹”粒子，并爆炸成大量的浮华粒子...每帧... 有时，通过运动，旋转，alpha，事件调度，缩放等，最多可计算50.000个PNG。但是，这只是一个场景... 目前，我正在尝试使用带有链接列表的对象池... 希望运行整个阵列/向量或在每个帧创建新实例更快，并让它们使用垃圾回收进行染色。有人知道更好/更快的方法吗？

已邀请:

6 个回复

骂狮淋唐便

根据您修订后的问题，除非我们要讨论数千个对象，否则我不会将其视为搜索优化问题。当您的某个对象来自“ \ die”池时，它可能会通知您管理对象的代码（通过事件或回调），然后您将其在活动项字典中的条目清空（或从Array进行拼接，或使用标志将其杀死，更多信息请参见下文**），然后将其压入另一个数组，该数组是一堆等待重用的对象。当您需要一个新对象时，首先要检查回收堆栈中是否有任何物品，如果有，则弹出其中一个物品并重新初始化它。如果堆栈为空，则构造一个新的堆栈。 **用于保存活动对象列表（数组/向量/字典）的哪种数据结构的最佳选择可能取决于列表的性质-我愿意打赌，最快的数据结构循环播放（例如，如果您需要在每一帧进行更新），则不必将其最便宜地删除。随身携带哪个对象，应该最适合您拥有的对象数量以及删除，重新添加或更新对象的频率。只需进行一些基准测试，就可以轻松测试所有这些基准。如果您的对象相对较少，并且不需要连续地遍历它们，则可以将钱花在活动池的Dictionary上。从此答案中得出的关键点是，每次需要找到一个死掉的物品重新使用时，都不要遍历所有物品，而是应在它们死后将它们取出，并将其作为一个单独的水池保存。

佬棠

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

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


    }
}

干杯!

剿畦缄饥小

这实际上取决于您如何识别对象。您是在比较它的价值还是在比较参考？假定引用，您应该使用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]

磐乓铝举

您是否有某种可以归因于对象的密钥？（或可能将对象用作密钥）我相信，字典查找可能最快，因为它的完成方式类似于Java的HashMap。在这种情况下，您可以将对象作为键，然后执行 myDictionary[complexObject] != null （如果没有该对象的条目，则为null）虽然如果您可以进一步指定它是什么，则需要查找，但我可能可以对此提供进一步的应用

财沟项胶

我会说Vector，但结果似乎有些不同。 Vector。<> vs数组 http://impossiblearts.com/blog/2008/06/fp10-vector-vs-array/

倪蕊悲潍

如果您的精灵具有唯一的ID，并且可以使用字典，那么问题是什么？字典肯定更快。向量或数组上的平均搜索最多需要O（log（n））时间。虽然只有在对Vector进行排序后才能实现，但这意味着要花时间在其他地方以确保它保持排序。如果不对它进行排序，则必须进行扫描，这意味着O（n）。字典（通常称为哈希表，映射）在正确实施时（而且我只能假定Actionscript提供的内容在正确实施时）可以保证O（1）访问时间。您需要为更多的内存付费。 O（1）隐藏了一些比Vector搜索要高的常数时间，因此对于较小的项目列表，Vector会更有效。但是，从对问题的描述来看，这听起来很容易。

要回复问题请先登录或注册

在列表中找到复杂类型的最快方法（向量，数组，字典，等等）

6 个回复

发起人

object_pooling

actionscript_3

performance

问题状态

在列表中找到复杂类型的最快方法（向量，数组，字典，等等）

与内容相关的链接

6 个回复

发起人

object_pooling

actionscript_3

performance

问题状态