arrays - Flash AS3，如何使用整数键索引 HashMap

Question

这是交易。

现在我有一个游戏状态字典

history = new Dictionary();

每个状态的key是一个时间戳(int)

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

我的问题是，如何找到最近的游戏状态。假设我想知道 670 时的状态，我想要不大于 670 的最新历史记录(我不想显示 future ) 。这将是历史[500]。

现在我正在循环遍历每个键，以找到最新的一个。有什么方法可以索引这些时间戳，这样我就可以比线性时间更快地搜索吗？ (我会有很多 key !)也许我不需要字典？

Answer 1

您可以使用二分搜索(分而治之)方法，将状态保存在排序数组中，然后递归地:

1. 将数组分成两半
2. 如果数组包含一项，则返回该项
3. 确定哪一半包含正确的结果
4. 转到步骤 1

这应该在对数时间内找到结果。 (请注意，log₂(1,000) ~ 10 和 log₂(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 类，以便从数组中获取类型化对象，因为使用动态对象会对性能产生负面影响。