Хеш таблица като брояч

Код на:JavaC#PythonJavaScript

Накратко: Речникът като брояч (Map в JavaScript) брои колко пъти се среща всеки елемент с едно минаване: O(n) вместо O(n²) с търсене в списък.

Проблем

Най-продаваните продукти за деня

Таблото на магазина показва трите най-продавани продукта за деня. Дневникът е списък от поръчки, по една на ред. Кодът пази два списъка, имената и бройките, и за всяка поръчка търси продукта от началото на имената:

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(`поръчки: ${log.length}`);
console.log(`продукти: ${names.length}`);
console.log(`сравнения: ${comparisons}`);

Изход

поръчки: 1000
продукти: 251
сравнения: 125255

Хиляда поръчки и 251 различни продукта: 125 255 сравнения. Каталогът расте заедно с магазина, а с него и списъкът, който всяка поръчка обхожда. В голям ден с 100 000 поръчки таблото се зарежда минути.

Откъде е дневникът

Дневникът е по формула, за да го построят еднакво програмите на четирите езика и сравнението в браузъра по-долу. Каталогът е n / 4 + 1 продукта:

function logOf(n) {
  const catalog = Math.floor(n / 4) + 1;
  return Array.from({ length: n }, (_, i) => `SKU-${(i * 7919) % catalog}`);
}

Идеята

Речникът брои

В урока „Map и Set“ броеше поръчки с речник. Тук то става техника: hash таблица като брояч (frequency map). Ключът е това, което броиш, стойността е колко пъти си го видял.

• Едно минаване по данните. За всеки елемент: намери брояча му (или 0) и добави 1.
• Търсенето е в hash таблица: средно O(1), колкото и продукти да има. Общо O(n) вместо O(n · m).
• След това отговаряш на въпросите от бройките, а не от данните: кое е най-често, кое е веднъж, дали две неща имат еднакви бройки.

Паметта е O(m): по една двойка за всеки различен продукт.

Виж го

Броячът се пълни

const log = [
  "мишка", "слушалки", "мишка", "монитор",
  "клавиатура", "мишка", "слушалки", "монитор",
  "мишка", "слушалки",
];
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);
}

Изход

мишка 4
слушалки 3
монитор 2

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);
}

Стъпка по стъпка, с думи

1. Празен речник: продукт → колко пъти е продаден. Дневникът има 10 поръчки.
2. Поръчка 1: мишка. Още я няма в речника, затова получава брой 1.
3. Поръчка 2: слушалки. Още я няма в речника, затова получава брой 1.
4. Поръчка 3: мишка, 1 → 2. Едно търсене в hash таблицата, без да минаваш през другите продукти.
5. Поръчка 4: монитор. Още я няма в речника, затова получава брой 1.
6. Поръчка 5: клавиатура. Още я няма в речника, затова получава брой 1.
7. Поръчка 6: мишка, 2 → 3. Едно търсене в hash таблицата, без да минаваш през другите продукти.
8. Поръчка 7: слушалки, 1 → 2. Едно търсене в hash таблицата, без да минаваш през другите продукти.
9. Поръчка 8: монитор, 1 → 2. Едно търсене в hash таблицата, без да минаваш през другите продукти.
10. Поръчка 9: мишка, 3 → 4. Едно търсене в hash таблицата, без да минаваш през другите продукти.
11. Поръчка 10: слушалки, 2 → 3. Едно търсене в hash таблицата, без да минаваш през другите продукти.
12. 10 поръчки, 10 обновявания на брояча. Подреждат се само 4-те различни продукта по брой, не поръчките.
13. Първите три: мишка 4, слушалки 3, монитор 2.

counts.get(item) ?? 0 дава 0 за продукт, който още го няма. Скобите около него са нужни: без тях + 1 се смята преди ??. Първите три идват от подреждане на двойките по брой: подреждат се само различните продукти, не поръчките.

Пробвай

Попълни

Редът, който брои:

counts.set(item, (counts.get(item)  0) + 1);

Провери

Виж го

Инструментите на езика

JavaScript няма готов брояч. Map с get, ?? 0 и set е обичайният начин. Обикновен обект също става, но има наследени ключове ("constructor", "toString") и превръща всеки ключ в текст. Map обхожда ключовете в реда на добавяне:

const log = [
  "мишка", "слушалки", "мишка", "монитор",
  "клавиатура", "мишка", "слушалки", "монитор",
  "мишка", "слушалки",
];
const counts = new Map();
for (const item of log) counts.set(item, (counts.get(item) ?? 0) + 1);
console.log(counts.get("мишка"), counts.get("таблет") ?? 0);
for (const [item, n] of counts) console.log(item, n);

Изход

4 0
мишка 4
слушалки 3
монитор 2
клавиатура 1

Виж го

Измери: списък от двойки срещу речник

Същите хиляда поръчки с речника:

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(`поръчки: ${log.length}`);
console.log(`продукти: ${counts.size}`);
console.log(`обновявания на брояча: ${updates}`);

Изход

поръчки: 1000
продукти: 251
обновявания на брояча: 1000

1000 обновявания вместо 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

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

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);
}

По-точно, за любопитните

Първите k без да подреждаш всичко. Подреждането на m различни продукта е O(m log m). Ако продуктите са милиони, а трябват първите 10, пазиш heap с най-много k двойки: всяка двойка влиза, а ако станат k + 1, най-малката излиза. Това е O(m log k).

Ключ от няколко части. Броиш продажби по град и продукт: ключът е двойката. В JavaScript Map сравнява обектите по референция, затова ключът е текст: `${city}|${item}`.

Идеята

Кошницата и комплектът

Комплектът „домашен офис“ е монитор, клавиатура, мишка и два кабела. Складът проверява, че кошницата за изпращане е точно комплектът: нищо в повече, нищо липсващо. Редът не е важен, бройките са.

Един брояч: +1 за всеки продукт от комплекта, −1 за всеки от кошницата. Кошницата съвпада, ако накрая всички бройки са 0.

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);
}

Същото е проверката за анаграми: „рамка“ и „карма“ имат едни и същи букви със същите бройки. Броячът е по букви вместо по продукти.

Пробвай

Предвиди проверката

const kit = [
  "монитор", "клавиатура", "мишка", "кабел",
  "кабел",
];
const basket1 = [
  "кабел", "мишка", "монитор", "кабел",
  "клавиатура",
];
const basket2 = [
  "монитор", "клавиатура", "мишка", "мишка",
  "кабел",
];
console.log(`кошница 1: ${matches(kit, basket1) ? "пълен комплект" : "не съвпада"}`);
console.log(`кошница 2: ${matches(kit, basket2) ? "пълен комплект" : "не съвпада"}`);

Отговор

кошница 1: пълен комплект
кошница 2: не съвпада

кошница 1: не съвпада
кошница 2: пълен комплект

кошница 1: пълен комплект
кошница 2: пълен комплект

Провери

Идеята

Първият клиент с една поръчка

Маркетингът праща ваучер „върни се“ на клиентите, които са поръчали само веднъж. Иска първия такъв по време. Броячът дава бройките, но не и реда:

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(`първият клиент с една поръчка: ${firstSingle(customers)}`);

Изход

първият клиент с една поръчка: C-21

Две минавания: първото брои, второто върви по дневника, в реда на поръчките, и спира при първия с брой 1. O(n), без вложен цикъл.

По-точно, за любопитните

Защо второто минаване е по дневника, а не по речника? Map обхожда в реда на добавяне (обещано от спецификацията), затова тук и обхождането на counts би дало същия отговор. Дневникът пак е по-ясен: редът идва от него.

Идеята

Два продукта за точно 50 €

Клиентът има ваучер за точно 50 € и иска два продукта, които да го изчерпят. Цените в каталога не са подредени.

Вървиш по цените и за всяка питаш: виждал ли съм вече цената, която допълва тази до 50? Речникът пази видените цени и мястото им:

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(`продукти ${a} и ${b}: ${prices[a]} € + ${prices[b]} €`);

Изход

продукти 1 и 5: 14 € + 36 €

Едно минаване: O(n) време и O(n) памет. С два указателя става без речник, с O(1) памет, но цените трябва да са подредени. Ако не са, подреждането струва O(n log n) и губи мястото на всеки продукт в каталога. Затова: подредени данни, два указателя; неподредени, речник.

Пробвай

Намери грешката

Някой е разместил два реда. Сега за ваучер от 50 € програмата предлага един продукт два пъти:

const prices = [27, 14, 33, 25, 8, 36, 19];
const [a, b] = voucherPair(prices, 50);
console.log(`продукти ${a} и ${b}: ${prices[a]} € + ${prices[b]} €`);

Изход

продукти 3 и 3: 25 € + 25 €

Избери реда с грешката.

1function voucherPair(prices, voucher) {2 const seen = new Map();3 for (let i = 0; i < prices.length; i++) {4 seen.set(prices[i], i);5 const j = seen.get(voucher - prices[i]);6 if (j !== undefined) return [j, i];7 }8 return null;9}

Провери

Упражнение

Кой харчи най-много

Реши задачата в редактора си.

Оборот по клиент. Дневникът е от двойки клиент и сума: 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?
• Първият повторен. Намери първата поръчка, чийто клиент вече е поръчвал по-рано. Трябва ли ти брояч, или стига множество?
• Периоди с еднакви бройки. От префиксните суми знаеш как се броят периоди с даден сбор. Преброй периодите от поредни дни, в които броят на върнатите поръчки е равен на броя на доставените.

Тест

Провери се

1. Дневникът има 100 000 поръчки и 25 000 различни продукта. Колко обновявания на брояча прави речникът?

25 000: по едно на продукт100 000 · 25 000100 000: по едно на поръчка

2. Как проверяваш с един речник, че кошницата е точно комплектът?

Подреждаш двата списъка и ги сравняваш, речник не трябва+1 за всеки продукт от комплекта, −1 за всеки от кошницата, и всички бройки трябва да са 0Проверяваш, че всеки продукт от кошницата е в комплекта

3. В voucherPair цената влиза в речника след търсенето на двойката ѝ. Защо не преди?

Заради скоросттаИначе продукт за 25 € намира себе си за ваучер от 50 €Без значение е

4. Кога два указателя са по-добрият избор за двойка с дадена сума?

Винаги, защото са по-бързиКогато цените вече са подредени: без речник и без допълнителна паметНикога

5. Трябват ти първите 10 от 2 000 000 различни продукта. Кое е най-евтино?

Да подредиш всички 2 000 000 двойкиДесет пъти търсене на най-големияHeap с най-много 10 елемента: O(m log k)

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Хеш таблица · Приоритетна опашка · Два указателя · Префиксни суми
• Задачи по темата: Техники за задачи