java - 数据结构ArrayList中的高效搜索

Question

我有一个包含我的节点的 ArrayList。节点具有源、目标和成本。现在我必须遍历整个 ArrayList。这会持续一段时间超过 1000 个节点。因此，我试图按来源对我的列表进行排序。但是为了在列表中找到相应的对，我尝试了二进制搜索。不幸的是，只有当我想比较源或目标时才有效。但我必须比较两者才能找到合适的一对。还有另一种可能有效地搜索 ArrayList 吗？

Answer 1

不幸的是，没有。 ArrayList 不是为了高效搜索而设计的。它们用于存储数据而不是搜索数据。如果你只想知道是否包含一个项目，我建议你使用 HashSet 因为查找的时间复杂度为 O(1) 而不是 ArrayList 的 O(n) (假设你已经为你的对象实现了一个有效的 equals 方法)。

如果您想快速搜索对象，我建议使用 Dictionnary 的实现，例如 HashMap。如果你能负担得起空间需求，你可以有多个 map ，每个 map 都有不同的键，无论你必须搜索什么键，都可以快速查找你的对象。请记住，查找还需要实现正确的 equals 方法。不幸的是，这要求每个 key 都是唯一的，这在您的情况下可能不是一个绝妙的主意。

但是，您可以使用 HashMap 为每个源存储以键控源作为源的节点列表。您可以对成本和目标执行相同的操作。这样您就可以大大减少需要迭代的节点数量。对于几乎没有连接的网络，这应该被证明是一个很好的解决方案。

private HashMap<Source, ArrayList<Node>> sourceMap = new HashMap<Source, ArrayList<Node>>();
private HashMap<Target, ArrayList<Node>> targetMap = new HashMap<Target, ArrayList<Node>>();
private HashMap<Cost, ArrayList<Node>> costMap = new HashMap<Cost, ArrayList<Node>>();

/** Look for a node with a given source */
for( Node node : sourceMap.get(keySource) )
{
    /** Test the node for equality with a given node. Equals method below */
    if(node.equals(nodeYouAreLookingFor) { return node; }
}

为了确保您的代码能够正常工作，请务必覆盖equals 方法。我知道我已经说过了，但这是一个很常见的错误。

@Override
public boolean equals(Object object)
{ 
    if(object instanceof Node)
    {
        Node node = (Node) object;
        if(source.equals(node.getSource() && target.equals(node.getTarget()))
        {
            return true;
        }
    } else {
        return false;
    }
}

如果您不这样做，测试将简单地比较引用，这些引用可能相等也可能不相等，具体取决于您处理对象的方式。

编辑:只需阅读您的平等基础。 equals 方法应该在您的节点类中实现。但是，要使其正常工作，您还需要为源和目标实现和覆盖 equals 方法。也就是说，如果它们是对象。不过要注意，如果它们也是 Node，这可能会导致相当多的测试跨越整个网络。

更新:添加了代码以在注释中反射(reflect)代码的用途。

ArrayList<Node> matchingNodes = sourceMap.get(desiredSourde).retainAll(targetMap.get(desiredTarget));

现在您有一个包含与源和目标条件匹配的所有节点的列表。如果您愿意牺牲一点内存，上面的查找将具有 O(|sourceMap| * (|sourceMap|+|targetMap|)) [1] 的复杂度。 .虽然这优于所有节点的线性查找，O(|allNodeList|)，但如果您的网络足够大，我认为有 1000 个节点，您可能会受益匪浅。如果您的网络遵循自然发生的网络，那么正如 Albert-László Barabási 所展示的那样，它很可能是无标度的。这意味着将您的网络分成至少包含源和目标的列表可能(我没有证据证明)会导致这些列表的大小分布无标度。因此，我相信查找源和目标的复杂性将大大降低，因为 |sourceMap|和|targetMap|应该大大低于 |allNodeList|。