Gruppe und reduzieren Liste der Objekte

Question

Ich habe eine Liste von Objekten mit vielen dupliziert und einige Felder, die zusammengeführt werden müssen. Ich möchte dies auf eine Liste von einzigartigen Objekten reduzieren, die nur Java 8 Streams verwenden (ich weiß, wie man das über Old-Skool macht, aber das ist ein Experiment.)

Dies ist, was ich gerade habe. Ich nicht wirklich mag, weil die Karte Bildung scheint fremd und die Werte() Sammlung eine Ansicht der Trägerkarte ist, und Sie müssen es in einem neuen ArrayList<>(...) wickeln eine spezifischere Sammlung zu erhalten. Gibt es einen besseren Ansatz, vielleicht die allgemeineren Reduktionsoperationen?

@Test 
public void reduce() { 
    Collection<Foo> foos = Stream.of("foo", "bar", "baz") 
        .flatMap(this::getfoos) 
        .collect(Collectors.toMap(f -> f.name, f -> f, (l, r) -> { 
         l.ids.addAll(r.ids); 
         return l; 
        })).values(); 

    assertEquals(3, foos.size()); 
    foos.forEach(f -> assertEquals(10, f.ids.size())); 
} 

private Stream<Foo> getfoos(String n) { 
    return IntStream.range(0,10).mapToObj(i -> new Foo(n, i)); 
} 

public static class Foo { 
    private String name; 
    private List<Integer> ids = new ArrayList<>(); 

    public Foo(String n, int i) { 
     name = n; 
     ids.add(i); 
    } 
} 

Answer 1

Wenn Sie die Gruppierung brechen und Schritte zu reduzieren, können Sie etwas Reiniger erhalten:

Stream<Foo> input = Stream.of("foo", "bar", "baz").flatMap(this::getfoos); 

Map<String, Optional<Foo>> collect = input.collect(Collectors.groupingBy(f -> f.name, Collectors.reducing(Foo::merge))); 

Collection<Optional<Foo>> collected = collect.values(); 

Dies setzt voraus, ein paar bequeme Methoden in Ihrer Foo Klasse:

public Foo(String n, List<Integer> ids) { 
    this.name = n; 
    this.ids.addAll(ids); 
} 

public static Foo merge(Foo src, Foo dest) { 
    List<Integer> merged = new ArrayList<>(); 
    merged.addAll(src.ids); 
    merged.addAll(dest.ids); 
    return new Foo(src.name, merged); 
} 

Answer 2

Wie bereits In den Kommentaren wurde darauf hingewiesen, dass eine Map eine sehr natürliche Sache ist, wenn man eindeutige Objekte identifizieren möchte. Wenn Sie nur die einzigartigen Objekte suchen müssten, könnten Sie die Methode Stream::distinct verwenden. Diese Methode verbirgt die Tatsache, dass es eine Karte beteiligt ist, aber anscheinend hat es intern eine Karte verwenden, wie this question angedeutet, das zeigt, sollten Sie eine hashCode Methode implementieren oder distinct möglicherweise nicht korrekt verhalten.

Bei der Methode distinct, bei der keine Zusammenführung erforderlich ist, können einige der Ergebnisse zurückgegeben werden, bevor die gesamte Eingabe verarbeitet wurde. In Ihrem Fall müssen Sie alle Eingaben abarbeiten, bevor Sie die Ergebnisse zurückgeben, es sei denn, Sie können zusätzliche Annahmen über die Eingabe treffen, die in der Frage nicht erwähnt wurden. Daher verwendet diese Antwort eine Karte.

Es ist leicht genug, um Streams zu verwenden, um die Werte der Karte zu verarbeiten und es in einen Arraylist zurück, though. Ich zeige, dass in dieser Antwort, sowie eine Möglichkeit bietet, das Auftreten einer Optional<Foo> zu vermeiden, die in einer der anderen Antworten auftaucht.

public void reduce() { 
    ArrayList<Foo> foos = Stream.of("foo", "bar", "baz").flatMap(this::getfoos) 
      .collect(Collectors.collectingAndThen(Collectors.groupingBy(f -> f.name, 
      Collectors.reducing(Foo.identity(), Foo::merge)), 
      map -> map.values().stream(). 
       collect(Collectors.toCollection(ArrayList::new)))); 

    assertEquals(3, foos.size()); 
    foos.forEach(f -> assertEquals(10, f.ids.size())); 
} 

private Stream<Foo> getfoos(String n) { 
    return IntStream.range(0, 10).mapToObj(i -> new Foo(n, i)); 
} 

public static class Foo { 
    private String name; 
    private List<Integer> ids = new ArrayList<>(); 

    private static final Foo BASE_FOO = new Foo("", 0); 

    public static Foo identity() { 
     return BASE_FOO; 
    } 

    // use only if side effects to the argument objects are okay 
    public static Foo merge(Foo fooOne, Foo fooTwo) { 
     if (fooOne == BASE_FOO) { 
      return fooTwo; 
     } else if (fooTwo == BASE_FOO) { 
      return fooOne; 
     } 
     fooOne.ids.addAll(fooTwo.ids); 
     return fooOne; 
    } 

    public Foo(String n, int i) { 
     name = n; 
     ids.add(i); 
    } 
} 

Answer 3

Wenn die Eingangselemente in der zufälligen Reihenfolge geliefert werden, dann Zwischen Karte ist, wahrscheinlich die beste Lösung. Allerdings, wenn Sie im Voraus wissen, dass alle die Foos mit dem gleichen Namen sind neben (diese Bedingung tatsächlich in Ihrem Test erfüllt ist), kann der Algorithmus stark vereinfacht werden: Sie brauchen nur das aktuelle Element mit dem vorherigen zu vergleichen und zusammenführen sie, wenn der Name derselbe ist.

Leider gibt es keine Stream-API-Methode, die Sie einfach und effektiv zu so etwas tun würde ermöglichen. Eine mögliche Lösung ist benutzerdefinierte Collector wie folgt zu schreiben:

public static List<Foo> withCollector(Stream<Foo> stream) { 
    return stream.collect(Collector.<Foo, List<Foo>>of(ArrayList::new, 
      (list, t) -> { 
       Foo f; 
       if(list.isEmpty() || !(f = list.get(list.size()-1)).name.equals(t.name)) 
        list.add(t); 
       else 
        f.ids.addAll(t.ids); 
      }, 
      (l1, l2) -> { 
       if(l1.isEmpty()) 
        return l2; 
       if(l2.isEmpty()) 
        return l1; 
       if(l1.get(l1.size()-1).name.equals(l2.get(0).name)) { 
        l1.get(l1.size()-1).ids.addAll(l2.get(0).ids); 
        l1.addAll(l2.subList(1, l2.size())); 
       } else { 
        l1.addAll(l2); 
       } 
       return l1; 
      })); 
} 

Meine Tests zeigen, dass dieser Kollektor schneller ist immer als abzubilden Sammeln (bis auf durchschnittliche Anzahl der doppelten Namen 2x je), die beide in sequentiellen und parallelen Modus .

Ein weiterer Ansatz ist meine StreamEx Bibliothek zu verwenden, die einschließlich collapse eine Reihe von „partial reduction“ Methoden bestimmt:

public static List<Foo> withStreamEx(Stream<Foo> stream) { 
    return StreamEx.of(stream) 
      .collapse((l, r) -> l.name.equals(r.name), (l, r) -> { 
       l.ids.addAll(r.ids); 
       return l; 
      }).toList(); 
} 

Dieses Verfahren nimmt zwei Argumente: ein BiPredicate die für zwei benachbarte Elemente angelegt wird, und sollte das Rück true, wenn Elemente zusammengeführt werden sollen und BinaryOperator, die das Zusammenführen durchführt. Diese Lösung ist im sequentiellen Modus ein wenig langsamer als der benutzerdefinierte Kollektor (parallel sind die Ergebnisse sehr ähnlich), aber es ist immer noch deutlich schneller als toMap Lösung und es ist einfacher und etwas flexibler als collapse ist eine Zwischenoperation, so dass Sie sammeln können auf eine andere Art.

Wieder funktionieren beide Lösungen nur dann, wenn bekannt ist, dass gleichnamige Objekte nebeneinander liegen. Es ist eine schlechte Idee, den Eingabestrom nach foo name zu sortieren, und dann diese Lösungen zu verwenden, da die Sortierung die Leistung drastisch reduziert, wodurch sie langsamer als toMap wird.

Answer 4

Wie bereits von anderen erwähnt, ist ein Zwischenprodukt Map unvermeidlich, da so die zu verschmelzenden Objekte gefunden werden können. Außerdem sollten Sie die Quelldaten während der Reduktion nicht ändern.

Trotzdem kann man beide Ziele zu erreichen, ohne dass mehrere Erstellen Foo Instanzen:

List<Foo> foos = Stream.of("foo", "bar", "baz") 
       .flatMap(n->IntStream.range(0,10).mapToObj(i -> new Foo(n, i))) 

       .collect(collectingAndThen(groupingBy(f -> f.name), 
        m->m.entrySet().stream().map(e->new Foo(e.getKey(), 
         e.getValue().stream().flatMap(f->f.ids.stream()).collect(toList()))) 
        .collect(toList()))); 

Dies setzt voraus, dass Sie einen Konstruktor

public Foo(String n, List<Integer> l) { 
     name = n; 
     ids=l; 
    } 

zu Ihrem Foo Klasse hinzufügen, wie es sollte, wenn Foo wirklich ist soll in der Lage sein, eine Liste von IDs zu halten. Als Nebenbemerkung erscheint mir ein Typ, der sowohl als einzelnes Element als auch als Container für zusammengeführte Ergebnisse dient, unnatürlich. Dies ist der Grund, warum Code so kompliziert ist.

Wenn die Quellelemente ein einzelnes id hatte, so etwas wie groupingBy(f -> f.name, mapping(f -> id, toList()) verwenden, gefolgt von Kartieren der Einträge von (String, List<Integer>) zu den fusionierten Elemente ausreichend.

Da dies nicht der Fall ist und Java 8 fehlt die flatMapping Kollektor, wird der Flatmapping-Schritt auf den zweiten Schritt verschoben, wodurch es viel komplizierter aussehen.

In beiden Fällen ist der zweite Schritt jedoch nicht veraltet, da die Ergebniselemente tatsächlich erstellt werden und die Konvertierung in den gewünschten Listentyp kostenlos erfolgt.