Montag, 4. Januar 2021

Vergiß den Letzten nicht!

Eine Gruppenschleifenfunktion in JavaScript


Eine bekannte Konstruktion


Bei der Abarbeitung von Listen in einer Schleife will man häufig die Elemente der Liste zu Gruppen zusammenfassen und dann für jede Gruppe eine Aktion ausführen. Es kann beispielsweise eine Liste von Positionen mehrerer Aufträge gegeben sein, und man will pro Auftrag eine Funktion aufrufen, um dessen Positionen zu verbuchen:

AuftragPos.Aktion
471110
471120
471130Auftrag 4711 verbuchen
471210
471220Auftrag 4712 verbuchen
471310
.........
489910
489920Auftrag 4899 verbuchen

Neben der vollständigen Liste allItems aller Auftragspositionen ist also noch ein "Gruppenwechselkriterium" gegeben, um zu erkennen, ob mit der aktuellen Position ein neuer Auftrag begonnen wurde. Ist dieses erfüllt, führt man die Aktion aus. Wenn nicht, sammelt man die Position weiter im "Gruppenarray".

Und hier muß man nun Vergiß den Letzten nicht! beachten: nachdem die Schleife beendet wurde, befinden sich die Positionen des letzten Auftrags im Gruppenarray, wurden aber noch nicht verbucht. Man muß daher den Verbucher nicht nur beim Gruppenwechsel aufrufen, sondern ausdrücklich noch ein letztes Mal nach Beendigung der Schleife.

Von der Idee her müßte der Code also etwa so aussehen:
let orderItems = [], previousItem;
for (let item of allItems) {
  if ( previousItem !== undefined && 
       item.orderNumber != previousItem.orderNumber ) {
    saveOrder(orderItems);
    orderItems = [];
  }
  orderItems.push(item);
  previousItem = item;
}
// Don't forget the last!
if (orderItems.length > 0) saveOrder(orderItems);

Dieser an die Schleife hinten angehängte Extra-Aufruf von saveOrder() ist häßlich, aber leider nötig. Es gibt keinen vernünftigen Weg, ihn zu vermeiden.[1] Der Grund ist, daß man bei der Prüfung auf Gruppenwechsel gewissermaßen zurückschaut: von der neuen Position wird auf die zurückliegenden Positionen geschaut, und durch den Vergleich mit der zuletzt durchlaufenen Position wird erkannt, daß wieder ein Auftrag verbucht werden muß. Die Positionen dieses Auftrags werden also zu einem Zeitpunkt verbucht, zu dem sie "gar nicht mehr aktuell" sind, weil man bereits bei der ersten Position des nachfolgenden Auftrags angekommen ist. Für die Positionen des letzten Auftrags gibt es aber keine nachfolgende Position mehr, von der aus man zurückschauen kann.

Idee: eine Gruppenschleifenfunktion


Man könnte sich aber ein Konstrukt "Gruppenschleife" ausdenken, in der diese Art der Gruppenbildung - inclusive des häßlichen letzten expliziten Aufrufs - hinter den Kulissen abgearbeitet wird. Tatsächlich gibt es in der Programmiersprache ABAP genau ein solches Konstrukt - die sehr mächtige Anweisung LOOP AT ... GROUP BY ... (die neben dieser Aufgabe noch eine Menge anderer Aufgaben rund um das Thema "Gruppierung von Einträgen interner Tabellen" löst). Dann müßte man genau noch einmal das häßliche Don't forget the last programmieren, aber eben hinter den Kulissen, in der Implementierung des Konstrukts "Gruppenschleife", das dann im Anwendungscode nur noch aufgerufen wird.

In JavaScript würde man nicht die originale Liste abarbeiten, sondern einen Gruppeniterator, der in jedem Iterationsschritt die Gruppe der zu dieser Auftragsnummer gesammelten Position liefert (Voraussetzung ist natürlich, daß die Liste nach der Auftragsnummer sortiert ist, also Positionen zum gleichen Auftrag in der Liste aufeinander folgen).

Mit einer (noch zu schreibenden) Funktion groupsByKey() könnte der obige Code dann wie folgt vereinfacht werden, wobei die Absicht des Programms klarer ausgedrückt wird und die technischen Details der Gruppenbildung in diese Funktion ausgelagert werden:
for (let orderItems of groupsByKey(allItems,it=>it.orderNumber)) {
  saveOrder(orderItems);
}

Wie sie zu schreiben wäre


Damit eine solche Funktion groupsByKey() ihre Arbeit tun kann, braucht sie zweierlei:
  • Eine Liste (ein iterierbares Objekt) baseIterable - im Beispiel die Grundliste allItems vieler Auftragspositionen
  • Eine Funktion getKey(), die einem Element der Liste seinen Gruppenschlüsselwert zuordnet. Durch Vergleich der Gruppenschlüsselwerte kann die Gruppenschleifen-Implementierung erkennen, daß ein Gruppenwechsel vorliegt.

Man könnte sich nun eine Implementierung vorstellen, die einen Array von Arrays (AoA) zurückliefert: der äußere Array zählt die einzelnen Gruppen auf, und jede einzelne Gruppe ist ihrerseits ein Array, bestehend aus den Elementen dieser Gruppe. Diese Lösung würde aber keinen effizienten Gebrauch vom Speicher machen, was für große Arrays ein Problem darstellen kann.

Eine bessere Lösung ist es, die Funktion groupsByKey() nur einen Iterator zurückgeben zu lassen und die einzelnen Gruppen nur pro Iterationsschritt zurückzugeben. Während also der Aufrufer über die Gruppen iteriert:
for (let orderItems of groupsByKey(allItems,it=>it.orderNumber)) { ... }
wird in der Implementierung von groupsByKey über die Elemente von allItems selbst iteriert.

Generatorfunktionen in JavaScript


Das für eine solche Implementierung perfekt passende Konstrukt sind in JavaScript die sogenannten Generatorfunktionen, die mit dem Schlüsselwort function* definiert werden. Bei einem Iterationsschritt werden sie ausgeführt, bis sie zur nächsten yield-Anweisung stoßen. Den dort angegebenen Ausdruck geben sie zurück. Beim nächsten Iterationsschritt werden sie genau nach dem letzten yield fortgesetzt, wobei der gesamte Ausführungskontext der Funktion erhalten bleibt. Wird die Funktion schließlich beendet, so wird auch die Iteration beendet.

Die Gruppenschleife kann daher als function* wie folgt definiert werden:
function* groupsByKey(baseIterable,getKey) {

  let currentGroup = [];
  for (let entry of baseIterable) {
    let key = getKey( entry );
    if (currentGroup.key !== key) {
        yield currentGroup;  // Gruppen-Array an Aufrufer zurückgeben
        currentGroup = [];   // Gruppen-Array für neuen Key initialisieren
        currentGroup.key = key;
      } 
    }
    currentGroup.push(entry);
  } 
  // "DON'T FORGET THE LAST" (falls baseIterable nicht leer war):
  if (currentGroup.length > 0) {
    yield currentGroup;
  }
  
}

Wie man sieht, gibt es immer noch den Teil DON'T FORGET THE LAST, bei Verwendung dieser Funktion aber eben nur noch einmal - und zwar hinter den Kulissen, nicht mehr im Anwendungscode selbst.

In dieser Implementierung sind die bei der Iteration gelieferten Gruppenobjekte einfach Arrays, die die einzelnen Elemente der Gruppe bis zum Gruppenwechsel enthalten, "verziert" mit einem zusätzlichen Attribut key, das den Schlüssel dieser Gruppe enthält.

Die Funktion groupsByKey() wäre ein Kandidat für eine Bibliothek übergreifender (applikationsunabhängiger) Funktionen, die dann für die verschiedensten konkreten Gruppenschleifen genutzt werden kann.

Noch ein Beispiel


Nehmen wir beispielsweise an, testArray sei ein sortierter Array natürlicher Zahlen. Dann können wir ihn mit dem folgenden Code in Tausendern gruppieren:
for (let g of groupsByKey(testArray,x=>Math.floor(x/1000))) {
  console.log(g.key,[...g])  
}
Die Konsole gibt dann beispielsweise aus:
  0 [ 364 ]
  2 [ 2628 ]
  3 [ 3208, 3550 ]
  4 [ 4110, 4602, 4851 ]
  5 [ 5480, 5532, 5533 ]
  7 [ 7032, 7385, 7485, 7632 ]
  9 [ 9271 ]

Beliebige groupChange()-Funktionen


Die Funktion groupsByKey() ist noch leicht verallgemeinerbar. Die Annahme war ja, daß die Einträge über eine Schlüsselfunktion getKey() zu gruppieren sind, wobei vorausgesetzt wird, daß Einträge gleichen Schlüssels in der Grundliste aufeinanderfolgen. Das ist aber schon eine Spezialisierung. Eigentlich benötigt man nur eine Funktion groupChange(currentEntry,lastEntry), die für aufeinanderfolgende Einträge des Arrays aufgerufen wird (wie im allerersten Beispiel dieses Blogposts) und true zurückliefert, falls ein Gruppenwechsel vorliegt. Wie ein Gruppenwechsel definiert wird, liegt dann voll in der Freiheit des Aufrufers.

Nun ist natürlich die Ermittlung des Gruppenwechsels über eine Schlüsselfunktion schon der häufigste Anwendungsfall. Daher sollte man aus der obigen Funktion groupsByKey() eine allgemeinere Iteratorfunktion groups() extrahieren, die mit einer beliebigen groupChange-Funktion arbeitet. So ergeben sich schließlich zwei Funktionen:
// Implementation of the function "groups()" 
// using a generator function
function* groups(baseIterable,groupChange) {

  let currentGroup = [], previousEntry;
  for (let entry of baseIterable) {
    if (previousEntry !== undefined) {
      if (groupChange(entry,previousEntry)) {
        yield currentGroup;
        currentGroup = [];
      } 
    }
    currentGroup.push(entry);
    previousEntry = entry;
  } 
  // "DON'T FORGET THE LAST" 
  // (if there were iterations at all)
  if (currentGroup.length > 0) {
    yield currentGroup;
  }

}

// The most typical use case: entries grouped by key
function* groupsByKey(baseIterable,getKey) {
  let key,lastKey; // Buffer current key and last key
  let groupChange = (a,b)=>{    
    lastKey = key ?? getKey(b);
    key = getKey(a);
    return key!=lastKey;
  };
  for (let g of groups(baseIterable,groupChange)){
    g.key = lastKey;
    yield g;
    lastKey = key;
  }
}
Die etwas umständliche Pufferung von key und lastKey in dieser Implementierung von groupsByKey() (die identisch wie die obige funktioniert, nur daß eben der eigentliche Gruppenschleifenmechanismus in eine allgemeinere Funktion groups() ausgelagert wurde) dient erstens dazu, daß die Funktion getKey() pro Eintrag wirklich nur einmal aufgerufen werden muß; zum anderen wird der lastKey verwendet, um das Attribut key des Gruppen-Arrays zu setzen (ebenfalls ohne getKey() noch einmal aufrufen zu müssen).

Online Testen


Hier kann man den Code in action betrachten - auf der JavaScript-Online-Plattform repl.it.






[1] Zumindest wenn man "Liste" im allgemeinen Sinn versteht - als ein Ding, über das man iterieren kann. Wenn man weitere strukturelle Annahmen macht, kann man auch herausfinden, ob man im letzten Schleifendurchgang ist (bei einem Array zum Beispiel weiß man, welches der höchste Index ist,  oder bei einer verketteten Liste liefert die Nachfolgerfunktion des letzten Elements den Wert null) und dies könnte man bereits innerhalb der Schleife zur Gruppenwechselbedingung hinzunehmen: "wenn Gruppenwechsel vorliegt oder wenn wir gerade das letzte Item verarbeitet haben."  Aber auch dann hat man das "Vergiß die letzte Gruppe nicht" - man hat es nur in die Gruppenwechselbedingung in der Schleife hineingezogen.

6 Kommentare :

Elvis Isik hat gesagt…

Sehr nützlich, Danke Rüdiger für den Beitrag

Rüdiger Plantiko hat gesagt…

Freut mich, Elvis, daß es Dir gefallen hat! Alles Gute im neuen Jahr!

Unknown hat gesagt…

Cooles Foto mit den jungen Weibchen. Wo hast Du das her?

Unknown hat gesagt…

War die Frage zu sehr off topic?

Rüdiger Plantiko hat gesagt…

Bißchen enttäuscht, daß das Deine einzige Frage zum Post war, aber OK. Ich sehe sie erst jetzt (schaue hier nicht täglich rein). Das Bild ist ein bekanntes Meme (vergleiche https://knowyourmeme.com/photos/1765157-girls-in-class-looking-back ). Es fängt hervorragend einen gewissen Blick ein: alle schauen auf Dich, mit einer Mischung aus fasziniertem Interesse und Befremden, wie auf einen exotischen Käfer. Ein Blick, den jeder Software-Entwickler kennen dürfte.

Unknown hat gesagt…

Besten Dank für die Aufklärung!