1

If element less then given that move to left if more then move to right. Simple code with java 7 style:

private static <T extends Comparable> List<T> doAction(List<T> original, T state) {
    List<T> left = new ArrayList<T>();
    List<T> fight = new ArrayList<T>();
    for (T e : original) {
        if (e.compareTo(state) < 0) {
            left.add(e);
        } else {
            fight.add(e);
        }
    }
    left.addAll(fight);
    return left;
}

How to rewrite code above to java 8 stream style with using parallel stream?

Nicolas Filotto
  • 43,537
  • 11
  • 94
  • 122
Alstresh
  • 583
  • 2
  • 4
  • 16

2 Answers2

4

One approach, being equivalent to your original code, would be:

private static <T extends Comparable<T>> List<T> doAction(List<T> original, T state) {
    Map<Boolean, List<T>> collect = original.parallelStream()
        .collect(Collectors.partitioningBy(e -> e.compareTo(state) < 0));
    List<T> left = collect.get(true);
    List<T> right = collect.get(false);
    return Stream.of(left, right).flatMap(List::stream).collect(Collectors.toList());
}

However, since you only partition the data, to join them afterwards, a simpler solution would be:

private static <T extends Comparable<T>> List<T> doAction(List<T> original, T state) {
    return original.parallelStream()
        .sorted(Comparator.comparingInt(e -> Integer.signum(e.compareTo(state))|1))
        .collect(Collectors.toList());
}

But note that in either case, you need a rather big source list to benefit from parallel execution.

Note that the second approach can be even performed in-place, in case the original List is mutable (and you don’t need the original order anymore):

original.sort(Comparator.comparingInt(e -> Integer.signum(e.compareTo(state))|1));
Holger
  • 285,553
  • 42
  • 434
  • 765
  • does it really help to create a new Stream with 2 lists to build a single list? why not simply left.addAll(right);return left;? – Nicolas Filotto May 26 '16 at 14:05
  • 1
    @Nicolas Filotto: because `left` is not guaranteed to be a mutable list. In the current implementation, it’s an `ArrayList`, but that may change. You would have to use the more complicated collector `Collectors.partitioningBy(…, Collectors.toCollection(ArrayList::new))` to be sure that you can call `addAll` on the result lists. However, unless you have a very small `right` list, it’s the unlikely that the capacity of `left` is sufficient for that subsequent `addAll`, so the number of copying operations performed under the hood does not change. So I kept the collector simple. – Holger May 26 '16 at 14:36
  • 1
    Alternatively, you could say `left=new ArrayList<>(left); left.addAll(right);` or, if performance matters, `result=new ArrayList<>(left.size()+right.size()); result.addAll(left); result.addAll(right);`, as said, I just wanted to keep it simple. I’d prefer the second variant anyway. – Holger May 26 '16 at 14:40
  • Yes the second approach is better indeed as we know the size of the resulting list so it will be faster, I know that later we could get an immutable list but my point was only to avoid over using Streams even for trivial op like appending 2 lists. – Nicolas Filotto May 26 '16 at 14:46
  • "if all you have is a hammer, everything looks like a nail" :-) – Nicolas Filotto May 26 '16 at 14:47
  • @Nicolas Filotto: well, I thought about “how to add/concat two lists of unknown mutability” and came to the conclusion, that the stream way isn’t worse than any other solution. So I wouldn’t call it “overusing”. – Holger May 26 '16 at 14:55
2

Although Holger answer is great, you (or other readers) might be interested in writing your own Collector or to know how would you write one.

Firstly, you you need a way to represent partial results 

static class PartialResult<T extends Comparable<T>>  {
    public List<T> left = new ArrayList<>();
    public List<T> right = new ArrayList<>();
}

And now we define our own Collector,

  static class PartitionCollector<T extends Comparable<T>> implements Collector<T,PartialResult<T>,List<T>>{

    private final T pivot;

    public PartitionCollector(T pivot){
      this.pivot = pivot;
    }

    @Override
    public Supplier<ResultPair<T>> supplier() {
        return ResultPair::new;
    }

    @Override
    public BiConsumer<PartialResult<T>, T> accumulator() {
        return  (result, e) -> {
        if (e.compareTo(pivot) < 0) {
              result.left.add(e);
          }else {
              result.right.add(e);
          }
        };
    }

    @Override
    public BinaryOperator<PartialResult<T>> combiner() {
        BinaryOperator<PartialResult<T>> mergeOp = (r1,r2) ->{
           r1.left.addAll(r2.left);
           r1.right.addAll(r2.right);
           return r1;
        };
        return mergeOp;
    }

    @Override
    public Function<PartialResult<T>, List<T>> finisher() {
        Function<PartialResult<T>,List<T>> finisher = r -> {
            List<T> finalResult = new ArrayList<>(r.left.size() + r.right.size());
            finalResult.addAll(r.left);
            finalResult.addAll(r.right);
            return finalResult;
        };
        return finisher;
    }

    @Override
    public Set<Characteristics> characteristics() {
        return Collections.unmodifiableSet(EnumSet.of(Characteristics.CONCURRENT));
    }
}
  1. The supplier is easy, we just need to tell it to create a new instance.
  2. accumulator, given an element, we put it in its part accordingly.
  3. combiner, we have two partial results ( multi-threads computed two branches of our solution tree), combine them into one.
  4. finsiher, at the end, I want a full list and not a partial solution.
Sleiman Jneidi
  • 22,907
  • 14
  • 56
  • 77
  • 2
    Note that the combiner is allowed to modify one of its arguments and return that, so instead of creating a new `ResultPair`, you could simply do `(r1,r2) -> { r1.left.addAll(r2.left); r1.right.addAll(r2.right); return r1; }`. Further, the accumulator can be simplified to `(result, e) -> (e.compareTo(pivot)<0? result.left: result.right).add(e)` – Holger May 26 '16 at 14:48