2

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

4

5 回答 5

5

很不幸的是，不行。ArrayLists 不能被有效地搜索。它们用于存储数据而不是搜索数据。如果您只想知道是否包含某个项目，我建议您使用HashSet查找将具有 O(1) 而不是 O(n) 的 ArrayList 的时间复杂度（假设您已经equals为您的对象）。

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

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

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 方法。也就是说，如果它们是对象。但是请注意，如果它们也是Nodes，这可能会导致相当多的测试跨越整个网络。

更新：添加了代码以反映注释中代码的用途。

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

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

于 2013-06-24T15:11:00.910 回答
1

您需要将源和目标组合成一个比较器，例如

compare(T o1, T o2) {
    if(o1.source < o2.source) { return -1; }
    else if(o1.source > o2.source) { return 1; }
    // else o1.source == o2.source
    else if(o1.target < o2.target) { return -1; }
    else if(o1.target > o2.target) { return 1; }
    else return 0;
}
于 2013-06-24T15:07:18.940 回答
0

您可以使用该.compareTo()方法来比较您的节点。

于 2013-06-24T15:07:35.347 回答
0

您可以创建两个 ArrayList。第一个按源排序，第二个按目标排序。然后，您可以在相应的列表上使用 binarySearch 按源或目标进行搜索。

于 2013-06-24T15:10:45.627 回答
0

您可以创建一个帮助类来存储源-目标对：

class SourceTarget {

    public final Source source; // public fields are OK when they're final and immutable.
    public final Target target; // you can use getters but I'm lazy
                                // (don't give this object setters. Map keys should ideally be immutable)

    public SourceTarget( Source s, Target t ){
        source = s;
        target = t;
    }

    @Override
    public boolean equals( Object other ){
        // Implement in the obvious way (only equal when both source and target are equal
    }

    @Override
    public int hashCode(){
        // Implement consistently with equals
    }
}

然后将你的东西存储在 aHashMap<SourceTarget, List<Node>>中，每个源-目标对映射到恰好具有该源-目标对的节点列表。要检索只需使用

List<Node> results = map.get( new SourceTarget( node.source, node.target ) );

除了创建一个辅助类之外，您还可以使用 Zim-Zam 的答案中的比较器和一个TreeMap<Node,List<Node>>具有代表性的Node对象作为SourceTarget配对。

于 2013-06-24T16:41:01.810 回答