Search in a custom arraylist most efficient

Question

I have a List of custom class in which i want to search for some items via name or number without using any for loop because it have around 100000 items

class Contact{
    String name;
    String phone;
}

but iterating using a loop takes too long time to complete, is there any efficient way to do the same ??

public static void main(String[] args){
    String textToSearch = "name"; //or it can be number also
    List<Contact> list = new ArrayList<>();
    list.addAll(myOldListOfCustomContacts);
    for(Contact contact : list){
        if(contact.name.toLowerCase().contains(textToSearch) || contact.phone.toLowerCase().contains(textToSearch)){
            Log.e("TAG", "found");
        }
    }
}

before positing this question i searched it on StackOverFlow but didn't get my answer, like this Most efficient way to see if an ArrayList contains an object in Java

Answer 1

Not easy as you are searching for substrings somewhere inside your contact name or phone number. You need something that quickly reduces the million candidates to a manageable number.

If you don't find a library doing what you want, you can go for trigraph indexing. Let's explain the idea for the contact names (then the phone numbers are just a second incarnation of the same indexing).

Create a HashMap<String,List<Contact>> with trigraphs as key and multiple Contacts as values (those contacts that have the trigraph as substring of their names). So for every three-character substring (trigraph) from every contact name, add this Contact to the list under the trigraph key.

When you search for Contacts with a given substring, take the first three characters of the search string, and read the list from your map. This lookup will be fast and give you a small subset of the million original elements. Then sequentially check the Contacts you found in that subset for containing the full search string.

In addition to the main procedure, you probably need to support corner cases like names or search strings shorter than three characters. And depending on the typical search strings, maybe a more intelligent selection of the search trigraph gives better results than just taking the first three letters, e.g. an intersection of the results for all search-string trigraphs.

Answer 2

This solution uses an index list to help you use Collections.binarySearch().

/**
 * Adds indexing on a list of type C given a field accessor that can extract a field of type T from a C.
 * 
 * Please ensure your list is `RandomAccess`.
 */
class Index<C, T extends Comparable<T>>
        extends AbstractList<T> implements List<T>, RandomAccess {
    // The actual list.
    final List<C> actual;
    // My sorted index to the list.
    final List<Integer> index;
    // The getter to get a T from a C
    final Function<C, T> getter;

    public Index(List<C> actual, Function<C, T> getField) {
        this.actual = actual;
        getter = getField;
        // Start the index mapping i -> i
        index = IntStream.rangeClosed(0, actual.size() - 1).boxed().collect(Collectors.toList());
        // Sort it on the actual.
        Collections.sort(index, (o1, o2) -> get(o1).compareTo(get(o2)));
    }

    @Override
    public T get(int index) {
        // Translate all access through the index.
        return getter.apply(actual.get(this.index.get(index)));
    }

    @Override
    public int size() {
        return index.size();
    }

    // Finds all occurrences of thing.
    public List<C> find(T thing) {
        // Is it there at all?
        int where = Collections.binarySearch(this, thing);
        if (where >= 0) {
            // Step back to ensure we aren't in the middle of a run.
            while (where > 0 && get(where - 1).equals(thing)) {
                where -= 1;
            }
            // Gather the list.
            List<C> found = new ArrayList<>();
            while (where < index.size() && get(where).equals(thing)) {
                found.add(actual.get(index.get(where++)));
            }
            return found;
        } else {
            return Collections.EMPTY_LIST;
        }
    }
}

// For demo.
class Contact {
    final String name;
    final String phone;

    public Contact(String name, String phone) {
        this.name = name;
        this.phone = phone;
    }

    public String getName() {
        return name;
    }

    public String getPhone() {
        return phone;
    }

    @Override
    public String toString() {
        return "Contact{" +
                "name='" + name + '\'' +
                ", phone='" + phone + '\'' +
                '}';
    }
}

private void test(String[] args) {
    // Sample list.
    List<Contact> list = new ArrayList<>();
    list.add(new Contact("Me", "1234"));
    list.add(new Contact("You", "5678"));
    list.add(new Contact("Us", "6666"));
    list.add(new Contact("Many", "6666"));
    list.add(new Contact("Them", "9999"));
    list.add(new Contact("Them", "99999"));
    list.add(new Contact("Them", "999999"));

    // Build sorted indexes by name and phone.
    Index<Contact, String> byName = new Index<>(list, Contact::getName);
    Index<Contact, String> byPhone = new Index<>(list, Contact::getPhone);

    // Use binary search to find a name and a phone.
    int me = Collections.binarySearch(byName, "Me");
    System.out.println(me + " -> " + list.get(me));
    int six = Collections.binarySearch(byPhone, "6666");
    System.out.println(six + " -> " + list.get(six));
    System.out.println("Them -> " + byName.find("Them"));
    System.out.println("6666 -> " + byPhone.find("6666"));
}

Answer 3

1) You can sort your list by name or phone, after that search will be easier(binary search etc.)

2) If you have only unique contacts, you can break the loop when result is found.

3) If you have multiple contacts with the same name or phone try to sort list. and add a partition, like all contacts with name by A,B,C etc.

4) If you searching like "a", after that "an" , and after "ana". You can use sub lists. Like:

1 step: find all contacts with "a" and use result of it.

2 step: will search not from full list, you will search from result of step 1.

3 step: search from result of step 2.

the same will be with phone number.

Answer 4

You may use the good old Java's ThreadPoolExecutor.

Before I start, I suggest your read the other answers and comments, which pointed out useful data structures that should improve your search function without the need of multithreading utilities.

As @Xenolion mentioned, if you load your contacts from a database, consider querying directly into it without blocking your UI Thread.

If you go with the ThreadPoolExecutor, you are basically dividing your Array into smaller chunks that will each be processed by a Thread .

You can find an exhaustive example in the Android Docs.

You'll need to implement a Runnable class that will be assigned a partition of your data.

class Worker implements Runnable {

    // ...

    public Worker(final Contact[] data, final int start, final int end) {
         // have your workers hold a reference to the data array
         this.data = data;
         // ...
    }

    @Override public void run() {
         for (int i = this.start, i < this.end; i++) {
            if (this.data[i].contains(....) || ...) {
                this.notifySearchEnded(i);
                break;
            }
         }
         // found nothing...
    }

    private void notifySearchEnded(final int index) {
        // do whatever you want with the contact
        log("Runnable " + this.id + " has found the contact at index " + index);
        // hold somehow a reference to the executor
        EXECUTOR.shutdown(); // tell the executor to stop the other threads
    }
}

You'll then instantiate your ExecutorService and execute your Worker Threads.

    private static final int CORES = Runtime.getRuntime().availableProcessors();

    public static final ExecutorService EXECUTOR = Executors.newFixedThreadPool(CORES);

Split your array into smaller chunks.

final int dataSize = data.lenght; // let's say 76'513

final int step = (int) (dataSize / CORES); // 76'513 / 4 = 19128

for (int i = 0; i < CORES; i++) {
    final int start = i * step;
    // give the left-over data to the last thread
    final int end = (i == (CORES - 1)) ? (dataSize - 1) : (start + step - 1);
    EXECUTOR.execute(new Worker(this.data, start, end));
}

My example isn't very efficient though. The Android link mentioned above contains a better example which makes use of a dynamic number of thread and a timeout for the executor. Take my example as a basis and follow the docs for an optimized version.

More examples, here and (with Futures), here and here: