CODEWITHSUNDEEP
java
Amogh
Amogh

Reputation: 4573

Fastest and optimized way to search for value in a List<T>

I have a List<Person> persons = new ArrayList<Person>(), the size of this list is 100+. I want to check whether a particular personID object is contained in this list or not. Currently I am doing it in this way :

for(Person person : persons) 
{
    for(Long pid : listOfIDs) 
    {
        if(person.personid == pid) 
        {
            // do somthing 
        } 
        else
        {
            // do somthing 
        }
    } // end of inner for
}

But I don't want to traverse through the persons list for each element in listOfIDs. I thought of taking HashMap of Person with personid as the key and Person object as value. So that I can only traverse through listOfIDs and check for contains()

Is there any other way to do it?

Upvotes: 1

Views: 2427

Answers (3)

AndrWeisR
AndrWeisR

Reputation: 1226

Comparison of 3 search methods - look for a word in a list of a million words:

List<String> list = new ArrayList<>();
            
// One million random 5 letter words.
for (int i = 0; i < 1000000; i++) {
    list.add( String.valueOf((char)(65 + (int)(Math.random() * 26)))
            + String.valueOf((char)(65 + (int)(Math.random() * 26)))
            + String.valueOf((char)(65 + (int)(Math.random() * 26)))
            + String.valueOf((char)(65 + (int)(Math.random() * 26)))
            + String.valueOf((char)(65 + (int)(Math.random() * 26)))
    );
}
list.add("POPPY");
            
Collections.sort(list);
            
long start;
            
start = System.currentTimeMillis();
System.out.println(list.contains("POPPY"));
System.out.println("Contains took " + (System.currentTimeMillis() - start) + " ms.");
            
start = System.currentTimeMillis();
System.out.println(Collections.binarySearch(list,"POPPY"));
System.out.println("BinarySearch took " + (System.currentTimeMillis() - start) + " ms.");
            
start = System.currentTimeMillis();
if (list.parallelStream().anyMatch(s -> s.equals("POPPY"))) {
    System.out.println("Found.");
}
System.out.println("Anymatch took " + (System.currentTimeMillis() - start) + " ms.");

Outputs:

true
Contains took 46 ms.
598377
BinarySearch took 0 ms.
Found.
Anymatch took 26 ms.

Upvotes: 0

Rob
Rob

Reputation: 6497

Your implementation with nested loops will not scale well if the lists get long. The number of operations you will do is the product of the length of the two lists.

If at least one of your lists is sorted by ID, you can use binary search. This will be an improvement over nested loops.

Building a Map is a good idea and will scale well. Using this technique, you will iterate over the list of Persons once to build the map and then iterate over the list of IDs once to do the lookups. Make sure that you initialize the size of the HashMap with the number of Persons (so you don't have to rehash as you put the Persons into the Map). This is a very scalable option and does not require that either list be sorted.

If BOTH lists happen to be sorted by ID, you have another attractive alternative: jointly walk down the two lists. You will start at the beginning of both lists and move forward in the list with the smallest ID. If the IDs are equal, then you do your business logic for having found the person with that ID and step forward in both lists. As soon as you get to the end of either list, you are done.

Upvotes: 1

sprinter
sprinter

Reputation: 27956

Java's Collections provides a binary search which is very fast but it assumes you are searching for a member of the list. You could implement your own using your ID criteria:

Collections.sort(persons, (p1, p2) -> p1.personID - p2.personID);
if (binarySearch(persons, id)) {
    ...
}

boolean binarySearch(List<Person> personList, Long id) {
    if (personList.empty())
        return false;
    long indexToTest = personList.size() / 2;
    long idToTest = personList.get(indexToTest).personID;
    if (idToTest < id) 
        return binarySearch(personList.subList(indexToTest + 1, personList.size());
    else if (idToTest > id)
        return binarySearch(personList.subList(0, indexToTest));
    else
        return true;
}

If you don't want to sort your list then you could copy it to a sorted list and search on that: for large lists that would still be much faster than iterating through it. In fact that's pretty similar to keeping a separate hash map (though a hash map could be faster).

If you must iterate, then you can at least use a parallel stream to take advantage of multiple cores if you have them:

if (persons.parallelStream().anyMatch(p -> p.personID == id)) {
    ...
}

Upvotes: 0

Related Questions