CODEWITHSUNDEEP
javaalgorithm
Carol.Kar
Carol.Kar

Reputation: 5355

Fast way to compare String[] to List

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!

Upvotes: 4

Views: 567

Answers (4)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476699

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).

Upvotes: 1

Luiggi Mendoza
Luiggi Mendoza

Reputation: 85779

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));

Upvotes: 7

Narmer
Narmer

Reputation: 1454

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);
}

Upvotes: 1

Natix
Natix

Reputation: 14257

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");
    }
}

Upvotes: 1

Related Questions