Efficient way to find duplicate items among lists in Groovy

user_968831 0
Viewed 91

I have groovy map built in following manner :

list1 = [ "val1" "val2" "val3" ]
list2 = [ "val7" "val8" ]
list3 = [ "val4" "val5" "val2" ]
list4 = [ "val6" "val4" "val3" ]
map["key1"] = list1
map["key2"] = list2
map["key3"] = list3
map["key4"] = list4

I need to iterate through map and compare each list with another lists in the map and if any of the item from a list matches with item with any of other list then throw an error for e.g. in above case,as list1's value ( val2 ) matches with list3, so it should throw an error and stop processing further in the map.

I can intersect 2 lists to find the duplicates but for this I may need to iterate over the map twice, for e.g. for each key , fetch the values and then iterate again the map to fetch lists for other keys and intersect one by one from first list to find the duplicates OR something similar along this direction but that would not be an efficient way to achieve this.

Can this be achieved in more efficient way in groovy?

jenkins-groovy groovy
3 Answers

How about something like the below using disjoint

def list1 = [ "val1", "val2" ,"val3" ]
def list2 = [ "val7", "val8" ]
def list3 = [ "val4", "val5", "val24" ]
def list4 = [ "val6", "val4", "val3" ]

def map = [:]

map["key1"] = list1
map["key2"] = list2
map["key3"] = list3
map["key4"] = list4

def merged = []

map.each { key, val ->
    println "KEY: $key VAL: $val"
    if(!merged.disjoint(val)) {
         throw new Exception("Duplicates!!!")
    }
    merged.addAll(val) 
}

Here the time complexity of disjoint is O(n). Also, it's worth noting that between two lists a and b if a.size() < b.size() the time complexity will be O(a).

user_26270180

Iterating each element of a list over all elements of another list is O(n^2)

Instead, sort the lists. This O(n.log(n)).

You can then iterate over all the lists at the same time in O(n)

So asymptotically, the algorithm is going to be O(n.log(n))

If n is small, there may be a smarter way to do this, in particular if one of the list is really small. In that case the “brute force” algorithm in O(n^2) may fail faster on average, but, in any case, if n is small, optimizing is not worth: program what is the easiest to understand by the maintainer.

user_12639420

I would put them into a List. You'd only have to loop through the list of Strings once. As you are putting the items into the List first do a check to see if the item is in the list.

import java.util.ArrayList;
import java.util.List;

public class Main {

    List<String> mergedList = new ArrayList<>();
    public String stringList1[] = { "12q3", "21351", "1312", "12331", "34554", "cfA23" };
    public String stringList2[] = { "12ASD3", "21351", "13\32", "12F331", "345D4", "cfF23" };

    public static void main(String args[]) {
        Main main = new Main();
        main.start();
    }

public void start() {
    List<String[]> listOfLists = new ArrayList<>();
    listOfLists.add(stringList1);
    listOfLists.add(stringList2);

    for (String[] strings : listOfLists) {
        checkForDuplicates(strings);
    }

}

public void checkForDuplicates(String[] listOfStrings) {
    for (String currentString : listOfStrings) {
        if (mergedList.contains(currentString)) {
            System.out.println("Duplicated Item:currentString");
            continue;
        }
        System.out.println("Added:" + currentString);
        mergedList.add(currentString);
    }

}
}
user_11511440
Related