2

これが取引です。

今、私はゲーム状態の辞書を持っています

history = new Dictionary();

各状態keyはタイムスタンプ(int)

history[100] = currentState;
history[500] = currentState;
history[699] = currentState;

私の質問は、どうすれば最新のゲーム状態を見つけることができるかということです。の州がどのようなものであったかを知りたいとしましょう。670最新の履歴が670必要です (未来を示したくありません)。これはhistory[500].

現在、最新のキーを見つけるために、すべてのキーをループしています。これらのタイムスタンプにインデックスを付けて、線形時間よりも高速に検索できる方法はありますか? （たくさんの鍵を持っているよ！） 辞書はいらないかも？

4

1 に答える 1

2

ソートされた配列に状態を保存し、再帰的に行う二分探索 (分割統治) アプローチを使用できます。

  1. 配列を 2 つに分割する
  2. 配列に項目が 1 つ含まれている場合は、その項目を返します
  3. どちらの半分が正しい結果を含むかを決定する
  4. ステップ 1 に進みます

これは、対数時間で結果を見つける必要があります。(なお、log2 ( 1,000)～10、log2 ( 10,000)～13)

以下はドラフト (およびテストされていない) 実装です。

class HistoryEntry
{
    public var timestamp:int;
    public var state:GameState;

    public function HistoryEntry(timestamp:int, state:GameState)
    {
        this.timestamp = timestamp;
        this.state = state;
    }
}

class History
{
    private var states:Array;

    public function History()
    {
        super();
        states = [];
    }

    public function addState(state:State):void
    {
        var timestamp:int = getTimer();
        var entry:HistoryEntry = new HistoryEntry(timestamp, state);
        states.push(entry);
    }

    public function getStateBefore(timestamp:int):State
    {
        return doGetStateBefore(timestamp, 0, states.length - 1);
    }

    // Recursive function
    private function doGetStateBefore(timestamp:int, beginIndex:int, endIndex:int):State
    {
        if (beginIndex == endIndex) {
            return states[beginIndex];
        }

        var beginEntry:HistoryEntry = states[beginIndex];
        var endEntry:HistoryEntry = states[endIndex];
        if (beginEntry.timestamp == timestamp) {
            return beginEntry.state;
        }
        if (endEntry.timestamp == timestamp) {
            return endEntry.state;
        }

        var middleIndex:int = (beginIndex + endIndex) / 2;
        var middleEntry:HistoryEntry = states[middleIndex];
        if (midleEntry.timestamp >= timestamp) {
            return doGetStateBefore(timestamp, beginIndex, middleIndex);
        } else {
            return doGetStateBefore(timestamp, middleIndex + 1, endIndex);
        }
    }
}

HistoryEntry動的オブジェクトを使用するとパフォーマンスに悪影響を及ぼすため、配列から型指定されたオブジェクトを取得するようにクラスを導入しました。

于 2012-09-02T17:15:58.993 に答える