© katerin1234 / 123RF.com

In Rust ersetzen Iteratoren ineinander verschachtelte Schleifen und sorgen für übersichtlicheren Programmcode. Es lohnt sich, sich mit dem mächtigen Werkzeug zu beschäftigen, da es sich einfach einsetzen lässt und Programme beschleunigt.

Seit vielen Jahren findet vom 1. bis 25. Dezember der Programmierwettbewerb Advent of Code [1] statt. Genau um Mitternacht EST (in Deutschland 6 Uhr morgens) bekommen die Teilnehmenden jeden Tag eine neue Programmieraufgabe. Wer sie am schnellsten löst, erhält 100 Punkte, der oder die nächste 99 Punkte und so weiter. Wer nach 25 Tagen die meisten Punkte gesammelt hat, gewinnt. Was Sie immer gewinnen, sind neue Erfahrungen, denn Preise gibt es keine – aus meiner Sicht überaus sympathisch.

Im vergangenen Jahr versuchte ich erneut, so viele Aufgaben wie möglich mit Rust zu lösen. Ich zähle nicht zu den Frühaufstehern, deswegen lagen meine Rangplatzierungen zwischen 8000 und 20 000, was ich persönlich als ganz ordentlich empfinde. Danach habe ich mir die Veröffentlichungen anderer Rust-Teilnehmer angesehen. Dabei fiel mir auf, dass sie häufig mit Iteratoren arbeiteten, während ich Schleife in Schleife schachtelte. Iteratoren bringen zahlreiche Funktionen mit, die ich immer erst selbst programmierte.

Erste Quiz-Frage: Was steckt explizit hinter einem Iterator? Suchen Sie den Begriff im Internet, erhalten Sie häufig die Antwort “Entwurfsmuster” oder “Komponente”, was wenig weiterhilft. In Rust ist ein Iterator eine Schnittstelle (Trait) mit dem passenden Namen Iterator (Listing 1). Sie besteht im Wesentlichen aus der Funktion »next« (dritte Zeile). Jedesmal, wenn Sie die Funktion aufrufen, bekommen Sie etwas zurück.

trait Iterator {
  type Item;
  fn next(&mut self) -> Option<Self::Item>;
}

Das klingt ziemlich abstrakt, daher zeigt Listing 2 dazu ein konkretes Beispiel. Aus dem Vektor »values« mit den Werten »1,2,3,4« bauen Sie mit der Methode »iter()« einen eigenen Iterator (erste und zweite Zeile), den Sie in der Variablen »iter« ablegen. Beim Aufruf der Methode »next()« (dritte und vierte Zeile) gibt der Iterator immer den nächsten Wert zurück: beim ersten Mal das erste Element des Vektors (»1«), beim nächsten Mal das nächste Element des Vektors (»2«) und so weiter.

let values = vec![1,2,3,4];
let mut iter = values.iter();
println!("{}", iter.next().unwrap()); //=> 1
println!("{}", iter.next().unwrap()); //=> 2

An der Methode »unwrap()« erkennen Sie, dass der Iterator nicht die Zahl direkt zurückgibt, sondern den Rust-Datentyp »Option<Item>«. Ist ein Wert im Vektor vorhanden, bekommen Sie beispielsweise »Some(1)« zurück. Gibt es keinen Wert mehr, liefert der Iterator »None« zurück, und das Programm kann darauf reagieren. Der Iterator »iter« ist veränderbar (»mut«, zweite Zeile), da er sich bei jedem Aufruf von »next()« merken muss, welches Element als Nächstes kommt.

Ein weiteres Beispiel zu Iteratoren besteht im unkomplizierten, zeilenweisen Lesen eines langen Texts (Listing 3). Dabei liefert die Methode »lines()« (zweite Zeile) den Iterator zurück. Über die Methode »next()« (dritte und vierte Zeile) greifen Sie daraufhin auf die einzelnen Zeilen zu und verarbeiten sie.

let input = "?"; // Langer Text (String) aus vielen Zeilen
let mut lines = input.lines();
println!("{}", lines.next().unwrap()); // => "zeile 1"
println!("{}", lines.next().unwrap()); // => "zeile 2"

Schleifen und Iteratoren

Nun stellt sich die Frage, wo sich bei der For-Schleife der Iterator versteckt. Listing 4 sorgt für Klarheit. Bei jedem Schleifendurchlauf erhält die Variable »i« von Rust den nächsten Wert aus dem Vektor »values« (zweite Zeile). Intern holt sich dazu Rust von »values« einen Iterator und führt ihn aus. Findet sich ein Wert, wird die Schleife durchlaufen, im gegenteiligen Fall endet sie.

let values = vec![1,2,3,4];
for i in values {
  println!("{i}");
}

Eine For-Schleife in Rust können Sie mit jeder Datenstruktur verwenden, die einen Iterator zurückliefert. Diese Datenstrukturen implementieren in Rust die Schnittstelle (Traits) »IntoIterator« (Listing 5, erste Zeile). Die Methode »into_iter()« (dritte Zeile) gibt einen Iterator auf die Datenstruktur zurück.

pub trait IntoIterator {
  type Item;
  type IntoIter: Iterator<Item = Self::Item>;
  fn into_iter(self) -> Self::IntoIter;
}

Prinzipiell könnten Sie auf die For-Schleife verzichten. Dasselbe ließe sich mit einer Loop-Schleife programmieren, was allerdings etwas umständlich ausfiele. In Listing 6 erzeugt die Methode »into_iter()« (zweite Zeile) einen Iterator auf die Elemente des Vektors. Liefert »iter.next()« (Zeile 4) etwas zurück, geht es weiter mit dem nächsten Schleifendurchlauf. Bei »None« (Zeile 6) endet die Schleife.

let values = vec![1,2,3,4];
let mut iter = values.into_iter();
loop {
  match iter.next() {
    Some(i) => println!("{i}"),
    None => break
  }
}

Beim Erzeugen von Iteratoren gibt es hauptsächlich drei Methoden: »iter()« iteriert über »&T«, »Iter_mut()« über »&mut T« und »Into_iter()« über »T«. Die Namen der Methoden entsprechen in Rust etablierten Konventionen. Alternativ definieren Sie selbst eine Methode, die beispielsweise »liefer_mir_mal_was« heißt und einen Iterator erstellt. Falls andere Ihre Methode nutzen sollten, dürfte es ihnen jedoch etwas schwerfallen, den Zweck am Namen zu erkennen.

Iterator selbstgemacht

Das Programmieren eines eigenen Iterators gestaltet sich relativ einfach. Zum einen benötigen Sie eine Datenstruktur, häufig vom Typ »struct«, in der Sie den aktuellen Zustand speichern. Zum anderen implementiert diese Struktur die Schnittstelle »Iterator«. In Listing 7 sehen Sie dafür ein Beispiel.

struct Counter {
  count: usize,
  count_max: usize
}
impl Counter {
  fn new(count_max:usize) -> Counter {
    Counter {
      count: 0,
      count_max: count_max
    }
  }
}
impl Iterator for Counter {
  type Item = usize;
  fn next(&mut self) -> Option<Self::Item> {
    self.count += 1;
    if self.count <= self.count_max {
      Some(self.count)
      } else {
        None
    }
  }
}

Der Counter (Iterator) zählt bis zu einem maximalen Wert hoch. Mit der Methode »new()« (Zeile 6) erzeugen Sie einen neuen Counter und legen über den Parameter »count_max« den höchsten Wert fest. Das zweite Feld »count« (Zeile 8) in Counter dient dazu, bei jedem Aufruf von Rust um eins erhöht zu werden. Es bildet den aktuellen Zustand des Counters ab. Die für einen Iterator erforderliche Methode »next()« (Zeile 16) zählt eins hoch und liefert die Werte zurück.

Der Datentyp »Counter« lässt sich einfach in einer For-Schleife nutzen (Listing 8). Doch wer braucht einen solchen Datentyp, wenn man Ausdrücke wie »0..6« in Schleifen einsetzen kann? Dahinter steckt der Datentyp »Range«, der ebenso einen Iterator liefert.

for i in Counter::new(5) {
  println!("{i}");
}

Range in Rust

Der Ausdruck »0..5« in Rust entspricht intern dem folgenden Kommando:

std::ops::Range{start:0,end:5})

Rust erzeugt für den Ausdruck eine Datenstruktur vom Standardtyp »Range« mit den Feldern »start« und »end«. Der Bereich »start..end« enthält alle Werte des Bereichs »start <=x < end«. Der Wert für »end« bleibt dabei außen vor.

Bei der For-Schleife »for i in 0..5 { ? }« erzeugt Rust den Datentyp »Range« und holt sich von ihm einen Iterator für die Schleife, der die passenden Schnittstellen umfasst. Falls Sie den Wert für »end« einschließen möchten, definieren Sie »Range« über den Ausdruck »0..=5«.

Advent of Code

Die Programmieraufgaben beim Advent of Code bestehen stets aus einer schönen, die Aufgabenstellung beschreibenden Geschichte. Häufig geht es dabei um Wichtel, Schnee oder andere weihnachtliche Themen. Aus der Beschreibung müssen Sie die Eingabedaten und die Verarbeitung herausfiltern. Haben Sie Ihr Programm fertig geschrieben, kommt als Ergebnis immer eine Zahl heraus, die Sie auf der Webseite des Projekts eingeben. Stimmt die Zahl, stoppt die Zeit.

Die ausführliche Erklärung zur Aufgabe 1 aus dem Jahr 2023 finden Sie auf der Webseite [2]. Die Beispieldaten sehen so aus wie in Listing 9. In jeder Zeile finden sich eine erste und eine letzte Ziffer. Daraus ergibt sich jeweils eine zweistellige Zahl. Beispielsweise beginnt die erste Zeile mit der Ziffer 1, als letzte Ziffer kommt eine 2. Das Ergebnis für diese Zeile lautet dementsprechend 12. Die Ergebnisse sämtlicher Zeilen summieren Sie auf und erhalten damit das Gesamtergebnis.

1abc2
pqr3stu8vwx
a1b2c3d4e5f
treb7uchet

Wie Listing 10 demonstriert, ist der Algorithmus für diese Aufgabe nicht sonderlich kompliziert. Das mit Schleifen zu programmieren, sollte keine allzu große Herausforderung darstellen. Die Angelegenheit lässt sich allerdings ebenso mithilfe von Iteratoren und damit ganz ohne Schleifen lösen.

ergebnis = 0
für jede Zeile:
  erste_ziffer = suche erste Ziffer der Zeile
  letzte_ziffer
 = suche letzte Ziffer der Zeile
  zahl = 10 * erste_ziffer + letzte_ziffer
  ergebnis = ergebnis + zahl

Iteratoren kombinieren

Im ersten Schritt habe ich die Beispieldaten in die Text-Datei »input.txt« kopiert, die ich mit einem Befehl in eine Variable »input« vom Typ »String« lese (Listing 11, erste Zeile). Mehr zu Dateioperationen in Rust lesen Sie in einer späteren Ausgabe dieser Serie. Iteratoren lassen sich einfach miteinander kombinieren – konkret dient dabei das Ergebnis des einen Iterators dem nächsten Iterator als Eingabe. Vereinfacht sieht der Algorithmus für die beschriebene Programmieraufgabe so aus wie in der zweiten Zeile des Listings.

let input = fs::read_to_string("./input.txt").unwrap();
let result:usize = input.lines().map(|x| {x.len()}).sum();

Die Methode »lines()« liefert, wie bereits beobachtet, einen Iterator, der jede einzelne Zeile des Texts zurückgibt. Die Methode »map()« wiederum verarbeitet jedes Element, das sie von »lines()« erhält. Sie setzt sich aus einem Parameter zwischen zwei Strichen und einer Definitionzusammen, was sie damit machen soll. Als Definition geben Sie den auszuführenden Befehl direkt in geschweiften Klammern an (Closure), oder Sie schreiben dort eine beliebige Funktion hin. Im vereinfachten Beispiel steht dort lediglich ein einziger Befehl, der die Länge des Input-Strings zurückgibt. Für die Programmieraufgaben finden sich dort die Befehle, die in jeder Zeile die Ziffern heraussuchen und daraus als Ergebnis die zweistellige Zahl ausgeben.

Auf den Punkt gebracht steckt hinter der Methode »map()« ein Iterator Adapter. Das bedeutet, dass das Ergebnis von »map()« erneut ein Iterator ist. Fragt eine Funktion mit »next()« bei »map()« an, holt sich die Methode wiederum mit »next()« bei dem vorhergehenden Iterator den Input und verarbeitet ihn zum Ergebnis. Rust bezeichnet die Vorgehensweise als “lazy” und stößt die Verarbeitung erst an, wenn ein Abnehmer die Methode »next()« aufruft.

Nach den Methoden »lines()« und »map()« schließt sich die Methode »sum()« an. Sie fragt sämtliche Zahlen ab, die sie vom vorhergehenden Iterator bekommen kann, und liefert eine Gesamtsumme zurück. Damit ist »sum()« ein Konsument, der intern die Methode »next()« beim Iterator so oft wie möglich ausführt.

Mit der Verkettung der drei Methoden wäre die Programmieraufgabe gelöst. Was noch fehlt, ist die Verarbeitung je Zeile.

Nützliche Iteratoren

Listing 12 zeigt den Gesamtablauf für die beschriebene Programmieraufgabe. Die Lösung orientiert sich stark an der aus meiner Sicht eleganten Vorgehensweise von Chris Biscardi. Er hat nahezu alle 25 Programmieraufgaben von 2023 gelöst und sein Vorgehen auf Youtube veröffentlicht [3].

let input = fs::read_to_string("./input.txt").unwrap();
  let result = input
    .lines()
    .map(|x| {
      let mut itr =
        x.chars().filter_map(|character| {
            character.to_digit(10)
        });
      let first =
        itr.next().unwrap();
      match itr.last() {
        Some(last) => format!("{first}{last}"),
        None => format!("{first}{first}"),
      }.parse::<u32>().unwrap()
    })
    .sum::<u32>();
  println!("result {result}")
}

Das Listing enthält einige interessante und nützliche Methoden. Die Methode »chars()« (Zeile 6) zerlegt einen String in die einzelnen Zeichen. Sie lässt sich ebenso in einer For-Schleife verwenden, um je Zeichen etwas zu verarbeiten. Bei der Methode »filter_map()« (Zeile 6 bis 8) handelt es sich um die Kombination aus den beiden gängigen Methoden »filter()« und »map()«.

Dabei extrahiert »filter()« bestimmte Elemente aus den Input-Elementen. Der erste Parameter ist das gelieferte Element, der zweite die Bedingung, nach der es zu filtern gilt. Die Methode »is_digit()« gibt für Ziffern »true« und für andere Zeichen »false« aus. Der Parameter »10« legt fest, dass Sie mit Dezimalziffern arbeiten möchten. Oft arbeitet man in der Informatik mit Binär- (Ziffern 0 und 1) oder mit Hexadezimalsystemen. Dann wäre etwa das Zeichen »b« eine dem Wert 11 entsprechende Ziffer.

Die Methode »filter_map()« verbindet das Filtern mit einem gleichzeitigen Verarbeitungsschritt. Die eingesetzte Methode »character.to_digit(10)« (Zeile 7) wandelt das Zeichen in die entsprechende Zahl um, sofern es sich um eine Ziffer handelt. Ansonsten gibt das Programm »None« zurück. In diesem Fall filtert die Methode »filter_map()« das Element heraus.

Bei der Umwandlung von Strings in Zahlenketten kommt die Methode »parse« (Zeile 14) ins Spiel, bei der Sie in spitzen Klammern angeben, welchen Zahlentyp Sie zurückerhalten möchten:

"21".parse::<u32>().unwrap()

Sehen Sie sich die Lösung der Programmieraufgabe im Iterator-Style in Ruhe an. Anfangs sah all das für mich kompliziert aus. Allerdings habe ich immer wieder einige der Methoden eingebaut, was ein Programm durchaus kürzer und übersichtlicher macht.

Itertools

Zusätzlich zu den Standardmethoden für Iteratoren existiert die Bibliothek (Crate) Itertools, deren Komponenten von der funktionalen Programmiersprache Haskell und dem Python-Modul Itertools inspiriert sind. Dort finden Sie Funktionen zum Verschneiden oder Zusammenfügen von Iteratoren und vieles mehr.

Am elften Tag des Advent of Code 2023 ging es um das Aufsummieren aller Abstände zwischen Galaxien [4]. In den Itertools gibt es dazu die Methode »combinations()«. Mit ihrer Hilfe lassen Sie sich alle möglichen Kombinationen von Elementen für eine Grundmenge ausgeben. In Listing 13 sehen Sie eine vereinfachte Variante der Programmieraufgabe.

use itertools::Itertools;
let galaxies = vec![1,2,3,4];
let result:Vec<_> = galaxies
  .iter()
  .combinations(2)
  .collect();

Im Vektor »galaxies« (zweite Zeile) befindet sich für jede Galaxie eine Zahl. Auf Abstandsberechnungen habe ich in diesem Beispiel verzichtet. Durch die Methode »iter()« (Zeile 4) kommen die Elemente bei »combinations()« (Zeile 5) an. Der Parameter »2« gibt an, dass es immer zwei Elemente zu kombinieren gilt. Die Methode »collect()« am Schluss macht aus dem Iterator wieder einen Vektor zum Ausdrucken. Das Ergebnis sieht folgendermaßen aus:

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

Bei Zweierkombinationen wie im Beispiel könnten Sie das mit zwei geschachtelten Schleifen erledigen. Benötigen Sie irgendwann jedoch Fünfer- oder noch größere Kombinationen, gestaltet sich die Sache unübersichtlich und damit fehleranfällig.

Ausblick

In den Geschichten zum Advent of Code im vergangenen Jahr ging es um die Reparatur der Schneemaschinen am Nordpol. Wie das Wetter Anfang 2024 gezeigt hat, waren die Entwicklerinnen und Entwickler erfolgreich. Die Aufgaben stehen online noch immer zur Verfügung, und ich kann sie Ihnen zum Sammeln von Programmiererfahrung nur ans Herz legen. (csi)