Berechnung eines Rankings mit Java 8 Stream API

Die beiden Fragen werden nacheinander angesprochen

• Rangdarstellung
• Ranking-Verfahren

Rangdarstellung

Das typische Ranking, wie oben gezeigt, ist eine Liste von Elementen, denen ihr relativer Ranking-Wert vorangestellt ist.

Es gibt mindestens zwei mögliche Implementierungen für den Rückgabewert einer Rangliste.

Option 1: List<Rank>

Eine mögliche interne Repräsentation des Rankings könnte eine Liste sein Elemente, die sowohl den Ranking-Wert als auch den Artikel enthalten. Zum Beispiel Wir könnten eine Klasse definieren:

Oder mit einem etwas esotherischeren Code:

Die resultierende Rangliste wird als List<Rank> zurückgegeben. Die Liste muss nach absteigendem Ranking sortiert zurückgegeben und in dieser Reihenfolge verarbeitet werden.

Ein möglicher Nachteil einer solchen Lösung ist die Notwendigkeit einer neuen Ad-hoc-Klasse oder Schnittstelle (d. h. Rank ).

Option 2: SortedMap<Integer,List<T>>

Eine alternative Lösung, die nur vordefinierte Standardklassen und Schnittstellen verwendet, basiert auf einer Karte.

Die Schlüssel der Karte entsprechen den Ranglistenwerten, während die Werte der Karte aus Listen bestehen, die die Elemente enthalten, die diese Rangliste teilen.

Der Rückgabetyp des Rankings wäre SortedMap<T,List<T>> . Die sortierte Karte wird implizit sortiert und kann entsprechend der natürlichen Reihenfolge des Schlüssels durchlaufen werden.

Diese letztere Lösung scheint vorzuziehen, weil sie keine neue Klasse erfordert und besser verstanden werden kann.

Rangierungsverfahren

Das Ranking-Berechnungsverfahren kann auf verschiedene Arten implementiert werden. Hier werden zwei Ansätze untersucht.

In allen Fällen müssen wir eine Funktion haben, die dem Zweck dient Extrahieren der Ranking-Eigenschaft:

In der Regel sollte der Eigenschaftstyp vergleichbar sein. Um jedoch allgemeiner zu sein (z. B. um Zeichenfolgen in absteigender Reihenfolge zu sortieren), kann der Eigenschaftenkomparator definiert werden:

Die beiden Ansätze werden anhand der oben beschriebenen Fallstudie veranschaulicht, wobei als Ausgangspunkt ein words stream verwendet wird:

Sortierung nach Ranking-Eigenschaft

Grundlegende Vorgehensweise

Eine anfängliche naive Version der Prozedur kann unter Verwendung einer unterstützenden Kartendatenstruktur definiert werden, auf der die Stream-Operationen mit Hilfe von Nebenwirkungen arbeiten:

Die Vorgehensweise ist wie folgt:

1. Sortiere die Elemente des Streams

   %Vor%

2. Ordnen Sie das Ranking zu, beginnend mit 1 und inkrementieren Sie es Jedes Mal, wenn sich die Eigenschaft ändert. Das Ranking muss erhöht werden nach der Anzahl der Elemente, die das aktuelle Ranking geteilt haben.

   %Vor%

Der obige Code funktioniert wie folgt:

• Die ursprüngliche Reihenfolge der Elemente ist unsortiert:

  {"DD","BBB","F","CCC","AAAA","EE"}

• Schritt 1 sortiert das Element mit dem propertyExtractor und dem relativen propertyComparator , d. h. nach Stringlänge:

  {"AAAA","BBB","CCC","DD","EE","F"}

• Dann wird für jedes Element (in der Reihenfolge) ein neuer Eintrag in der Karte hinzugefügt zu jedem Zeitpunkt unterscheidet sich die Länge des neuen Elements von der vorherigen Elementlänge

  • Wenn "AAAA" verarbeitet wird (erstes Element), wird ein neuer Eintrag hinzugefügt die Karte mit Schlüssel (d. h. Rangfolge) = 1:

    ranking : {1=["AAAA"]}

  • Da der zweite Eintrag "BBB" verarbeitet wird, seit seiner Länge (3) unterscheidet sich von der letzten Elementlänge (4, die Länge von "AAAA" ) Ein neuer Eintrag wird mit einem nicht aktualisierten Rangwert hinzugefügt:

    ranking : {1=["AAAA"],2=["BBB"]}

  • Da der dritte Artikel "CCC" verarbeitet wird, seit seiner Länge (3) ist gleich der letzten Elementlänge, der Artikel wird hinzugefügt zur Eintragsliste

    ranking : {1=["AAAA"],2=["BBB","CCC"]}

  • usw.

Verwendung von Kollektor

Eine mehr funktional-style -Version kann definiert werden, indem ein Kollektor verwendet wird, der die Datenstruktur einkapselt, in der die Ergebnisse akkumuliert werden. In der Praxis können wir einen einzelnen Stream-Ausdruck schreiben, der die Rangliste zurückgibt:

Ergebnisse kombinieren

Die Combiner -Methode, die im obigen Code undefiniert ist, verdient einige zusätzliche Überlegungen.

Die funktionale Schnittstelle ist beteiligt, wenn die Sammlung parallel durchgeführt wird; es wird verwendet, um zwei Teilergebnisse der Akkumulation zu einer einzigen zu kombinieren. In diesem Fall muss es die Schnittstelle BiConsumer<R,R> implementieren und es soll die beiden kumulierten Rangfolgen - rank1 und rank2 - in die erste kombinieren.

Eine mögliche Implementierung des Lieferanten ist:

Der Kollektor hat keine deklarierten Eigenschaften, daher werden die Elemente in der Reihenfolge verarbeitet und dann in der Reihenfolge zusammengesetzt. Z.B. die sortierte Liste der Artikel wird in zwei Teile geteilt, dann wird der erste Teil mit einer Kopie des Kollektors verarbeitet, wobei als Ergebnis die Karte rank1 ; parallel wird der zweite Teil verarbeitet, der als Ergebnis rank2 ergibt.

Nehmen wir an, die Ströme werden parallel in zwei Konkurenten verarbeitet Ausführung der Sammelvorgänge:

• der anfängliche sortierte Stream (Ergebnis der Operation sorted() ist in zwei streams aufgeteilt, die orded beibehalten

  • Teilstrom 1: {"AAAA","BBB","CCC"}
  • Teilstrom 2: {"DD","EE","F"}

• zwei verschiedene Kollektoren arbeiten parallel in jedem Teilstrom Das Ergebnis sind zwei Karten, die die Teilrangfolge jedes Teilstroms enthalten:

  • rank1 = {1=["AAAA"],2=["BBB","CCC"]}
  • rank2 = {1=["DD","EE"],3=["F"]}

• Die Operation combiner sollte in der Praxis rank2 in rank1 zusammenführen Jeder Eintrag der Operation rank2 sollte zu rank1 hinzugefügt werden Schlüssel aktualisiert. Die Schlüssel werden aktualisiert, indem ein Offset hinzugefügt wird, der gleich ist die Taste des letzten Eintrags plus die Länge der letzten Eintragsliste minus eins:

  %Vor%

  In der Praxis sollte der Eintrag 1=["DD","EE"] von rank2 verwendet werden 4=["DD","EE"] und hinzugefügt zu rank1 .

• Zusätzlich sollte ein besonderer Fall in Betracht gezogen werden, d. h. wenn die Gegenstände im letzten Eintrag von rank1 und die im ersten Eintrag von rank2 teilen Sie den gleichen Ranking-Eigenschaftswert. Z.B. für die Länge der Zeichenfolge:

  • rank1 = {1=["AAAA"],2=["BBB","CCC"]}
  • rank2 = {1=["DDD"],2=["EE"],3=["F"]}

  Wenn dieser Fall auftritt, werden die Elemente in der rank2 ersten Eintragsliste angezeigt muss dazu in der letzten rank1 Eintragsliste hinzugefügt werden, und dann die erster Eintrag entfernt. Das heißt, die obigen Karten sollten umgewandelt werden in:

  • rank1 = {1=["AAAA"],2=["BBB","CCC" ,"DDD" ]}
  • rank2 = { ~~ 1=["DDD"], ~~ 2=["EE"],3=["F"]}

  Dann können die Einträge von rank2 aktualisiert und zu rank1 as hinzugefügt werden oben beschrieben.

Gruppierung nach Ranking-Eigenschaft

Grundlegende Vorgehensweise

Wie bei der sortierten Listenversion kann eine anfängliche, naive Version der Prozedur unter Verwendung einer unterstützenden Kartendatenstruktur definiert werden, auf der die Stream-Operationen mit Hilfe von Nebenwirkungen arbeiten:

Das naive Verfahren ist wie folgt:

1. gruppieren Sie die Objekte nach ihrer Eigenschaft in einer sortierten Karte

   %Vor%

2. berechnet für jeden Eintrag in der obigen Karte die Rangfolge

   %Vor%

Der obige Code funktioniert wie folgt:

• Die ursprüngliche Reihenfolge der Elemente ist unsortiert:

  {"DD","BBB","F","CCC","AAAA","EE"}

• Schritt 1 gruppiert das Objekt nach ihrem propertyExtractor und speichert sie in ein sortierter Satz, dessen Schlüssel durch propertyComparator , d.h. nach Zeichenkettenlänge:

  {4=["AAAA"],3=["BBB","CCC"],2=["DD","EE"],1=["F"]}

• Schritt 2, erstellt für jeden Eintrag in der Zwischenkarte einen neuen Eintrag in die Ergebniskarte hat den Ranking-Wert als Schlüssel und den gleichen Wert (d. h. die Liste der Elemente) als Zwischeneintrag.

  Das Ranking wird wie folgt berechnet:

  • 1 für den ersten Eintrag (d. h. wenn die Ergebniskarte noch leer ist) oder
  • vorheriges Ranking ( ranking.lastKey() ) plus Anzahl der Elemente Teilen des vorherigen Rankings ( ranking.get(ranking.lastKey()).size() ).

  Das Ergebnis ist die endgültige Rangliste:

  {1=["AAAA"],2=["BBB","CCC"],4=["DD","EE"],6=["F"]}

Verwendung eines Kollektors

Die obige Prozedur kann mit einem Kollektor neu geschrieben werden, um Nebenwirkungen der Operationen zu vermeiden.

Da der erste Schritt in einer Sammlung besteht, können wir die vordefinierte Kollektorfabrik methdo collectingAndThen verwenden, um den ersten Kollektor mit einer Funktion zu verketten, die auf das Kollektorergebnis angewendet wird; Eine solche Funktion führt den oben beschriebenen Schritt 2 aus.

Da die Struktur des Ergebnisses, d. h. das Akkumulatorobjekt, das ist Wie bei der sortierten Stromlösung kann hier derselbe Combiner verwendet werden.

Generische Lösungen

Die obige Diskussion und Lösung, die auf den speziellen Fall von ein Strom von Strings. Aber der Ansatz kann generalisiert werden mit Generika.

Sortierfunktion für Ranglisten

Die Lösung basierend auf dem sortierten Datenstrom kann in eine Funktion eingeschlossen werden:

Die obige Methode kann wie folgt angewendet werden:

Ranking Gruppierung Sammler

Der Ansatz basierend auf der Gruppierung nach Eigenschaftswert kann sein in einem Kollektor eingekapselt:

Diese Kollektor-Fabrik-Methode kann z.B. wie:

Drucken der Rangliste

Sobald das Ranking berechnet und in der Karte gespeichert wurde, kann es gedruckt werden, typischerweise für Debug-Zwecke.

Hier sind einige mögliche Optionen, um das Ranking auf der Konsole zu drucken.

Drucker Consumer

Verwenden Sie ein Consumer-Objekt, das die Rangfolge übernimmt, formatieren Sie die Einträge und drucke sie aus. Der folgende Code meldet eine Factory-Methode die Rückgaben so ein Verbraucher:

Collator Function

Verwenden einer Funktion, die die Rangliste in transformiert eine Zeichenfolge, die aus der Verkettung der Elemente besteht.

Die obige Methode kann wie folgt verwendet werden:

Ranking Map class

Alternativ ist es möglich, die Klasse TreeMap zu ersetzen mit einer neuen Klasse, die es erweitert und die toString() überschreibt Methode.

Dies geschieht durch Schreiben des folgenden Kollektorakkumulators Lieferant, anstelle von TreeMap::new :

Der vollständige Code für die Generika-Lösung ist in der Klasse verfügbar StreamRanking ist auf meinem Github-Repo verfügbar.

Im Gegensatz zu Ihnen selbst gelöst von Design First mache ich es über TDD .

Schritt 1 unter der Annahme, dass nur ein Wort existiert.

Nehmen wir an, dass das Ranking "foo" als ["1 - foo (3)"] dargestellt wird, löste ich es mit Stream.map (Funktion) und fake den Rang mit der Konstante 1 .

Schritt 2, vorausgesetzt es gibt 2 Wörter, deren Länge gleich ist.

Nehmen wir an, dass das Ranking "foo bar" als ["1 - bar (3)","1 - foo (3)"] dargestellt wird. Ich löste es durch Stream.sorted (Vergleicher) ;

Schritt 3, vorausgesetzt, es gibt 2 Wörter, deren Länge unterschiedlich ist.

Nehmen wir an, dass das Ranking "fuzz bar" als ["1 - fuzz (4)","2 - bar (3)"] dargestellt wird, löste ich es mit Comparator.comparing (Funktion) .

das Ergebnis ["1 - fuzz (4)", "1 ~~ 2 ~~ - bar (3)"] sind identisch mit Ausnahme der gefälschten Rangkonstante 1 .so mache ich ein kleines Refactoring vor dem Änderungscode :

Dann kann ich die erste Funktion Stream.map (Funktion) mit Stream.collect (...) .stream () und ersetzen Sie die gefälschte Rangkonstante 1 mit ranking.size() + 1 .

aber Schritt 2 wegen rank = ranking.size() + 1 ; Dann wurde mir klar, dass ich seine Länge mit dem letzten Rang vergleichen musste.

Tatsächlich finde ich, dass ich eine ArrayList durch einen Stack weiter ersetzen kann:

Beheben Sie einen Fehler, indem Sie einen anderen Test einführen

Nachdem ich den Code fertig gestellt hatte, fand ich einen Fehler im Code. Nehmen wir an, das Ranking "fuzz buzz foo" wird als ["1 - buzz (4)","1 - fuzz (4)","2 - foo (3)"] dargestellt, ich habe es gelöst, indem ich den Rang als last.rank + 1 und nicht als ranking.size() + 1 berechnet habe.

Endlich

Ich benenne die Variable accumulator mit einem sinnvollen Namen um, zB: rankingEvaluation , und ersetze null durch Null-Objekt und .etc.