Fast way to compare String[] to List

Question

I would like to compare String arrays to a list with market objects.

I implemented the code like that:

private List<Data> addMarketData(List<Data> list) {
    String[] SEE = new String[]{"Albania", "Bosnia and Herzegovina", "Bulgaria", "Croatia", "Macedonia FYR", "Moldavia", "Montenegro", "Romania", "Serbia", "Slovenia" };
    List<String> seeList = Arrays.asList(SEE);
    String[] CEE = new String[]{"Czech Republic", "Hungary", "Poland", "Slovakia"}; 
    List<String> ceeList = Arrays.asList(CEE);
    for (int i = 0; i < list.size(); i++) {
        for (int j = 0; j < seeList.size(); j++) {
            if(list.get(i).getPropertyCountry().equals(seeList.get(j).toString())) {
                list.get(i).setMarket("SEE");
            }   
        }
        for (int k = 0; k < ceeList.size(); k++) {
            if(list.get(i).getPropertyCountry().equals(ceeList.get(k).toString())) {
                list.get(i).setMarket("CEE");
            }   
        }
    }
    return list;
}

However, I believe that this code produces more overhead than it really should. Especially the for loops. Could I just use one loop?

Therefore, how to make this piece of code much faster?

I appreciate your answer!

How check with `contains()` like `seeList.contains()` iterating just data list.? — Wundwin Born, Sep 01 '14 at 09:04

score 7 · Accepted Answer · edited May 23 '17 at 12:05

Move all the data into a Set<String>:

String[] SEE = ...
Set<String> setSEE = new HashSet<>(Arrays.asList(SEE));
String[] CEE = ...
Set<String> setCEE = new HashSet<>(Arrays.asList(CEE));
for (Data data : list) {
    if (setSEE.contains(data.getPropertyCountry()) {
        data.setMarket("SEE");
    } else if (setCEE.contains(data.getPropertyCountry()) {
        data.setMarket("CEE");
    }
}

This won't generate the overhead you may think. Also, it is faster than your current O(N^2) approach.

Another idea is to move the data of these arrays into a Map<String, String> as proposed by @Narmer, but in this case you should define a value when the country is not found as key in the map.

Since Java 7, you can use diamond operator. For Java 5 and 6, you have to specify the whole generics usage:

Set<String> setSEE = new HashSet<String>(Arrays.asList(SEE));
//...
Set<String> setCEE = new HashSet<String>(Arrays.asList(CEE));

@Vivien the search of the `String` in the `Set` is O(1), but since you're searching all the elements of `list` in both sets, it's O(N) where N is the size of list. — Luiggi Mendoza, Sep 01 '14 at 09:24
btw I am also getting `'<>' operator is not allowed for source level below 1.7`, any recommendations for that? — Carol.Kar, Sep 01 '14 at 09:25

Willem Van Onsem · Answer 2 · 2014-09-01T11:20:08.303

1

Well you can simply use two HashSet<String> collections to store the name of the countries in. A HashSet<String> performs lookups in approximately O(1) time per item, this O(n) for the entire array. Or you could use one HashMap<String,String> to perform lookups resulting in "SEE" or "CEE".

Example

Map<String,String> lut = new HashMap<String,String>();
for(String s : new String[]{"Albania", "Bosnia and Herzegovina", "Bulgaria", "Croatia", "Macedonia FYR", "Moldavia", "Montenegro", "Romania", "Serbia", "Slovenia" }) {
    lut.put(s,"SEE");
}
for(String s : new String[]{"Czech Republic", "Hungary", "Poland", "Slovakia"}) {
    lut.put(s,"CEE");
}

for (Data data : list) {
    data.setMarket(lut.get(data.getPropertyCountry()));
}

The generation of the HashMap<String,String> (and putting data into it) should only be executed once (at startup). This will increase performance with a factor equal to the number of elements you put into the HashMap<String,String> (in this case 14).

edited Sep 01 '14 at 11:20

answered Sep 01 '14 at 09:05

Willem Van Onsem

443,496
30
428
555

I recommend you to pay a read to this: [What does it mean to “program to an interface”?](http://stackoverflow.com/q/383947/1065197) – Luiggi Mendoza Sep 01 '14 at 09:12
You mean one better uses a `Map` instead of a `HashMap`? True if the instances are public. But if they are stored privately, there is not that much to gain. – Willem Van Onsem Sep 01 '14 at 09:15
You will never know when the requirement can change. So, it is better to declare the variable as the top interface or (abstract) class and initialize it with the proper class implementation. – Luiggi Mendoza Sep 01 '14 at 09:16
Well, it would be better if Java, like C# would implement a `var` keyword: this keyword tries to determine the type at compile time. Thus one does not pay a performance price (possibly) and still can modify the code without having to worry about types. – Willem Van Onsem Sep 01 '14 at 09:17
Maybe someday it would be available in Java as well. But today, it is what we have in Java (for good or not). – Luiggi Mendoza Sep 01 '14 at 09:19

Narmer · Answer 3 · 2014-09-01T09:26:28.233

You could use a Map instead of list.

private static final Map<String, String> markets = new HashMap<String,String>(){{
    put("Albania", "SEE");
    put("Bosnia and Herzegovina", "SEE");
    ...
    put("Hungary", "CEE");
    ...
}}

Then consult it

for(Data data: list){
    data.setMarket(markets.get(data.getPropertyCountry()));
}

EDIT

As per the comments, the above is the optimal situation. You should check that data.getPropertyCountry() is not null (if permitted) and that the value returned by the list ins't null either:

for(Data data: list){
    if(data.getPropertyCountry()!=null){
        String market = markets.get(data.getPropertyCountry());
        data.setMarket(market==null?"default market":market);
    }
    else data.setMarket("default value"); //if needed
}

Or using the beatiful Java 8 stream interface:

for(Data data: list.stream().filter(p -> p.getPropertyCountry() != null).collect(Collectors.toList())){
    String market = markets.get(data.getPropertyCountry());
    data.setMarket(market==null?"default market":market);
}

The only downside of this approach is when there's no key for the `PropertyCountry` field of the data. — Luiggi Mendoza, Sep 01 '14 at 09:11
Yes, a `null` check has to be made also when getting the value from the map if the key doesn't exists. — Narmer, Sep 01 '14 at 09:12

score 1 · Answer 4 · answered Sep 01 '14 at 09:06

Define seeList and ceeList as HashSets and then use its contains() method. HashSet's contains() has constant time complexity.

Set<String> seeSet = new HashSet<>();
Collections.addAll(seeSet, SEE);

Set<String> ceeSet = new HashSet<>();
Collections.addAll(ceeSet, CEE);

And then:

for (int i = 0; i < list.size(); i++) {
    if (seeSet.contains(list.get(i).getPropertyCountry()) {
        list.get(i).setMarket("SEE");
    }

    if (ceeSet.contains(list.get(i).getPropertyCountry()) {
        list.get(i).setMarket("CEE");
    }
}

Fast way to compare String[] to List

4 Answers4