Merge 2 lists based on original ordering from the input list - JAVA

Question

I have a following function:

List<Pair<SomeObject, Integer>> process(List<SomeObject> input) {
   List<Pair<SomeObject, Integer>> result = new ArrayList<>();
   List<SomeObject> couldBeProcessed = new ArrayList<>();

   for (SomeObject obj : input) {
      if (couldBeProcessed(obj)) {
         couldBeProcessed.add(obj);
      } else {
         result.add(Pair.of(obj, 0));
      }
   }

   List<Pair<SomeObject, Integer>> processResult = processInBatch(couldBeProcessed); 
   // TODO: merge processResult with result here
}

How do I add this processResult into results but preserve the ordering as it was given to me in the input?

what are you creating the `Pair`s for? – Naman Feb 27 '20 at 19:14 — Naman, Feb 27 '20 at 19:14

Andronicus · Accepted Answer · 2020-02-27T20:04:19.440

2

How about using a map to hold the index and then good 'ol for loop:

List<Pair<SomeObject, Integer>> process(List<SomeObject> input) {
   List<Pair<SomeObject, Integer>> result = new ArrayList<>();
   Map<Integer, Pair<SomeObject, Integer>> map = new HashMap();
   List<SomeObject> couldBeProcessed = new ArrayList<>();

   for (int i = 0; i < input.size(); i++) {
      if (couldBeProcessed(input.get(i))) {
         couldBeProcessed.add(obj);
      } else {
         map.put(i, Pair.newInstance(obj, 0));
      }
   }

   List<Pair<SomeObject, Integer>> processResult = processInBatch(couldBeProcessed); 

   for (int i = 0; i < input.size(); i++) {
      if (map.containsKey(i)) {
         result.add(map.get(i));
      } else {
         result.add(processResult.remove(0));
      }
   }
}

You can also use Map#computeIfAbsent to make the second loop more compact:

for (int i = 0; i < input.size(); i++) {
    result.add(map.computeIfAbsent(i, index -> processResult.remove(0));
}

P.S.: The elements of processResult must have the same indices as respective objects from the original list.

@Misha suggests a more natural way to handle the processed queue - by using Deque:

Deque<Pair<SomeObject, Integer>> processResult = new ArrayDeque(processInBatch(couldBeProcessed)); 

for (int i = 0; i < input.size(); i++) {
    if (map.containsKey(i)) {
        result.add(map.get(i));
    } else {
        result.add(processResult.removeFirst());
    }
}

edited Feb 27 '20 at 20:04

answered Feb 27 '20 at 19:04

Andronicus

25,419
17
47
88

I really like this idea especially using `computeIfAbsent`. Thank you! I will use this. – test123 Feb 27 '20 at 19:32
1

@test123 I am superhappy I could help! Have a great day! – Andronicus Feb 27 '20 at 19:33
1

Instead of repeatedly calling `remove(0)` it's better to make `Deque<...> que = new ArrayDeque<>(processResult);`. Then you call `que.removeFirst()`, which will then avoid moving the entire backing array on every call. – Misha Feb 27 '20 at 19:46
@Misha yes, that feels much better, thank you. I have added that note in my answer, I hope it's ok – Andronicus Feb 27 '20 at 19:49
1

@Andronicus Please use `ArrayDeque` instead of `LinkedList`. See https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist and other linked answers. – Misha Feb 27 '20 at 19:58
@Misha huh, I didn't know that, thank you very much! – Andronicus Feb 27 '20 at 20:04
@Andronicus we can still use `computeIfAbsent`, is that correct? – test123 Feb 28 '20 at 00:52
@Misha thank you! One question though: Why `Deque`? Could I use `Queue` instead? Since I don't really need to remove from last? – test123 Feb 28 '20 at 00:55
1

@test123 Sure. Makes no difference. – Misha Feb 28 '20 at 20:41

score 0 · Answer 2 · answered Feb 27 '20 at 19:23

Few suggestions possible with the current implementations inlined:

List<Pair<SomeObject, Integer>> process(List<SomeObject> input) {

    // use an index map if the initial order matters
    Map<SomeObject, Integer> indexMap = IntStream.range(0, input.size())
            .boxed()
            .collect(Collectors.toMap(input::get, Function.identity()));

    // to split to either 'true' or 'false' you can use partitioning 
    Map<Boolean, List<SomeObject>> partitioned = input.stream()
            .collect(Collectors.partitioningBy(this::couldBeProcessed));

    List<Pair<SomeObject, Integer>> result = partitioned.get(Boolean.FALSE).stream()
            .map(some -> Pair.of(some, 0))
            .collect(Collectors.toList());

    List<SomeObject> couldBeProcessed = partitioned.get(Boolean.TRUE);

    List<Pair<SomeObject, Integer>> processResult = processInBatch(couldBeProcessed);

    // while merging use the index from initial phases
    return Stream.concat(processResult.stream(), result.stream())
            .sorted(Comparator.comparing(e -> indexMap.get(e.getLeft())))
            .collect(Collectors.toList());
}

Though the point of using Pair is still unclear in your complete approach and you might be able to get rid of it as well.

I can't create `Map` unfortunately because of performance issues. `SomeObject` is very expensive to compute `hashCode`. Should've mentioned this in my original question. — test123, Feb 27 '20 at 19:34

Merge 2 lists based on original ordering from the input list - JAVA

2 Answers2