CODEWITHSUNDEEP
javaperformancearraylist
Niko
Niko

Reputation: 8153

Java iteration for possible matches in ArrayList

My question is about iteration and performance. Let's think of following case:

public class Car {

    private String name;
    private int type;
    private int horsePower;

    String getKey() {
        return type + "_" + horsePower;
    }

    private final int NUM_OF_CARS = 50000;

    public void test() {
        List<Car> cars = new ArrayList<Car>(NUM_OF_CARS);

        for (int i = 0; i < NUM_OF_CARS; i++) {
            Car c = new Car();

            if (i == 0 || i == 176 || i == 895 || i == 1500 || i == 4600) {
                c.name = "Audi A4 " + i;
                c.type = 1;
                c.horsePower = 200;
            } else {
                c.name = "Default";
                c.type = 2 + i;
                c.horsePower = 201;
            }

            cars.add(c);
        }

        // Matches should contain all Audi's since they have same type and horse
        // power

        long time = SystemClock.currentThreadTimeMillis();

        HashMap<String, List<Car>> map = new HashMap<String, List<Car>>();

        for (Car c : cars) {
            if (map.get(c.getKey()) != null) {
                map.get(c.getKey()).add(c);
            } else {
                List<Car> list = new ArrayList<Car>();
                list.add(c);
                map.put(c.getKey(), list);
            }
        }

        Iterator<Entry<String, List<Car>>> iterator = map.entrySet().iterator();

        while (iterator.hasNext()) {
            if (iterator.next().getValue().size() == 1) {
                iterator.remove();
            }
        }

        Log.d("test", String.valueOf((SystemClock.currentThreadTimeMillis() - time)));
    }
}

Is this the most efficient way of finding all Audi's here?

This took me 1700 ms

Thanks.

Upvotes: 1

Views: 129

Answers (4)

Zied Hamdi
Zied Hamdi

Reputation: 2660

Use Hashing collections: HashSet that uses Object.hashCode() and Object.equals() to optimize search. How?

You must define your implementation of MyClass.hashCode() and equals(). hashCode() gives an integer representation of your object (you can do what you want here, but do it in a way where two different objects have different values)

HashSet will then do a modulo on your result ex: if the HashSet size is 5000 it will do a modulo 5000 and it will find the index where to put your object ex: if your hashCode() returns 10252, then 10252 % 5000 = 252. And your object will be put in an array with the index 252.

Finally, when you will ask (do I have an instance of "BMW x6", the object you ask for will have its hashCode() method called, which will return 10252 again. And HashSet will only search if it has an object in the 252 index.

If ever two objects give the same hashCode, then they will be compared through the equals() method.

I hope my explanations were clear. In short implement hashCode and equals() and try making the implementation of hashCode() optimized so you will gain time when filling your HashSet

You will probably also be interested in HashMap which stores keys and values where keys use the hashing mechanism: so you can find an object by its key

Upvotes: 0

Anastasios Vlasopoulos
Anastasios Vlasopoulos

Reputation: 1802

If you want to find a String you should use HashMap. Otherwise you cannot avoid that type of iterations as far as i have in mind.

Upvotes: 0

Ari&#224;
Ari&#224;

Reputation: 914

Why don't you try (Map):

http://docs.oracle.com/javase/7/docs/api/java/util/Map.html

Basically it's a collection of Hashmaps: http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html

Here's an example:

  Map<String, List<Car>> map = new HashMap<String, List<Car>>();

Upvotes: 1

Kevin Workman
Kevin Workman

Reputation: 42176

It depends why you're iterating. If you really do need to visit every bottom-level Car, then you don't really have a choice. However, if you're looking for specific matches to the String, then you might consider using a Map.

Upvotes: 1

Related Questions