Eine Hashtabelle als Zähler
Kurz gesagt: Eine Map als Zähler (dict oder collections.Counter in Python) 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:
log = log_of(1000)names = []counts = []comparisons = 0for item in log: i = 0 while i < len(names): comparisons += 1 if names[i] == item: break i += 1 if i == len(names): names.append(item) counts.append(1) else: counts[i] += 1print(f"Bestellungen: {len(log)}")print(f"Produkte: {len(names)}")print(f"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:
def log_of(n): catalog = n // 4 + 1 return [f"SKU-{(i * 7919) % catalog}" for i in range(n)]Die Idee
Die Map zählt
In der Lektion „dict 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
from collections import defaultdict
log = [ "Maus", "Headset", "Maus", "Monitor", "Tastatur", "Maus", "Headset", "Monitor", "Maus", "Headset",]counts = defaultdict(int)for item in log: counts[item] += 1top = sorted(counts.items(), key=lambda e: e[1], reverse=True)for item, n in top[:3]: print(item, n)Maus 4Headset 3Monitor 2counts = defaultdict(int)for item in log: counts[item] += 1top = sorted(counts.items(), key=lambda e: e[1], reverse=True)for item, n in top[:3]: print(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.
defaultdict(int) erzeugt beim ersten Lesen eines neuen Schlüssels einen Zähler mit 0, also funktioniert counts[item] += 1 auch für ein neues Produkt. 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 = defaultdict()defaultdict(int) ruft für einen neuen Schlüssel int() auf, und int() ist 0.Sieh es dir an
Die Werkzeuge deiner Sprache
Python hat einen fertigen Zähler: collections.Counter. Er nimmt die Liste und zählt selbst, liefert 0 für einen fehlenden Schlüssel, und most_common(k) gibt die Top k nach Zähler zurück. Gleiche Zähler bleiben in der Reihenfolge des ersten Auftretens:
from collections import Counter
log = [ "Maus", "Headset", "Maus", "Monitor", "Tastatur", "Maus", "Headset", "Monitor", "Maus", "Headset",]counts = Counter(log)print(counts["Maus"], counts["Tablet"])print(counts.most_common(3))4 0[('Maus', 4), ('Headset', 3), ('Monitor', 2)]defaultdict(int) ist das allgemeinere Werkzeug: derselbe Zähler, aber der Wert kann auch eine Summe oder eine Liste sein.
Sieh es dir an
Miss es: eine Liste von Paaren gegen eine Map
Dieselben tausend Bestellungen mit der Map:
log = log_of(1000)counts = defaultdict(int)updates = 0for item in log: counts[item] += 1 updates += 1print(f"Bestellungen: {len(log)}")print(f"Produkte: {len(counts)}")print(f"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 |
counts = defaultdict(int)for item in log: counts[item] += 1top = sorted(counts.items(), key=lambda e: e[1], reverse=True)for item, n in top[:3]: print(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 Python ist es ein Tupel (city, item): Es ist unveränderlich und hat einen Hash.
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.
def matches(kit, basket): return Counter(kit) == Counter(basket)Counter wird mit == über seine Zähler verglichen, die ganze Prüfung ist also eine Zeile.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
from collections import Counter
kit = ["Monitor", "Tastatur", "Maus", "Kabel", "Kabel"]basket1 = ["Kabel", "Maus", "Monitor", "Kabel", "Tastatur"]basket2 = ["Monitor", "Tastatur", "Maus", "Maus", "Kabel"]print(f"Warenkorb 1: {'vollständiges Set' if matches(kit, basket1) else 'passt nicht'}")print(f"Warenkorb 2: {'vollständiges Set' if matches(kit, basket2) else '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:
def first_single(customers): counts = Counter(customers) for c in customers: if counts[c] == 1: return c return Nonefrom collections import Counter
customers = [ "C-17", "C-4", "C-17", "C-9", "C-4", "C-21", "C-9", "C-30",]print(f"erster Kunde mit einer Bestellung: {first_single(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 dict behält die Reihenfolge des Einfügens (seit Python 3.7 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:
def voucher_pair(prices, voucher): seen = {} for i, price in enumerate(prices): j = seen.get(voucher - price) if j is not None: return j, i seen[price] = i return Noneprices = [27, 14, 33, 25, 8, 36, 19]a, b = voucher_pair(prices, 50)print(f"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:
prices = [27, 14, 33, 25, 8, 36, 19]a, b = voucher_pair(prices, 50)print(f"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