Java, searching within a list of objects?

Question

I'm a bit lost on the way to make this happen the fastest. I have a large list of objects that have basic variable attributes (with getters / setters) and I need to do a search in this list to find the objects within the list that match a given parameter

I have found how to do a regular list search but I need to, for example search for the value of the result of doing a call getName() for each object in the list and get objects that have a result that matches my input.

Something like below where the third argument is the result of the method call and the second is what I am trying to find.

   int index = Collections.binarySearch(myList, "value", getName());

Any advice is appreciated

Answer 1

Take a look at the binarySearch that takes a comparator:

public static int binarySearch(List list, T key, Comparator c)

So you would do something like:

class FooComparator
    implements Comparator<Foo>
{
    public int compare(T a, T b)
    {
        return (a.getName().compareTo(b.getName());
    }
}

int index = Collections.binarySearch(myList, "value", new FooComparator());

You will need to first sort the list of course (Collections.sort takes a Comaprator as well...).

Answer 2

If you just as a one-off operation need to find the object(s) whose getName() is a particular value, then there's probably not much magic possible: cycle through the list, call getName() on each object, and for those that match, add them to your list of results.

If getName() is an expensive operation and there's some other way of a-priori working out if a given object definitely won't return a matching value, then obviously you can build in this 'filtering' as you cycle through.

If you frequently need to fetch objects for a given getName(), then keep an index (e.g. in a HashMap) of [result of getName()->object -> list of matches]. You'll need to decide how and if you need to keep this "index" in synch with the actual list.

See also the other proposition to use binarySearch() but to keep the list maintained. This way, inserts are more expensive than with a map and unsorted list, but if inserts are infrequent compared to lookups, then it has the advantage of only needing to maintain one structure.

Answer 3

I know anonymous inner classes are not fashion anymore, but while Java 8 arrives, you can create something like this:

1.- Create a search method that iterates the collection and pass an object that tells you if your object is to be returned or not.

2.- Invoke that method and create an anonymous inner class with the criteria

3.- Get the new list in separate variable.

Something like this:

result = search( aList, new Matcher(){ public boolean matches( Some some ) { 
  if( some.name().equals("a")) { 
     return true;
  }
}});

Here's a working demo:

import java.util.*;
class LinearSearchDemo { 
  public static void main( String ... args ) { 
      List<Person> list = Arrays.asList(
                                  Person.create("Oscar", 0x20),
                                  Person.create("Reyes", 0x30),
                                  Person.create("Java", 0x10)
                          );

      List<Person> result = searchIn( list, 
              new Matcher<Person>() { 
                  public boolean matches( Person p ) { 
                      return p.getName().equals("Java");
              }});

      System.out.println( result );

      result = searchIn( list, 
              new Matcher<Person>() { 
                  public boolean matches( Person p ) { 
                      return p.getAge() > 16;
              }});

      System.out.println( result );

  }
  public static <T> List<T> searchIn( List<T> list , Matcher<T> m ) { 
      List<T> r = new ArrayList<T>();
      for( T t : list ) { 
          if( m.matches( t ) ) { 
              r.add( t );
          }
      }
      return r;
  }
}

class Person { 
  String name;
  int age;

  String getName(){ 
      return name;
  }
  int getAge() { 
      return age;
  }
  static Person create( String name, int age ) { 
      Person p = new Person();
      p.name = name;
      p.age = age;
      return p;
  }
  public String toString() { 
      return String.format("Person(%s,%s)", name, age );
  }    
}
interface Matcher<T> { 
  public boolean matches( T t );
}

Output:

[Person(Java,16)]
[Person(Oscar,32), Person(Reyes,48)]

Answer 4

To do this in a more scalable way, without simply iterating/filtering objects, see this answer to a similar question: How do you query object collections in Java (Criteria/SQL-like)?

Answer 5

If the objects are immutable (or you at least know their names won't change) you could create an index using a HashMap.

You would have to fill the Map and keep it updated.

Map map = new HashMap();

map.put(myObject.getName(), myObject);
... repeat for each object ...

Then you can use map.get("Some name"); to do lookup using your index.

Answer 6

One library I'm familiar with is Guava -- you can compose its Predicate to pull out items from an Iterable. There's no need for the collection to be pre-sorted. (This means, in turn, that it's O(N), but it's convenient.)