Хеш таблица като брояч
Накратко: Речникът като брояч (dict или collections.Counter в Python) брои колко пъти се среща всеки елемент с едно минаване: O(n) вместо O(n²) с търсене в списък.
Проблем
Най-продаваните продукти за деня
Таблото на магазина показва трите най-продавани продукта за деня. Дневникът е списък от поръчки, по една на ред. Кодът пази два списъка, имената и бройките, и за всяка поръчка търси продукта от началото на имената:
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"поръчки: {len(log)}")print(f"продукти: {len(names)}")print(f"сравнения: {comparisons}")поръчки: 1000продукти: 251сравнения: 125255Хиляда поръчки и 251 различни продукта: 125 255 сравнения. Каталогът расте заедно с магазина, а с него и списъкът, който всяка поръчка обхожда. В голям ден с 100 000 поръчки таблото се зарежда минути.
Откъде е дневникът
Дневникът е по формула, за да го построят еднакво програмите на четирите езика и сравнението в браузъра по-долу. Каталогът е n / 4 + 1 продукта:
def log_of(n): catalog = n // 4 + 1 return [f"SKU-{(i * 7919) % catalog}" for i in range(n)]Идеята
Речникът брои
В урока „dict и set“ броеше поръчки с речник. Тук то става техника: hash таблица като брояч (frequency map). Ключът е това, което броиш, стойността е колко пъти си го видял.
- Едно минаване по данните. За всеки елемент: намери брояча му (или 0) и добави 1.
- Търсенето е в hash таблица: средно O(1), колкото и продукти да има. Общо O(n) вместо O(n · m).
- След това отговаряш на въпросите от бройките, а не от данните: кое е най-често, кое е веднъж, дали две неща имат еднакви бройки.
Паметта е O(m): по една двойка за всеки различен продукт.
Виж го
Броячът се пълни
from collections import defaultdict
log = [ "мишка", "слушалки", "мишка", "монитор", "клавиатура", "мишка", "слушалки", "монитор", "мишка", "слушалки",]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)мишка 4слушалки 3монитор 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)Стъпка по стъпка, с думи
- Празен речник: продукт → колко пъти е продаден. Дневникът има 10 поръчки.
- Поръчка 1: мишка. Още я няма в речника, затова получава брой 1.
- Поръчка 2: слушалки. Още я няма в речника, затова получава брой 1.
- Поръчка 3: мишка, 1 → 2. Едно търсене в hash таблицата, без да минаваш през другите продукти.
- Поръчка 4: монитор. Още я няма в речника, затова получава брой 1.
- Поръчка 5: клавиатура. Още я няма в речника, затова получава брой 1.
- Поръчка 6: мишка, 2 → 3. Едно търсене в hash таблицата, без да минаваш през другите продукти.
- Поръчка 7: слушалки, 1 → 2. Едно търсене в hash таблицата, без да минаваш през другите продукти.
- Поръчка 8: монитор, 1 → 2. Едно търсене в hash таблицата, без да минаваш през другите продукти.
- Поръчка 9: мишка, 3 → 4. Едно търсене в hash таблицата, без да минаваш през другите продукти.
- Поръчка 10: слушалки, 2 → 3. Едно търсене в hash таблицата, без да минаваш през другите продукти.
- 10 поръчки, 10 обновявания на брояча. Подреждат се само 4-те различни продукта по брой, не поръчките.
- Първите три: мишка 4, слушалки 3, монитор 2.
defaultdict(int) създава брояч 0 при първото четене на нов ключ, затова counts[item] += 1 работи и за нов продукт. Първите три идват от подреждане на двойките по брой: подреждат се само различните продукти, не поръчките.
Пробвай
Попълни
Редът, който брои:
counts = defaultdict()defaultdict(int) вика int() за нов ключ, а int() е 0.Виж го
Инструментите на езика
В Python има готов брояч: collections.Counter. Получава списъка и брои сам, за липсващ ключ дава 0, а most_common(k) връща първите k по брой. Равните бройки остават в реда на първото срещане:
from collections import Counter
log = [ "мишка", "слушалки", "мишка", "монитор", "клавиатура", "мишка", "слушалки", "монитор", "мишка", "слушалки",]counts = Counter(log)print(counts["мишка"], counts["таблет"])print(counts.most_common(3))4 0[('мишка', 4), ('слушалки', 3), ('монитор', 2)]defaultdict(int) е по-общият инструмент: същият брояч, но стойността може да е и сума, и списък.
Виж го
Измери: списък от двойки срещу речник
Същите хиляда поръчки с речника:
log = log_of(1000)counts = defaultdict(int)updates = 0for item in log: counts[item] += 1 updates += 1print(f"поръчки: {len(log)}")print(f"продукти: {len(counts)}")print(f"обновявания на брояча: {updates}")поръчки: 1000продукти: 251обновявания на брояча: 10001000 обновявания вместо 125 255 сравнения. Пусни двата начина в браузъра. n е броят поръчки, а каталогът расте с него:
- Списък от двойки продукт и брой
O(n²) - Речник като брояч
O(n)
| Алгоритъм | n = 10 | n = 1000 | n = 100 000 |
|---|---|---|---|
| Списък от двойки продукт и брой | 16 | 125 255 | ≈ 1 252 550 000 |
| Речник като брояч | 10 | 1000 | 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)По-точно, за любопитните
Първите k без да подреждаш всичко. Подреждането на m различни продукта е O(m log m). Ако продуктите са милиони, а трябват първите 10, пазиш heap с най-много k двойки: всяка двойка влиза, а ако станат k + 1, най-малката излиза. Това е O(m log k).
Ключ от няколко части. Броиш продажби по град и продукт: ключът е двойката. В Python е кортеж (city, item): той е неизменим и има hash.
Идеята
Кошницата и комплектът
Комплектът „домашен офис“ е монитор, клавиатура, мишка и два кабела. Складът проверява, че кошницата за изпращане е точно комплектът: нищо в повече, нищо липсващо. Редът не е важен, бройките са.
Един брояч: +1 за всеки продукт от комплекта, −1 за всеки от кошницата. Кошницата съвпада, ако накрая всички бройки са 0.
def matches(kit, basket): return Counter(kit) == Counter(basket)Counter се сравнява с == по бройките, затова цялата проверка е един ред.Същото е проверката за анаграми: „рамка“ и „карма“ имат едни и същи букви със същите бройки. Броячът е по букви вместо по продукти.
Пробвай
Предвиди проверката
from collections import Counter
kit = ["монитор", "клавиатура", "мишка", "кабел", "кабел"]basket1 = [ "кабел", "мишка", "монитор", "кабел", "клавиатура",]basket2 = [ "монитор", "клавиатура", "мишка", "мишка", "кабел",]print(f"кошница 1: {'пълен комплект' if matches(kit, basket1) else 'не съвпада'}")print(f"кошница 2: {'пълен комплект' if matches(kit, basket2) else 'не съвпада'}")Първата кошница има същите пет продукта в друг ред: всички бройки стават 0. Втората има две мишки и един кабел: мишката остава −1, кабелът +1, значи не съвпада, макар че продуктите са пет.
Идеята
Първият клиент с една поръчка
Маркетингът праща ваучер „върни се“ на клиентите, които са поръчали само веднъж. Иска първия такъв по време. Броячът дава бройките, но не и реда:
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"първият клиент с една поръчка: {first_single(customers)}")първият клиент с една поръчка: C-21Две минавания: първото брои, второто върви по дневника, в реда на поръчките, и спира при първия с брой 1. O(n), без вложен цикъл.
По-точно, за любопитните
Защо второто минаване е по дневника, а не по речника? dict пази реда на добавяне (обещано от Python 3.7), затова тук и обхождането на counts би дало същия отговор. Дневникът пак е по-ясен: редът идва от него.
Идеята
Два продукта за точно 50 €
Клиентът има ваучер за точно 50 € и иска два продукта, които да го изчерпят. Цените в каталога не са подредени.
Вървиш по цените и за всяка питаш: виждал ли съм вече цената, която допълва тази до 50? Речникът пази видените цени и мястото им:
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"продукти {a} и {b}: {prices[a]} € + {prices[b]} €")продукти 1 и 5: 14 € + 36 €Едно минаване: O(n) време и O(n) памет. С два указателя става без речник, с O(1) памет, но цените трябва да са подредени. Ако не са, подреждането струва O(n log n) и губи мястото на всеки продукт в каталога. Затова: подредени данни, два указателя; неподредени, речник.
Пробвай
Намери грешката
Някой е разместил два реда. Сега за ваучер от 50 € програмата предлага един продукт два пъти:
prices = [27, 14, 33, 25, 8, 36, 19]a, b = voucher_pair(prices, 50)print(f"продукти {a} и {b}: {prices[a]} € + {prices[b]} €")продукти 3 и 3: 25 € + 25 €Избери реда с грешката.
Цената влиза в речника, преди да се потърси двойката ѝ. Продуктът за 25 € търси 50 − 25 = 25 и намира себе си. Записът трябва да е след търсенето: тогава в речника са само продуктите преди текущия, и програмата намира 14 € + 36 €.
Упражнение
Кой харчи най-много
Реши задачата в редактора си.
Оборот по клиент. Дневникът е от двойки клиент и сума: C-4 за 30 €, C-17 за 55 €, C-4 за 20 €, C-9 за 80 €, C-17 за 10 € и C-4 за 45 €. Събери сумите по клиент с речник (стойността е сума, не брой) и отпечатай двамата, които са похарчили най-много:
C-4: 95 €C-9: 80 €Още задачи
- Анаграми. Напиши проверка дали две думи са анаграми („рамка“ и „карма“), като броиш буквите с речник. Колко операции прави за думи с дължина n?
- Първият повторен. Намери първата поръчка, чийто клиент вече е поръчвал по-рано. Трябва ли ти брояч, или стига множество?
- Периоди с еднакви бройки. От префиксните суми знаеш как се броят периоди с даден сбор. Преброй периодите от поредни дни, в които броят на върнатите поръчки е равен на броя на доставените.
Тест