arrays - 快速更有效地搜索数组以匹配不同类型的方法

Question

我正在使用 Swift 3 在数组中查找具有与目标 x,y 位置匹配的 x,y 位置的 GKGraphNode。下面是节点的初始化。您可以看到每个节点都有一个名为 gridPosition 的 vector_int2 坐标。我创建了这些节点的数组来匹配我的 map 的六边形网格。

class HexGraphNode : GKGraphNode {
var gridPosition: vector_int2!

required init(gridPosition: vector_int2) {
    super.init()

    self.gridPosition = gridPosition

}

required init?(coder aDecoder: NSCoder) {
    fatalError("init(coder:) has not been implemented")
}

}

我需要能够搜索这个数组以找到占据某个特定网格坐标的节点。我正在使用下面的功能。本地图很小(如 500 个节点以下)时，此函数可以正常工作。然而，随着数组的增长，程序的速度会减慢到无法接受的程度。我需要一种更有效的方法来搜索数组并找到匹配的节点，而不必每次都从索引零开始。我寻找过其他帖子，但它们似乎总是比较同一类型的对象。在本例中，我需要将对象的属性 (node.position) 与不同类型(包含 x,y 整数的 vector_int2)进行比较。

func node(atGridPosition position: vector_int2) -> NodeType {

    var result: NodeType!

    for node in self.nodes as! [NodeType] {

        if node.gridPosition.x == position.x && node.gridPosition.y == position.y {
            result = node

            break
        }
    }

    return result
}

任何帮助将不胜感激。

Answer 1

如果节点的网格位置不会动态更改，您可以保留节点字典而不是(或除了数组之外)。如果网格的宽度或高度固定(或最大)，则 x,y 坐标可以转换为单个整数值以用作字典中的键。否则你可以使用二级字典。

访问节点将是 O(1) 操作，而不是 O(n/2)。