Looping over a huge list, check string equal to true

Question

I have a requirement as below:

List<User> userList = listOfUsers(); // Morethan 50,000 users

I need to find a user status from the list of users. if any one of the users is active then break the loop.

what is the efficient way to handle this in java ?

Answer 1

Because I see many Java 8 streaming solutions that do not use parallel streams, I add this answer. You have a large collection on which you do the matching, so you can use the power of parallelStreams when you would opt to use Java 8.

Optional<User> result = userList.parallelStream().filter(User::isActive).findAny();

Using a parallelStream will split the stream into multiple sub-streams which is more performant for very large collections. It uses the ForkJoinPool internally to process these sub-streams. The only difference here is that I use findAny() instead of findFirst() in this solution.

This is what Javadoc has to say about findAny():

The behavior of this operation is explicitly nondeterministic; it is free to select any element in the stream. This is to allow for maximal performance in parallel operations; the cost is that multiple invocations on the same source may not return the same result. (If a stable result is desired, use findFirst() instead.)

Here is a nice tutorial on Parallelism from Oracle.

Answer 2

One way to accelerate the search (Without Using Java 8) is by searching both directions in the ArrayList (i.e from the beginning to the middle, and from the end to the middle) at the same time via using multi-threading, I created this example and tested it against 1 million object/user to check if any of them is active (Note that I made only one user active and put him in the middle to see the longest time the search may take).

import java.util.ArrayList;

public class User {
    // some fields to test
    String name;
    boolean active;
    //volatile means all writes up to the volatile variable 
    //from other any thread are now visible to all other threads.
    //so they can share working on that variable
    static volatile boolean finishFirst = false; // to announce first thread finish
    static volatile boolean finishSecond = false; // to announce second thread finish
    static volatile boolean found = false; // // to announce if an active user found

    /**
     * Simple Constructor
     * @param name
     * @param active
     */
    public User(String name, boolean active){
        this.name = name;
        this.active = active;
    }


   public static void main(String[] args) {

     // create an ArrayList of type User
     ArrayList<User> list = new ArrayList<User>();

     // populate it with 1 MILLION user!!
     int i=0;
     for(;i<1000000; i++){
         // make only the one in the very middle active to prolong the search to max
         if(i==500000){
             list.add(new User(String.valueOf(i),true));
         }
         else{
             list.add(new User(String.valueOf(i),false));
         }

     }
     System.out.println("End of Adding " + i + " User" );

     // to measure how long it will take
     long startTime, endTime;
     startTime = System.currentTimeMillis();

     System.out.println("Found Any Active: "+ isAnyActive(list)); // invoke the method

     endTime = System.currentTimeMillis();
     System.out.println(endTime-startTime + " MilliScond");




   }

   public static boolean isAnyActive(ArrayList<User> list){
       found = false;

       // create two threads, each search the half of the array
       // so that shall save time to half
       Thread t1 = new Thread(new Runnable(){
         @Override
         public void run() {
            // read one more index in case the size is not an even number
             // so it will exceed the middle in one -> no problem at all
             for(int i=0; i<=(list.size()/2)+1; i++){ 
                   if(list.get(i).active) {
                       found = true;
                       finishFirst = true;
                       break; 
                   }
             } 
             finishFirst = true; // in case did not find any 
         }  
       });

       // second thread the same, but read from the end to the middle 
       Thread t2 = new Thread(new Runnable(){
             public void run() {
                 for(int i=list.size()-1; i>=list.size()/2; i--){
                       if(list.get(i).active) {
                           found = true;
                           finishSecond = true;
                           break; 
                    }
                 }
                 finishSecond = true;
            }      
       });

       // start both thread
       t2.start();
       t1.start();

       // while one of them has not finished yet
       while(!finishFirst || !finishSecond){
        // but in case not finished looping but found an active user
           // break the loop
               if(found){break;} 
        }

       return found; // return the result
   } 
} 

Test

End of Adding 1000000 User
Found Any Active: true
31 MilliScond

Answer 3

You may use Collections ArrayDeque. ArrayDeques will use half of the iteration to find the active user. In your case

ArrayDeque sample = new ArrayDeque(userList);

    for(int i=0;i<sample.size();i++){
                if(sample.pollFirst().status.equalsIgnoreCase("A")) {
                    break;
                }

                if(sample.pollLast().status.equalsIgnoreCase("A")) {
                    break;
                }
                if(sample.size()==0) break;

            }

Answer 4

I would certainly think about using Java 8 Lambda. I have written an example class:

package com.chocksaway;

import java.util.ArrayList;
import java.util.List;

/**
* Author milesd on 05/06/2017.
*/

class Name {
    private String name;
    private Boolean status;

    public Name(String name, Boolean status) {
        this.name = name;
        this.status = status;
    }


    public String getName() {
        return name;
    }

    public Boolean getStatus() {
        return status;
    }
}

public class FindFirstInStream {
    public static void main(String[] args) {
        List<Name> userList = new ArrayList<>();

        userList.add(new Name("James", false));
        userList.add(new Name("Eric", true));
        userList.add(new Name("David", false));

        Name firstActiveName = userList.stream()
            .filter(e -> e.getStatus().equals(true))
            .findFirst()
            .get();

        System.out.println(firstActiveName.getName());
    }
}

---

I've created a Name class, with name, and status.

I populate a userList with James, Eric, and David.

I use Java 8 stream to filter, and return the first "active" name (Eric).

This is stored in "firstActiveName".

Answer 5

The efficient way is to do that filter with SQL if you are using that. Select just the active users....

When you have all that list to work with java it will be slow as hell and there is no magic here, you will need to iterate.

public User getActiveUserFromList(userList) {
  for (User user : userList) {
    if (user.isActive()) {
      return user;
    }
    return null;
  }
}

If you have that list anyway ordered you can try to hack it, let's assume it is ordered by active status

public Boolean isAnyActive(userList) {
   if (userList.first().isActive()) { // try first
     return true;
   }
   if (userList.last().isActive()) {  // if its ordered and there is an active user, the last surely will be active, since first wasn't
     return true;
   }
   return false;
}

Answer 6

Java 8 solution with method reference:

userList.stream().filter(User::isActive).findFirst()

It'll return Optional so you could map over it.