List merge individually each cell

2
votes

Let's say I have 2 lists defined like that :

  • A[0] = [A01, A02]
  • A[1] = [A11, A11]
  • A[2] = [A21, A21]
  • B[0] = [B01, B01]
  • B[1] = [B11, B11]
  • B[2] = [B21, B21]

I want to generate an ouput single list like that :

  • O[0] = {A01, A02, B01, B02}
  • O[1] = {A01, A02, B11, B12}
  • O[2] = {A01, A02, B21, B22}
  • O[3] = {A11, A12, B01, B02}
  • O[4] = {A11, A12, B11, B12}
  • O[5] = {A11, A12, B21, B22}
  • O[6] = {A21, A22, B01, B02}
  • O[7] = {A21, A22, B11, B12}
  • O[8] = {A21, A22, B21, B22}

So far I'm doing it with 2 loops on each list and create a new list by combining each values from the loop.

List<Map<String, Object>> newList = new ArrayList<>();
for (Map<String, Object> originalData : originalDatas) {
    for (Map<String, Object> duplicateData : duplicateDatas) {
        Map<String, Object> newData = new HashMap<>();
        newData.putAll(originalData);
        newData.putAll(duplicateData);
        newList.add(newData);
    }
};

This is working fine as long as we don't have a lot of data.

However if both lists have ~10000 entries, it will take a long time to run.

If anyone have an idea about how to improve running time ?

Thanks for your help.

2
javaalgorithm

2 Answers

1
votes

The way you are currently doing it is the most efficient way I know of. The number of possibilities is n^2 (if the lists are of the same size) or n * m (if they are different); therefore, it has a runtime of O(n^2) or O(n * m) and as you add more variables the run time should grow exponentially.

1
votes

You can try a parallel merging. I can't say exactly how much the performance will be improved in your particular case. But it's worth a try:

List<Map<String, Object>> newList = Arrays.asList(originalData, duplicateData)
                        .stream()
                        .parallel()
                        .map(m -> m.entrySet().stream()
                             .collect(Collectors.toMap(k->k.getKey(), v->v.getValue())))
                        .collect(Collectors.toList());

Of course, this approach will only work with Java 8 and later.