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. 如果数组包含一项，则返回该项
  3. 确定哪一半将包含正确的结果
  4. 转到第 1 步

这应该在对数时间内找到结果。（注意 log 2 (1,000) ~ 10 和 log 2 (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 回答