fork(4) download
copy 
  1. import java.util.*;
  2. import java.util.function.BinaryOperator;
  3. import java.util.stream.Collectors;
  4. import java.util.stream.IntStream;
  5.  
  6. class Ideone
  7. {
  8.     static class RecordingEntity {
  9.         int size, ops;
  10.  
  11.         RecordingEntity(int size) {
  12.             this.size = size;
  13.         }
  14.         RecordingEntity concat(RecordingEntity e) {
  15.             RecordingEntity result = new RecordingEntity(size + e.size);
  16.             // the costs of each construction scale with the result size
  17.             result.ops = ops + e.ops + result.size;
  18.             return result;
  19.         }
  20.     }
  21.  
  22.     public static void main(String[] args) {
  23.         List<RecordingEntity> input = IntStream.of(10, 20, 5, 15, 7, 3, 25)
  24.             .mapToObj(RecordingEntity::new)
  25.             .collect(Collectors.toList());
  26.  
  27.         System.out.println("naive concatenation");
  28.         {
  29.             RecordingEntity r = input.stream().reduce(RecordingEntity::concat).get();
  30.             System.out.println("String of length "+r.size+", constructed in "+r.ops+" operations");
  31.         }
  32.         System.out.println("exploiting associativity (using combiner)");
  33.         {
  34.             RecordingEntity r = splitReduce(input, RecordingEntity::concat);
  35.             System.out.println("String of length "+r.size+", constructed in "+r.ops+" operations");
  36.         }
  37.     }
  38.     static <T> T splitReduce(List<T> list, BinaryOperator<T> reduce) {
  39.         if(list.size() > 3) {
  40.             int mid = list.size() >>> 1;
  41.             return reduce.apply(
  42.                 splitReduce(list.subList(0, mid), reduce),
  43.                 splitReduce(list.subList(mid, list.size()), reduce));
  44.         }
  45.         return list.stream().reduce(reduce).get();
  46.     }
  47. }
Success #stdin #stdout 0.14s 37240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
naive concatenation
String of length 85, constructed in 317 operations
exploiting associativity (using combiner)
String of length 85, constructed in 250 operations
https://ideone.com/0kRRnt
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!