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

Проблем

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

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

List<String> log = logOf(1000);
List<String> names = new ArrayList<>();
List<Integer> counts = new ArrayList<>();
long comparisons = 0;
for (String item : log) {
    int i = 0;
    while (i < names.size()) {
        comparisons++;
        if (names.get(i).equals(item)) break;
        i++;
    }
    if (i == names.size()) {
        names.add(item);
        counts.add(1);
    } else {
        counts.set(i, counts.get(i) + 1);
    }
}
System.out.println("поръчки: " + log.size());
System.out.println("продукти: " + names.size());
System.out.println("сравнения: " + comparisons);

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

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

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

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

static List<String> logOf(int n) {
    int catalog = n / 4 + 1;
    List<String> log = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        log.add("SKU-" + (i * 7919) % catalog);
    }
    return log;
}

Идеята

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

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

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

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

Виж го

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

List<String> log = List.of(
    "мишка", "слушалки", "мишка", "монитор",
    "клавиатура", "мишка", "слушалки", "монитор",
    "мишка", "слушалки");
Map<String, Integer> counts = new HashMap<>();
for (String item : log) {
    counts.merge(item, 1, Integer::sum);
}
List<Map.Entry<String, Integer>> top =
    new ArrayList<>(counts.entrySet());
top.sort((x, y) -> y.getValue() - x.getValue());
for (var e : top.subList(0, 3)) {
    System.out.println(e.getKey() + " " + e.getValue());
}

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

Map<String, Integer> counts = new HashMap<>();
for (String item : log) {
    counts.merge(item, 1, Integer::sum);
}
List<Map.Entry<String, Integer>> top =
    new ArrayList<>(counts.entrySet());
top.sort((x, y) -> y.getValue() - x.getValue());
for (var e : top.subList(0, 3)) {
    System.out.println(e.getKey() + " " + e.getValue());
}

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

Празен речник: продукт → колко пъти е продаден. Дневникът има 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.

merge(item, 1, Integer::sum) слага 1, ако ключа го няма, а иначе събира стария брой с 1. Първите три идват от подреждане на двойките по брой: подреждат се само различните продукти, не поръчките.

Пробвай

Попълни

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

counts.merge(item, 1, );

merge получава как да събере стария брой с новия: Integer::sum.

Виж го

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

В Java броячът е HashMap<String, Integer>. getOrDefault с put прави същото като merge, но търси ключа два пъти. merge го търси веднъж. Когато трябва подредени ключове, Collectors.groupingBy с TreeMap и Collectors.counting() брои в поток:

List<String> log = List.of(
    "мишка", "слушалки", "мишка", "монитор",
    "клавиатура", "мишка", "слушалки", "монитор",
    "мишка", "слушалки");
Map<String, Integer> counts = new HashMap<>();
for (String item : log) {
    counts.put(item, counts.getOrDefault(item, 0) + 1);
}
System.out.println(counts.get("мишка") + " " + counts.getOrDefault("таблет", 0));
Map<String, Long> sorted = log.stream()
    .collect(Collectors.groupingBy(item -> item, TreeMap::new, Collectors.counting()));
System.out.println(sorted);

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

Виж го

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

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

List<String> log = logOf(1000);
Map<String, Integer> counts = new HashMap<>();
long updates = 0;
for (String item : log) {
    counts.merge(item, 1, Integer::sum);
    updates++;
}
System.out.println("поръчки: " + log.size());
System.out.println("продукти: " + counts.size());
System.out.println("обновявания на брояча: " + 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 не пускаме, за да не замръзне страницата.

Map<String, Integer> counts = new HashMap<>();
for (String item : log) {
    counts.merge(item, 1, Integer::sum);
}
List<Map.Entry<String, Integer>> top =
    new ArrayList<>(counts.entrySet());
top.sort((x, y) -> y.getValue() - x.getValue());
for (var e : top.subList(0, 3)) {
    System.out.println(e.getKey() + " " + e.getValue());
}

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

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

Ключ от няколко части. Броиш продажби по град и продукт: ключът е двойката. В Java е record CityItem(String city, String item): record има equals и hashCode по полетата.

Идеята

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

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

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

static boolean matches(List<String> kit, List<String> basket) {
    Map<String, Integer> need = new HashMap<>();
    for (String item : kit) need.merge(item, 1, Integer::sum);
    for (String item : basket) need.merge(item, -1, Integer::sum);
    for (int n : need.values()) {
        if (n != 0) return false;
    }
    return true;
}

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

Пробвай

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

List<String> kit = List.of(
    "монитор", "клавиатура", "мишка", "кабел",
    "кабел");
List<String> basket1 = List.of(
    "кабел", "мишка", "монитор", "кабел",
    "клавиатура");
List<String> basket2 = List.of(
    "монитор", "клавиатура", "мишка", "мишка",
    "кабел");
System.out.println("кошница 1: " + (matches(kit, basket1) ? "пълен комплект" : "не съвпада"));
System.out.println("кошница 2: " + (matches(kit, basket2) ? "пълен комплект" : "не съвпада"));

Отговор

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

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

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

Идеята

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

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

static String firstSingle(List<String> customers) {
    Map<String, Integer> counts = new HashMap<>();
    for (String c : customers) counts.merge(c, 1, Integer::sum);
    for (String c : customers) {
        if (counts.get(c) == 1) return c;
    }
    return null;
}

List<String> customers = List.of(
    "C-17", "C-4", "C-17", "C-9",
    "C-4", "C-21", "C-9", "C-30");
System.out.println("първият клиент с една поръчка: " + firstSingle(customers));

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

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

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

Защо второто минаване е по дневника, а не по речника? HashMap не пази никакъв ред: обхождането му е по кофи. LinkedHashMap пази реда на добавяне и тогава става и обхождане на речника.

Идеята

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

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

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

static int[] voucherPair(int[] prices, int voucher) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < prices.length; i++) {
        Integer j = seen.get(voucher - prices[i]);
        if (j != null) return new int[] { j, i };
        seen.put(prices[i], i);
    }
    return null;
}

int[] prices = { 27, 14, 33, 25, 8, 36, 19 };
int[] p = voucherPair(prices, 50);
System.out.println("продукти " + p[0] + " и " + p[1] + ": " + prices[p[0]] + " € + " + prices[p[1]] + " €");

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

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

Пробвай

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

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

int[] prices = { 27, 14, 33, 25, 8, 36, 19 };
int[] p = voucherPair(prices, 50);
System.out.println("продукти " + p[0] + " и " + p[1] + ": " + prices[p[0]] + " € + " + prices[p[1]] + " €");

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

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

Упражнение

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

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

Оборот по клиент. Дневникът е от двойки клиент и сума: 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)

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

Бисквитки