Eine Hashtabelle als Zähler
Kurz gesagt: Eine Map als Zähler (Dictionary in C#) zählt in einem einzigen Durchgang, wie oft jedes Element vorkommt: O(n) statt O(n²) bei der Suche in einer Liste.
Problem
Die meistverkauften Produkte des Tages
Das Shop-Dashboard zeigt die drei meistverkauften Produkte des Tages. Das Log ist eine Liste von Bestellungen, eine pro Zeile. Der Code führt zwei Listen, die Namen und die Zähler, und sucht für jede Bestellung das Produkt vom Anfang der Namen an:
var log = LogOf(1000);var names = new List<string>();var counts = new List<int>();long comparisons = 0;foreach (var item in log){ int i = 0; while (i < names.Count) { comparisons++; if (names[i] == item) break; i++; } if (i == names.Count) { names.Add(item); counts.Add(1); } else { counts[i]++; }}Console.WriteLine($"Bestellungen: {log.Count}");Console.WriteLine($"Produkte: {names.Count}");Console.WriteLine($"Vergleiche: {comparisons}");Bestellungen: 1000Produkte: 251Vergleiche: 125255Tausend Bestellungen und 251 verschiedene Produkte: 125.255 Vergleiche. Der Katalog wächst mit dem Shop, und mit ihm die Liste, die jede Bestellung durchläuft. An einem großen Tag mit 100.000 Bestellungen lädt das Dashboard minutenlang.
Woher das Log kommt
Das Log folgt einer Formel, damit die Programme in allen vier Sprachen und der Vergleich unten im Browser genau dasselbe bauen. Der Katalog hat n / 4 + 1 Produkte:
static List<string> LogOf(int n){ int catalog = n / 4 + 1; var log = new List<string>(); for (int i = 0; i < n; i++) { log.Add($"SKU-{(i * 7919) % catalog}"); } return log;}Die Idee
Die Map zählt
In der Lektion „Dictionary und HashSet“ hast du Bestellungen mit einer Map gezählt. Hier wird daraus eine Technik: eine Hashtabelle als Zähler (eine Häufigkeitsmap). Der Schlüssel ist, was du zählst, der Wert, wie oft du es gesehen hast.
- Ein Durchgang über die Daten. Für jedes Element: seinen Zähler finden (oder 0) und 1 addieren.
- Das Nachschlagen geschieht in einer Hashtabelle: im Durchschnitt O(1), egal wie viele Produkte es gibt. Insgesamt O(n) statt O(n · m).
- Danach beantwortest du die Fragen aus den Zählern, nicht aus den Daten: welches am häufigsten ist, welches einmal vorkommt, ob zwei Dinge dieselben Zähler haben.
Der Speicher ist O(m): ein Paar für jedes verschiedene Produkt.
Sieh es dir an
Der Zähler füllt sich
List<string> log = [ "Maus", "Headset", "Maus", "Monitor", "Tastatur", "Maus", "Headset", "Monitor", "Maus", "Headset"];var counts = new Dictionary<string, int>();foreach (var item in log){ counts[item] = counts.GetValueOrDefault(item) + 1;}var top = counts.OrderByDescending(e => e.Value).Take(3);foreach (var (item, n) in top){ Console.WriteLine($"{item} {n}");}Maus 4Headset 3Monitor 2var counts = new Dictionary<string, int>();foreach (var item in log){ counts[item] = counts.GetValueOrDefault(item) + 1;}var top = counts.OrderByDescending(e => e.Value).Take(3);foreach (var (item, n) in top){ Console.WriteLine($"{item} {n}");}Schritt für Schritt, in Worten
- Eine leere Map: Produkt → wie oft es verkauft wurde. Das Log hat 10 Bestellungen.
- Bestellung 1: Maus. Es ist noch nicht in der Map, also bekommt es den Zähler 1.
- Bestellung 2: Headset. Es ist noch nicht in der Map, also bekommt es den Zähler 1.
- Bestellung 3: Maus, 1 → 2. Ein Nachschlagen in der Hashtabelle, ohne die anderen Produkte zu durchlaufen.
- Bestellung 4: Monitor. Es ist noch nicht in der Map, also bekommt es den Zähler 1.
- Bestellung 5: Tastatur. Es ist noch nicht in der Map, also bekommt es den Zähler 1.
- Bestellung 6: Maus, 2 → 3. Ein Nachschlagen in der Hashtabelle, ohne die anderen Produkte zu durchlaufen.
- Bestellung 7: Headset, 1 → 2. Ein Nachschlagen in der Hashtabelle, ohne die anderen Produkte zu durchlaufen.
- Bestellung 8: Monitor, 1 → 2. Ein Nachschlagen in der Hashtabelle, ohne die anderen Produkte zu durchlaufen.
- Bestellung 9: Maus, 3 → 4. Ein Nachschlagen in der Hashtabelle, ohne die anderen Produkte zu durchlaufen.
- Bestellung 10: Headset, 2 → 3. Ein Nachschlagen in der Hashtabelle, ohne die anderen Produkte zu durchlaufen.
- 10 Bestellungen, 10 Zähleraktualisierungen. Sortiert werden nur die 4 verschiedenen Produkte nach Zähler, nicht die Bestellungen.
- Die Top drei: Maus 4, Headset 3, Monitor 2.
GetValueOrDefault(item) liefert 0 für ein Produkt, das noch nicht da ist, also ergibt die erste Bestellung 1. Die Top drei entstehen durch Sortieren der Paare nach Zähler: Sortiert werden nur die verschiedenen Produkte, nicht die Bestellungen.
Probier es aus
Ergänze
Die Zeile, die zählt:
counts[item] = counts.(item) + 1;GetValueOrDefault liefert den Wert oder 0 für einen Schlüssel, der nicht da ist.Sieh es dir an
Die Werkzeuge deiner Sprache
In C# ist der Zähler ein Dictionary<string, int>. TryGetValue liest ohne Exception bei einem fehlenden Schlüssel. counts[item] = counts.GetValueOrDefault(item) + 1 schlägt den Schlüssel zweimal nach: einmal zum Lesen, einmal zum Schreiben. CollectionsMarshal.GetValueRefOrAddDefault liefert eine Referenz (ref) auf den Wert in der Tabelle, und du erhöhst ihn an Ort und Stelle mit einem Nachschlagen. Seit .NET 9 hat auch LINQ ein fertiges Zählen, CountBy, in der Reihenfolge des ersten Auftretens:
List<string> log = [ "Maus", "Headset", "Maus", "Monitor", "Tastatur", "Maus", "Headset", "Monitor", "Maus", "Headset"];var counts = new Dictionary<string, int>();foreach (var item in log){ ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, item, out _); slot++;}Console.WriteLine($"{counts["Maus"]} {(counts.TryGetValue("Tablet", out int t) ? t : 0)}");foreach (var (item, n) in log.CountBy(x => x)){ Console.WriteLine($"{item} {n}");}4 0Maus 4Headset 3Monitor 2Tastatur 1Sieh es dir an
Miss es: eine Liste von Paaren gegen eine Map
Dieselben tausend Bestellungen mit der Map:
var log = LogOf(1000);var counts = new Dictionary<string, int>();long updates = 0;foreach (var item in log){ counts[item] = counts.GetValueOrDefault(item) + 1; updates++;}Console.WriteLine($"Bestellungen: {log.Count}");Console.WriteLine($"Produkte: {counts.Count}");Console.WriteLine($"Zähleraktualisierungen: {updates}");Bestellungen: 1000Produkte: 251Zähleraktualisierungen: 10001.000 Aktualisierungen statt 125.255 Vergleiche. Lass beide im Browser laufen. n ist die Zahl der Bestellungen, und der Katalog wächst mit:
- Eine Liste von Paaren aus Produkt und Anzahl
O(n²) - Eine Map als Zähler
O(n)
| Algorithmus | n = 10 | n = 1.000 | n = 100.000 |
|---|---|---|---|
| Eine Liste von Paaren aus Produkt und Anzahl | 16 | 125.255 | ≈ 1.252.550.000 |
| Eine Map als Zähler | 10 | 1.000 | 100.000 |
var counts = new Dictionary<string, int>();foreach (var item in log){ counts[item] = counts.GetValueOrDefault(item) + 1;}var top = counts.OrderByDescending(e => e.Value).Take(3);foreach (var (item, n) in top){ Console.WriteLine($"{item} {n}");}Genauer, für Neugierige
Die Top k ohne alles zu sortieren. Das Sortieren von m verschiedenen Produkten ist O(m log m). Gibt es Millionen von Produkten und du brauchst die Top 10, behältst du einen Heap mit höchstens k Paaren: Jedes Paar kommt hinein, und bei k + 1 Paaren geht das kleinste hinaus. Das ist O(m log k).
Ein Schlüssel aus mehreren Teilen. Du zählst Verkäufe nach Stadt und Produkt: Der Schlüssel ist das Paar. In C# ist es ein Tupel (city, item) oder ein record: Beide haben Equals und GetHashCode über ihre Felder.
Die Idee
Der Warenkorb und das Set
Das Set „Homeoffice“ besteht aus einem Monitor, einer Tastatur, einer Maus und zwei Kabeln. Das Lager prüft, dass der Warenkorb, der verschickt werden soll, genau das Set ist: nichts zu viel, nichts zu wenig. Die Reihenfolge ist egal, die Zähler nicht.
Ein Zähler: +1 für jedes Produkt des Sets, −1 für jedes Produkt im Warenkorb. Der Warenkorb passt, wenn alle Zähler am Ende 0 sind.
static bool Matches(List<string> kit, List<string> basket){ var need = new Dictionary<string, int>(); foreach (var item in kit) need[item] = need.GetValueOrDefault(item) + 1; foreach (var item in basket) need[item] = need.GetValueOrDefault(item) - 1; return need.Values.All(n => n == 0);}Dieselbe Prüfung findet Anagramme: „listen“ und „silent“ haben dieselben Buchstaben mit denselben Zählern. Der Zähler läuft über Buchstaben statt über Produkte.
Probier es aus
Sag die Prüfung voraus
List<string> kit = [ "Monitor", "Tastatur", "Maus", "Kabel", "Kabel"];List<string> basket1 = [ "Kabel", "Maus", "Monitor", "Kabel", "Tastatur"];List<string> basket2 = [ "Monitor", "Tastatur", "Maus", "Maus", "Kabel"];Console.WriteLine($"Warenkorb 1: {(Matches(kit, basket1) ? "vollständiges Set" : "passt nicht")}");Console.WriteLine($"Warenkorb 2: {(Matches(kit, basket2) ? "vollständiges Set" : "passt nicht")}");Der erste Warenkorb hat dieselben fünf Produkte in anderer Reihenfolge: Jeder Zähler wird 0. Der zweite hat zwei Mäuse und ein Kabel: Die Maus bleibt bei −1, das Kabel bei +1, also passt er nicht, obwohl es fünf Produkte sind.
Die Idee
Der erste Kunde mit einer einzigen Bestellung
Das Marketing schickt einen „Komm zurück“-Gutschein an die Kunden, die nur einmal bestellt haben. Es will den zeitlich ersten. Der Zähler liefert die Zähler, aber nicht die Reihenfolge:
static string? FirstSingle(List<string> customers){ var counts = new Dictionary<string, int>(); foreach (var c in customers) counts[c] = counts.GetValueOrDefault(c) + 1; foreach (var c in customers) { if (counts[c] == 1) return c; } return null;}List<string> customers = [ "C-17", "C-4", "C-17", "C-9", "C-4", "C-21", "C-9", "C-30"];Console.WriteLine($"erster Kunde mit einer Bestellung: {FirstSingle(customers)}");erster Kunde mit einer Bestellung: C-21Zwei Durchgänge: Der erste zählt, der zweite läuft durch das Log, in der Reihenfolge der Bestellungen, und hält beim ersten mit Zähler 1 an. O(n), ohne verschachtelte Schleife.
Genauer, für Neugierige
Warum läuft der zweite Durchgang durch das Log und nicht durch die Map? Ein Dictionary durchläuft im heutigen .NET die Reihenfolge des Einfügens, solange nichts entfernt wurde, aber die Dokumentation verspricht es nicht. Verlass dich nicht darauf.
Die Idee
Zwei Produkte für genau 50 €
Der Kunde hat einen Gutschein über genau 50 € und will zwei Produkte, die ihn aufbrauchen. Die Preise im Katalog sind nicht sortiert.
Du gehst die Preise durch und fragst bei jedem: Habe ich den Preis, der diesen auf 50 auffüllt, schon gesehen? Die Map behält die bisher gesehenen Preise und ihre Positionen:
static (int, int)? VoucherPair(int[] prices, int voucher){ var seen = new Dictionary<int, int>(); for (int i = 0; i < prices.Length; i++) { if (seen.TryGetValue(voucher - prices[i], out int j)) return (j, i); seen[prices[i]] = i; } return null;}int[] prices = { 27, 14, 33, 25, 8, 36, 19 };var (a, b) = VoucherPair(prices, 50).Value;Console.WriteLine($"Produkte {a} und {b}: {prices[a]} € + {prices[b]} €");Produkte 1 und 5: 14 € + 36 €Ein Durchgang: O(n) Zeit und O(n) Speicher. Mit zwei Zeigern geht es ohne Map, mit O(1) Speicher, aber die Preise müssen sortiert sein. Sind sie es nicht, kostet das Sortieren O(n log n) und die Position jedes Produkts im Katalog geht verloren. Also: sortierte Daten, zwei Zeiger; unsortierte Daten, eine Map.
Probier es aus
Finde den Fehler
Jemand hat zwei Zeilen vertauscht. Jetzt bietet das Programm für einen Gutschein über 50 € ein Produkt zweimal an:
int[] prices = { 27, 14, 33, 25, 8, 36, 19 };var (a, b) = VoucherPair(prices, 50).Value;Console.WriteLine($"Produkte {a} und {b}: {prices[a]} € + {prices[b]} €");Produkte 3 und 3: 25 € + 25 €Wähle die Zeile mit dem Fehler.
Der Preis kommt in die Map, bevor sein Partner nachgeschlagen wird. Das Produkt für 25 € sucht 50 − 25 = 25 und findet sich selbst. Das Schreiben muss nach dem Nachschlagen kommen: Dann enthält die Map nur die Produkte vor dem aktuellen, und das Programm findet 14 € + 36 €.
Übung
Wer gibt am meisten aus
Löse die Aufgabe in deinem eigenen Editor.
Umsatz pro Kunde. Das Log hat Paare aus Kunde und Betrag: C-4 mit 30 €, C-17 mit 55 €, C-4 mit 20 €, C-9 mit 80 €, C-17 mit 10 € und C-4 mit 45 €. Addiere die Beträge pro Kunde mit einer Map (der Wert ist eine Summe, kein Zähler) und gib die zwei aus, die am meisten ausgegeben haben:
C-4: 95 €C-9: 80 €Weitere Aufgaben
- Anagramme. Schreibe eine Prüfung, ob zwei Wörter Anagramme sind („listen“ und „silent“), indem du die Buchstaben mit einer Map zählst. Wie viele Operationen braucht sie bei Wörtern der Länge n?
- Die erste Wiederholung. Finde die erste Bestellung, deren Kunde schon früher bestellt hat. Brauchst du einen Zähler, oder genügt ein Set?
- Zeiträume mit gleichen Zählern. Aus den Präfixsummen weißt du, wie man Zeiträume mit gegebener Summe zählt. Zähle die Zeiträume aufeinanderfolgender Tage, in denen die Zahl der zurückgeschickten Bestellungen der Zahl der gelieferten entspricht.
Test