Efficient Search In Datastructure Arraylist

I've an ArrayList which contains my nodes. A node has a source, target and costs. Now I have to iterate over the whole ArrayList. That lasts for for over 1000 nodes a while. Theref

Solution 1:

Unfortunately, no. ArrayLists are not made to be efficiently searched. They are used to store data and not search it. If you want to merely know if an item is contained, I would suggest you use HashSet as the lookup will have a time complexitiy of O(1) instead of O(n) for the ArrayList (assuming that you have implemented a functioning equals method for your objects).

If you want to do fast searches for objects, I recommend using an implementation of Dictionnary like HashMap. If you can afford the space requirement, you can have multiple maps, each with different keys to have a fast lookup of your object no matter what key you have to search for. Keep in mind that the lookup also requires implementing a correct equals method. Unfortunately, this requires that each key be unique which may not be a brilliant idea in your case.

However, you can use a HashMapto store, for each source, a List of nodes that have the keyed source as a source. You can do the same for cost and target. That way you can reduce the number of nodes you need to iterate over substantially. This should prove to be a good solution with a scarcely connected network.

privateHashMap<Source, ArrayList<Node>> sourceMap = new HashMap<Source, ArrayList<Node>>();
privateHashMap<Target, ArrayList<Node>> targetMap = new HashMap<Target, ArrayList<Node>>();
privateHashMap<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; }
}

In order to be sure that your code will work, be sure to overwrite the equals method. I know I have said so already but this is a very common mistake.

@Overridepublicbooleanequals(Objectobject)
{ 
    if(objectinstanceofNode)
    {
        Node node = (Node) object;
        if(source.equals(node.getSource() && target.equals(node.getTarget()))
        {
            returntrue;
        }
    } else {
        returnfalse;
    }
}

If you don't, the test will simply compare references which may or may not be equal depending on how you handle your objects.

Edit: Just read what you base your equality upon. The equals method should be implemented in your node class. However, for it to work, you need to implement and override the equals method for the source and target too. That is, if they are objects. Be watchful though, if they are Nodes too, this may result in quite some tests spanning all of the network.

Update: Added code to reflect the purpose of the code in the comments.

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

Now you have a list of all nodes that match the source and target criteria. Provided that you are willing to sacrifice a bit of memory, the lookup above will have a complexity of O(|sourceMap| * (|sourceMap|+|targetMap|)) [1]. While this is superior to just a linear lookup of all nodes, O(|allNodeList|), if your network is big enough, which with 1000 nodes I think it is, you could benefit much. If your network follows a naturally occurring network, then, as Albert-László Barabási has shown, it is likely scale-free. This means that splitting your network into lists of at least source and target will likely (I have no proof for this) result in a scale-free size distribution of these lists. Therefore, I believe the complexity of looking up source and target will be substantially reduced as |sourceMap| and |targetMap| should be substantially lower than |allNodeList|.

Solution 2:

You'll need to combine the source and target into a single comparator, e.g.

compare(T o1, T o2) {
    if(o1.source < o2.source) { return -1; }
    elseif(o1.source > o2.source) { return1; }
    // else o1.source == o2.sourceelseif(o1.target < o2.target) { return -1; }
    elseif(o1.target > o2.target) { return1; }
    elsereturn0;
}

Solution 3:

You can use the .compareTo() method to compares your nodes.

Solution 4:

You can create two ArrayLists. The first sorted by source, the second sorted by target. Then you can search by source or target using binarySearch on the corresponding List.

Solution 5:

You can make a helper class to store source-target pairs:

classSourceTarget {

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

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

    @OverridepublicinthashCode(){
        // Implement consistently with equals
    }
}

Then store your things in a HashMap<SourceTarget, List<Node>>, with each source-target pair mapped to the list of nodes that have exactly that source-target pair. To retrieve just use

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

---

Alternatively to making a helper class, you can use the comparator in Zim-Zam's answer and a TreeMap<Node,List<Node>> with a representative Node object acting as the SourceTarget pair.