在数据结构ArrayList中进行高效搜索

Question

我有一个包含我的节点的ArrayList.节点具有源,目标和成本.现在我必须迭代整个ArrayList.这持续一段时间超过1000个节点.因此,我尝试按来源对列表进行排序.但是要在列表中找到相应的对,我尝试了二进制搜索.不幸的是,只有当我想要比较源或目标时才有效.但我必须比较两者以获得正确的一对.还有另一种搜索ArrayList的可能性吗？

Answer 1

很不幸的是,不行.ArrayList不能有效地搜索s.它们用于存储数据而不是搜索数据.如果你只想知道一个项是否被包含,我建议你使用,HashSet因为查找将有一个时间复杂的O(1)而不是O(n)的ArrayList(假设你已经实现了一个功能equals方法为你的对象).

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

但是,您可以使用a 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如此,这可能会导致相当多的测试跨越整个网络.

更新:添加代码以反映注释中代码的用途.

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 |.