Eine Hashtabelle als Zähler
Kurz gesagt: Eine Map als Zähler (Map in JavaScript) 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:
const log = logOf(1000);const names = [];const counts = [];let comparisons = 0;for (const item of log) { let i = 0; while (i < names.length) { comparisons++; if (names[i] === item) break; i++; } if (i === names.length) { names.push(item); counts.push(1); } else { counts[i]++; }}console.log(`Bestellungen: ${log.length}`);console.log(`Produkte: ${names.length}`);console.log(`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:
function logOf(n) { const catalog = Math.floor(n / 4) + 1; return Array.from({ length: n }, (_, i) => `SKU-${(i * 7919) % catalog}`);}Die Idee
Die Map zählt
In der Lektion „Map und Set“ 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
const log = [ "Maus", "Headset", "Maus", "Monitor", "Tastatur", "Maus", "Headset", "Monitor", "Maus", "Headset",];const counts = new Map();for (const item of log) { counts.set(item, (counts.get(item) ?? 0) + 1);}const top = [...counts].sort((x, y) => y[1] - x[1]);for (const [item, n] of top.slice(0, 3)) { console.log(item, n);}Maus 4Headset 3Monitor 2const counts = new Map();for (const item of log) { counts.set(item, (counts.get(item) ?? 0) + 1);}const top = [...counts].sort((x, y) => y[1] - x[1]);for (const [item, n] of top.slice(0, 3)) { console.log(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.
counts.get(item) ?? 0 liefert 0 für ein Produkt, das noch nicht da ist. Die Klammern darum sind nötig: Ohne sie wird + 1 vor ?? berechnet. 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.set(item, (counts.get(item) 0) + 1);?? liefert 0, wenn get für ein Produkt, das noch nicht da ist, undefined zurückgibt.Sieh es dir an
Die Werkzeuge deiner Sprache
JavaScript hat keinen fertigen Zähler. Eine Map mit get, ?? 0 und set ist der übliche Weg. Ein einfaches Objekt funktioniert auch, hat aber geerbte Schlüssel ("constructor", "toString") und macht jeden Schlüssel zu Text. Eine Map durchläuft ihre Schlüssel in der Reihenfolge des Einfügens:
const log = [ "Maus", "Headset", "Maus", "Monitor", "Tastatur", "Maus", "Headset", "Monitor", "Maus", "Headset",];const counts = new Map();for (const item of log) counts.set(item, (counts.get(item) ?? 0) + 1);console.log(counts.get("Maus"), counts.get("Tablet") ?? 0);for (const [item, n] of counts) console.log(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:
const log = logOf(1000);const counts = new Map();let updates = 0;for (const item of log) { counts.set(item, (counts.get(item) ?? 0) + 1); updates++;}console.log(`Bestellungen: ${log.length}`);console.log(`Produkte: ${counts.size}`);console.log(`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 |
const counts = new Map();for (const item of log) { counts.set(item, (counts.get(item) ?? 0) + 1);}const top = [...counts].sort((x, y) => y[1] - x[1]);for (const [item, n] of top.slice(0, 3)) { console.log(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 JavaScript vergleicht eine Map Objekte nach Referenz, also ist der Schlüssel ein Text: `${city}|${item}`.
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.
function matches(kit, basket) { const need = new Map(); for (const item of kit) need.set(item, (need.get(item) ?? 0) + 1); for (const item of basket) need.set(item, (need.get(item) ?? 0) - 1); return [...need.values()].every((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
const kit = [ "Monitor", "Tastatur", "Maus", "Kabel", "Kabel",];const basket1 = [ "Kabel", "Maus", "Monitor", "Kabel", "Tastatur",];const basket2 = [ "Monitor", "Tastatur", "Maus", "Maus", "Kabel",];console.log(`Warenkorb 1: ${matches(kit, basket1) ? "vollständiges Set" : "passt nicht"}`);console.log(`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:
function firstSingle(customers) { const counts = new Map(); for (const c of customers) counts.set(c, (counts.get(c) ?? 0) + 1); for (const c of customers) { if (counts.get(c) === 1) return c; } return null;}const customers = [ "C-17", "C-4", "C-17", "C-9", "C-4", "C-21", "C-9", "C-30",];console.log(`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? Eine Map durchläuft in der Reihenfolge des Einfügens (von der Spezifikation zugesichert), also würde hier das Durchlaufen von counts dieselbe Antwort geben. Das Log ist trotzdem klarer: Die Reihenfolge kommt von ihm.
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:
function voucherPair(prices, voucher) { const seen = new Map(); for (let i = 0; i < prices.length; i++) { const j = seen.get(voucher - prices[i]); if (j !== undefined) return [j, i]; seen.set(prices[i], i); } return null;}const prices = [27, 14, 33, 25, 8, 36, 19];const [a, b] = voucherPair(prices, 50);console.log(`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:
const prices = [27, 14, 33, 25, 8, 36, 19];const [a, b] = voucherPair(prices, 50);console.log(`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