Which is the fastet and the most efficient implementation in java for updating object in a list if present, else add it

Question

I have a problem statement which is working but still i would like to know more efficient, faster and more importantly correctly designed to handle the below mentioned scenario.

I have a POJO class

class A {
  String s;
  Double d;
}

I am trying to populate a List, basically a List of Object A into the list. Now the implementation in question. While adding the Object A into the list i need to check if an Object with String s already exists. If yes i want to update the older Object with old d1 + new d1 and do not add the new Object to the list, If no add the new Object to the list. My present implementation is something like below.

double dd = 0.0;
    List<A> aList = new List<A>();
    List<A> aListToRemove = new List<A>();
    A newA = null;
    for(int i=0;i<=100;i++ ){
        newA = method call which returns newA;
        for(A oldA: aList ){
            if(oldA.getS().equals(newA.getS())){
                dd = oldA.getD() + newA.getD();
                newA.setD(dd);
                aListToRemove.add(oldA);
            }
            aList.add(newA);
            aList.removeAll(aListToRemove);
        }
    }

//at the end, i would like to see aList with no duplicates, but with updated d value.

Is there a more efficient way to do the processing within the second for loop?

Answer 1

It seems you could use a map for your use case:

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

and put items in the map like this:

map.put(someA.s, someA);

That should turn your O(n^2) algoritm into an O(n) algorithm.

When you receive a newA, you can use the following:

A a = map.get(newA.getS());
if (a == null) {
    map.put(newA.getS(), newA); //new string => new item in the map
} else {
    a.setD(a.getD() + newA.getD()); //found string => updating the existing item
}

Answer 2

You should really consider using a Map.

Answer 3

Does it have to be a List? It sounds like a Map could do the job for you. Specifically, the put() operation adds or replaces a key-value pair, which fits your semantics perfectly.

Cheers,

Answer 4

Consider using a Map. You can check if an item is in the map with the get method (it seems s would be the key):

A a = myMap.get(newA.getS());
if (a != null){
 a.setD(a.getD() + newA.getD());
} else {
 myMap.put(newA);
}

Answer 5

If you want efficiency, I would use a MultiMap or Map<String, List<String>> This will mroe more efficient to not only perform the lookup but the accumulation of data. If you need to append the String together, the best option could be to use a Map<String, double[]>

class A {
  String s;
  double d; // don't use Double unless you need null values.
}

Map<String, double[]> map = new LinkedHashMap<>();

for(A newA: getAs()) {
    double[] total = map.get(newA.getS());
    if (total== null)
        map.put(newA.getS(), total = new double[0]);
    total[0] += newA.getD();
}

This will give you O(1) lookup and accumulate the values with a minimum of object creation.

Answer 6

You should use a java.util.Set for your operations.

You can check the existence of your object in O(1) time and perform your operation accordingly.

It will also take care of removing the duplicates.

   double dd = 0.0;
    Set<A> aList = new HashSet<A>();
    A newA = null;
    for(int i=0;i<=100;i++ ){
        newA = //method call which returns newA;
        A oldA = aList.get(newA);
        if(oldA != null){
           aList.remove(oldA);
        }
        dd = oldA.getD() + newA.getD();
        newA.setD(dd);
        aList.add(newA);
    }

Please make sure you override your equals and hashcode() methods in class A which will be used by Set else the default implementation will be used