1

あられ、スタック！

複雑なタイプ（オブジェクトとスプライトの拡張）のリスト（ベクトル、配列、辞書など、より高速なもの）内のアイテムを見つけるための最良の方法を知る必要があります。
「NeedleinHaystack」方式を使用しましたが、十分な速度ではないようです。

たとえば、スプライトのコレクション（実際にはプール）があるとします。
各スプライトはステージに追加され、いくつかのアクションを実行します。その後、それは死ぬでしょう。
私はそれを処分する（ガベージコレクション）と毎回別の（新しい）ものを作成するためのコストを払いたくないので、死んだスプライトをコレクションに保持します。

時々、ステージにスプライトを追加するメソッドを呼び出すことがあります。
このスプライトは、すでに死んでいる場合は古いスプライトにすることができ、プールに空きスプライトがない場合は新しいスプライトにすることができます。

この質問に私を駆り立てたシナリオの1つは、パーティクルシステムでした。
フレームごとにパーティクルの「トレイル」を残し、派手な多数のパーティクルに爆発する「ヘッド」パーティクル...すべてのフレーム...

モーション、回転、アルファ、イベントディスパッチ、スケールなどで最大50.000 PNGをカウントすることもあります
が、これは1つのシナリオです...

現時点では、リンクリスト付きのオブジェクトプールを使用しようとしています...
配列/ベクトル全体を実行したり、フレームごとに新しいインスタンスを作成してガベージコレクションで染色したりするよりも高速になることを願っています。

誰かがそれを行うためのより良い/より速い方法を知っていますか？

4

6 に答える 6

2

あなたが何を探しているのか、それで何をしたいのかわかりません。文字列がリストに含まれているかどうかを判断しようとしている場合、最速の解決策は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


    }
}

乾杯！

于 2011-04-12T16:36:52.697 に答える
1

オブジェクトに起因するキーはありますか？（またはオブジェクトをキーとして使用する可能性があります）

辞書の検索は、JavaのHashMapと同様に行われるため、おそらく最速になると思います。

その場合、オブジェクトをキーとして使用することができます
myDictionary[complexObject] != null （そのオブジェクトのエントリがない場合はnullになります）
。ただし、さらに検索する必要があるものを指定できれば、次のアプリケーションをさらに提供できる可能性があります。これ

于 2011-04-12T17:22:46.800 に答える
1

これは、実際には、オブジェクトを識別する方法によって異なります。あなたはそれのいくつかの価値を比較していますか、それとも参照を比較していますか？

参照を想定すると、配列とベクトルの両方にある組み込みメソッドを使用する必要があります。線形検索（リスト全体のループなど）は、リスト内のアイテムの数が増えるにつれて遅くなります。組み込みのソリューションは、より高速な非線形検索アルゴリズムを使用します。例えば：

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

あなたの改訂された質問に基づいて、私たちが何千ものオブジェクトについて話しているのでない限り、私はこれを検索最適化の問題とは見ていません。プールからのオブジェクトの1つが「死ぬ」と、オブジェクトを管理しているコードに（イベントまたはコールバックによって）通知し、アクティブなアイテムのディクショナリのエントリを無効にする（または配列からスプライスするか、強制終了する）フラグを付けて、これについては以下で詳しく説明します**）、再利用を待機しているオブジェクトのスタックである別の配列にプッシュします。新しいオブジェクトが必要な場合は、最初にリサイクルスタックに何かがあるかどうかを確認し、ある場合は、そのうちの1つをポップして再初期化します。スタックが空の場合は、新しいスタックを作成します。

**アクティブオブジェクトリスト（配列/ベクトル/辞書）を保持するために使用するデータ構造の最良の選択は、おそらくリストの性質に依存します-私は、最も速いデータ構造がループオーバー（たとえば、フレームごとにループオーバーを実行して更新する必要がある場合）は、必ずしも削除するのに最も安価なものではありません。どちらを使用するかは、取得したオブジェクトの数と、オブジェクトが削除、再追加、または更新される頻度に最も適したものにする必要があります。少しベンチマークを行うだけで、すべてをテストするのは簡単です。オブジェクトが比較的少なく、それらを継続的にループする必要がない場合は、アクティブプールのディクショナリにお金を入れます。

この答えから得られる重要なポイントは、再利用するために死んだアイテムを見つける必要があるたびにすべてのアイテムをループするのではなく、それらが死んだときにそれらを引き出し、それを別のプールとして保持する必要があるということです。

于 2011-04-15T13:14:18.427 に答える
0

ベクターと言いますが、結果はまちまちです。

ベクトル。<>対配列

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

于 2011-04-12T16:07:47.090 に答える
0

スプライトに一意のIDがあり、辞書を使用できる場合、質問は何ですか？辞書は間違いなく高速です。

ベクトルまたは配列の平均検索には、せいぜいO（log（n））時間がかかります。ただし、ベクターがソートされている場合にのみそれを達成できます。つまり、ソートされたままになるように他の場所で時間を費やすことを意味します。並べ替えない場合は、スキャンする必要があります。つまり、O（n）です。

辞書（ハッシュテーブル、マップとしてさまざまに知られています）は、正しく実装されている場合（そして、Actionscriptが提供するものが正しく実装されているとしか想定できません）、O（1）アクセス時間を保証します。あなたはより多くのメモリでそれを支払います。O（1）は、Vector検索よりも長い定数時間を非表示にするため、アイテムの小さなリストの場合、Vectorの方が効率的です。ただし、問題の説明からは、簡単に聞こえます。

于 2011-04-15T05:41:48.830 に答える