Hammerhall Сколько стоит Войти

Множество как ключ карты: самые популярные комбо

Статья 2 · читать минут 20

Для кого. Ты прочитал статью 1 или знаешь то же сам: множества равны по содержимому, retainAll меняет множество на месте. Из «Стримов по шагам» помнишь groupingBy с counting(), «топ-N» с правилом ничьей, equals с hashCode у записи и неизменяемую копию List.copyOf.

Что будет. Как одной группировкой найти самые популярные комбо, если ключ карты — множество; почему множество годится в ключ, а печатать его как есть не стоит; что случится, если поменять ключ после того, как положил его в карту; чем список в ключе отличается от множества; во сколько раз группировка дешевле сравнения «все со всеми».

Откуда серия. Её пишет команда платформы Hammerhall. Задачи на алгоритмы — в кузнице Stream Forge на платформе, в слое mind; здесь — теория к ним: приём, его цена и где он ломается. Примеры учебные: каждый запускается одним файлом.

Зачем множество в ключе#

Хозяйка «Наковальни» хочет повесить у кассы «комбо месяца» — три набора, которые берут вместе чаще всего, — и дать на них скидку. Данные — месяц заказов из статьи 1: orders(42, 300, 30), 2843 заказа.

Комбо — набор позиций одного заказа: «латте + круассан». Порядок в нём не важен: пробил бариста сначала круассан, потом латте — комбо то же. Значит, нужно найти заказы с одинаковыми наборами и посчитать, сколько их у каждого набора.

Первое, что приходит в голову, — сравнить заказы попарно: первый — со вторым, с третьим и так до последнего, потом второй — со всеми после него. Для 2843 заказов это четыре миллиона сравнений. И это ещё не ответ: найденные равные пары надо потом собрать в группы.

Хватит одного прохода. «Что одинаковое» — вопрос группировки: одинаковые заказы сами лягут в одну стопку, если ключ стопки — набор позиций. Ключом карты станет множество. В этой статье — как это сделать, что при этом ломается и сколько работы это экономит.

Часть 1. Заказ как множество#

Комбо — множество названий#

Позиции заказа лежат списком Item, а у Item кроме названия есть цена и количество. equals записи сравнивает все поля — помнишь статью 4 «Стримов», — и «латте, 2 штуки» для него не равен «латте, 1 штука». Для комбо важны только названия, а порядок не важен. Значит, комбо — множество названий:

/** Комбо заказа — названия его позиций множеством: порядок и количество не важны. */
Set<String> combo(Order order) {
    return Set.copyOf(order.items().stream().map(Item::name).toList());
}

Set.copyOf(список) — неизменяемое множество из элементов списка, повторы отбросит; как List.copyOf из статьи 10 «Стримов». Зачем ключу неизменяемость, увидишь в части 3. Комбо первых двух заказов месяца:

IO.println(combo(orders.get(0)) + " " + combo(orders.get(1)));
[чай, какао] [эклер, капучино]

Запусти ещё раз — у нас вышло так:

[какао, чай] [капучино, эклер]

⚠️ Множество не обещает порядок печати

Множества те же, а порядок в скобках другой: у Set.of и Set.copyOf он не задан и меняется от запуска к запуску — помнишь статью 1. Для доски у кассы нужна своя подпись — названия по алфавиту.

Коллекторы в кусках статьи пишутся без Collectors.: статический импорт, как в статье 6 «Стримов», стоит в «Примере целиком».

/** Комбо для печати: названия по алфавиту через « + ». */
String label(Set<String> combo) {
    return combo.stream().sorted().collect(joining(" + "));
}
IO.println(label(combo(orders.get(0))) + " | " + label(combo(orders.get(1))));
какао + чай | капучино + эклер

Эта строка одинакова при любом запуске. Другой способ — new TreeSet<>(combo): TreeSet хранит элементы по порядку и так же их печатает.

Почему множество годится в ключ

HashMap ищет ключ так же, как HashSet ищет элемент: по hashCode находит место, а там сравнивает equals — номерок и крючок в гардеробе из статьи 4 «Стримов». Значит, у двух одинаковых комбо должны совпасть и equals, и hashCode — в каком бы порядке ни пробили позиции и каким бы классом ни собрали множество.

Set<String> a = Set.of("латте", "круассан");
Set<String> b = new TreeSet<>(List.of("круассан", "латте"));
IO.println(a.equals(b) + " " + (a.hashCode() == b.hashCode()));
true true

Оба true — не удача, а договор интерфейса Set. Множества равны, если у них одинаковый размер и каждый элемент одного есть в другом. А hashCode множества — коротко его называют хешем — по документации равен сумме хешей его элементов. От перестановки слагаемых сумма не меняется, поэтому порядок на номерок не влияет. И считают его так все множества: HashSet, TreeSet, Set.of.

🔑 Множество годится в ключ карты, потому что его equals и hashCode зависят только от содержимого — не от порядка и не от класса.

Часть 2. Группировка по множеству

Одна группировка — все наборы#

Ключ есть — дальше groupingBy с counting() из статьи 5 «Стримов»:

Map<Set<String>, Long> byCombo = orders.stream()
        .collect(groupingBy(order -> combo(order), counting()));
IO.println("разных наборов: " + byCombo.size());
разных наборов: 260

Тип карты читается как вопрос: «набор позиций → сколько заказов». 2843 заказа легли в 260 стопок.

Теперь три самых частых. «Топ-N» с правилом ничьей — из статьи 7 «Стримов»; он понадобится дважды, поэтому вынесем его в метод:

/** Первые {@code n} комбо по числу заказов; при равном счёте — по алфавиту. */
List<String> top(Map<Set<String>, Long> counts, int n) {
    return counts.entrySet().stream()
            .sorted(Map.Entry.<Set<String>, Long>comparingByValue().reversed()
                    .thenComparing(entry -> label(entry.getKey())))   // правило ничьей
            .limit(n)
            .map(entry -> label(entry.getKey()) + " — " + entry.getValue())
            .toList();
}

Сначала — больше заказов, при равном счёте — по алфавиту подписи. Подсказка типа <Set<String>, Long> — та же, что в статье 7 «Стримов»: без неё цепочка после comparingByValue() не скомпилируется. Ничью решает именно подпись: у множеств нет естественного порядка, как у чисел или строк, — какое из двух «меньше», Java не знает.

IO.println(top(byCombo, 3));
[эклер — 114, эспрессо — 112, чай — 106]

Одна позиция — ещё не комбо#

Ответ честный, но на другой вопрос. В лидерах — заказы из одной позиции: зашёл за эклером — ушёл с эклером. Таких за месяц 1160 из 2843. Хозяйке нужны наборы, поэтому одиночные заказы отсеем до группировки (названия внутри заказа генератор не повторяет, так что две позиции — это и два названия):

Map<Set<String>, Long> combos = orders.stream()
        .filter(order -> order.items().size() >= 2)              // одна позиция — ещё не комбо
        .collect(groupingBy(order -> combo(order), counting()));
IO.println("комбо: " + combos.size());
IO.println(top(combos, 3));
комбо: 248
[круассан + латте — 36, круассан + сырник — 29, матча + эспрессо — 29]

Вот и доска: латте с круассаном — 36 заказов за месяц. На втором месте ничья, и её решило правило: «круассан + сырник» раньше по алфавиту.

💡 Ключ — набор целиком. Заказ «круассан + латте + раф» — другое комбо, в эти 36 он не вошёл.

Часть 3. Каким должен быть ключ

⚠️ Изменённый ключ карта теряет

combo собирает множество через Set.copyOf. Почему не обычным HashSet? Посмотрим, что бывает с ключом, который можно менять. Доска — карта, ключ — HashSet:

Map<Set<String>, Long> board = new HashMap<>();
Set<String> key = new HashSet<>(List.of("латте", "круассан"));   // изменяемое множество
board.put(key, 36L);
IO.println(board.get(Set.of("латте", "круассан")));
key.add("раф");                                                  // изменили после put
IO.println(board.get(Set.of("латте", "круассан")));              // по старому содержимому
IO.println(board.get(Set.of("латте", "круассан", "раф")));       // по новому содержимому
IO.println(board.containsKey(key));                              // по тому же объекту
IO.println(board);
36
null
null
false
{[раф, латте, круассан]=36}

Пара в карте есть — её видно на печати. Но найти её нельзя ни по старому содержимому, ни по новому, ни даже по тому самому объекту, который положили.

Почему так. put посчитал номерок — хеш множества «латте, круассан» — и повесил пару на этот крючок. add поменял содержимое, а с ним и хеш: слагаемых теперь три. Ищешь по новому содержимому или по тому же объекту — номерок новый, а пара висит под старым. Ищешь по старому — крючок тот, но equals не сходится: на крючке уже три позиции, а ищешь ты две. Ошибки нет, исключения нет — карта просто перестала находить свою пару.

Документация Map об этом предупреждает: с изменяемыми ключами нужна большая осторожность; если ключ изменился так, что это задевает equals, поведение карты не определено. «Не определено» — значит, не обязательно null: в другой карте или другой версии Java может выйти иначе. Полагаться не на что.

Нарочно так никто не пишет. Ключ меняют мимоходом: взяли ключи карты, чтобы оставить в комбо одни напитки, и вызвали retainAll из статьи 1 — он меняет множество на месте. Или собрали ключ через collect(toSet()): документация toSet() не обещает ни класса, ни неизменяемости, а на JDK 25 это HashSet — его менять можно.

Неизменяемый ключ ломается громко

Замени в куске выше new HashSet<>(List.of("латте", "круассан")) на Set.copyOf(List.of("латте", "круассан")) — первая 36 напечатается, а на key.add("раф") программа упадёт:

Exception in thread "main" java.lang.UnsupportedOperationException

Неизменяемое множество не даёт себя поменять: любая попытка — исключение сразу, на той строке, где ошибка. Для ключа это то, что нужно. Тот же ключ одним коллектором — collect(toUnmodifiableSet()).

🔑 Ключ карты — только неизменяемый. Изменяемый ключ ломает карту молча и потом, неизменяемый — громко и сразу, там, где его пытаются поменять.

Список или множество: порядок в ключе

А почему не список? Список тоже бывает ключом, а toList() стрима даже неизменяемый:

Map<List<String>, Long> byList = orders.stream()
        .collect(groupingBy(order -> order.items().stream().map(Item::name).toList(),
                counting()));
IO.println("разных списков: " + byList.size());
IO.println(byList.get(List.of("латте", "круассан")) + " + "
        + byList.get(List.of("круассан", "латте")));
разных списков: 518
15 + 21

518 ключей вместо 260. Латте с круассаном разъехались на два ключа: 15 заказов в одном порядке и 21 в другом — вместе те же 36. У списка equals учитывает порядок: по документации List, два списка равны, если в них те же элементы в том же порядке. И хеш списка считается с порядком — перед каждым следующим элементом накопленное число умножают на 31, — так что номерки у двух списков, как правило, разные. А раздельными ключами их делает equals: даже при одинаковом номерке список с другим порядком — другой ключ.

Список годится в ключ, когда порядок — часть вопроса. Если не часть, отсортируй названия перед тем, как сделать ключ:

Map<List<String>, Long> bySorted = orders.stream()
        .collect(groupingBy(order -> order.items().stream().map(Item::name).sorted().toList(),
                counting()));
IO.println("разных отсортированных списков: " + bySorted.size());
разных отсортированных списков: 260

Снова 260, и такой ключ ещё и печатается одинаково при каждом запуске. Но множество говорит о намерении прямо: «порядок не важен» видно из типа ключа, а sorted() легко забыть.

Часть 4. Цена: группировка против «все со всеми»

Все со всеми#

Вернёмся к первой идее из «Зачем» — пары «все со всеми»: сравнить каждый заказ с каждым другим. Пар из n заказов — n·(n−1)/2, для 2843 это 2843·2842/2 = 4 039 903. Откуда формула и почему она растёт вчетверо — в статье 3. Здесь проверим число счётчиком, хватит двух циклов:

List<Set<String>> sets = orders.stream().map(order -> combo(order)).toList();
long comparisons = 0;
long equalPairs = 0;
for (int i = 0; i < sets.size(); i++) {
    for (int j = i + 1; j < sets.size(); j++) {                  // j после i: пара — один раз
        comparisons++;
        if (sets.get(i).equals(sets.get(j))) {
            equalPairs++;
        }
    }
}
IO.println("все со всеми: сравнений " + comparisons + ", равных пар " + equalPairs);
все со всеми: сравнений 4039903, равных пар 68736

Внутренний цикл начинается с i + 1 — каждая пара проверяется один раз. Нашлось 68 736 пар одинаковых заказов — но это только пары. «Круассан + латте — 36» из них ещё предстоит собрать.

Одна группировка#

Теперь группировка — со счётчиком, сколько раз она вызвала функцию ключа. Счётчик — поле рядом с методами, как в статье 9 «Стримов»: менять переменную метода из лямбды Java не даёт.

long lookups = 0;   // сколько раз группировка вызвала функцию ключа — только чтобы увидеть работу
Map<Set<String>, Long> groups = orders.stream()
        .collect(groupingBy(order -> {
            lookups++;                                           // один заказ — один ключ
            return combo(order);
        }, counting()));
long pairsInGroups = groups.values().stream()
        .mapToLong(count -> count * (count - 1) / 2)             // пары внутри группы
        .sum();
IO.println("группировка: обращений к карте " + lookups
        + ", равных пар в группах " + pairsInGroups);
группировка: обращений к карте 2843, равных пар в группах 68736

На каждый заказ groupingBy один раз считает ключ и один раз идёт в карту за стопкой этого ключа: 2843 заказа — 2843 обращения.

А равные пары никуда не делись. Два заказа одинаковы — значит, они в одной стопке. В стопке из c заказов пар c·(c−1)/2 — та же формула: у «круассан + латте» 36·35/2 = 630. Сумма по всем стопкам — те же 68 736. Группировка знает всё, что нашёл перебор, и сверх того — счёт по каждому комбо.

Итог: 2843 обращения к карте вместо 4 039 903 сравнений — в 1421 раз меньше, ровно (n−1)/2. Честная оговорка: обращение к карте — не одна операция. Надо посчитать хеш множества (сложить до трёх чисел) и сравнить ключ через equals. Но это несколько шагов, и их число не зависит от размера карты: документация HashMap обещает для get и put постоянное время, если хеши раскладывают ключи равномерно. Сравнение двух множеств в переборе — тоже несколько шагов. Разница — в том, сколько раз эти шаги делают.

Вдвое больше заказов#

Тот же опыт на месяцах побольше — orders(42, n, 30) для 1000, 2000 и 4000 гостей:

гостей заказов обращений к карте сравнений «все со всеми»
300 2 843 2 843 4 039 903
1000 9 834 9 834 48 348 861
2000 19 568 19 568 191 443 528
4000 38 969 38 969 759 271 996

Гостей вдвое больше — заказов почти вдвое больше, и обращений к карте тоже. А сравнений — вчетверо: n·(n−1)/2 растёт как квадрат n. Время — только иллюстрация: в наших прогонах на 4000 гостях перебор пар шёл больше 15 секунд, группировка — меньше 50 миллисекунд. У тебя числа будут другие, рост — тот же.

🔑 Если вопрос — «что одинаковое», пары не нужны: одинаковое само ляжет под один ключ. Пары нужны, когда общего ключа нет: «кто тратит почти столько же», «чьи наборы похожи». Равенства там нет, и группировка не поможет.

Проверь себя#

Ответь своими словами — вслух или на бумаге. Не получается — перечитай раздел.

  1. Почему комбо — множество названий, а не список позиций Item? Что пошло бы не так, если бы в множество клали Item целиком?
  2. Почему Set.of("латте", "круассан") и TreeSet с теми же словами в другом порядке — один и тот же ключ карты? Что для этого обещает документация Set?
  3. Почему комбо печатают через label, а не как есть? Что увидишь, если запустить пример дважды?
  4. В первом «топ-3» оказались эклер, эспрессо и чай. Почему это ответ не на тот вопрос и как его поправили?
  5. Ключ-HashSet положили в карту, потом добавили в него «раф». Почему пару не находит ни старое содержимое, ни новое, ни тот же объект?
  6. Попытку поменять ключ кто-нибудь всё равно однажды напишет. Чем тогда неизменяемый ключ лучше изменяемого?
  7. Почему ключей-списков 518, а ключей-множеств 260? Как сделать список, который годится в ключ комбо?
  8. Сколько сравнений делают пары «все со всеми» на n заказах и сколько обращений к карте — группировка? Как вырастет каждое число, если заказов вдвое больше?

Что дальше#

Статья 3 — пары «все со всеми»: как перебрать пары без повторов, почему n·(n−1)/2 не взлетает на больших данных и что делать, когда вопрос не «что одинаковое», а «что ближе».

Первоисточники#

Пример целиком#

Учебный пример — один файл. Нужен JDK 25: проверь командой java -version, первая строка должна начинаться с openjdk version "25 (или java version "25). С JDK из курса, 17 или 21, файл не запустится.

Записи, меню и генератор заказов стоят вверху файла — они одинаковые во всех статьях серии, генератор читать не обязательно. Методы и main — без класса вокруг: в Java 25 такой файл сам становится классом, а void main() без public static и без параметров — точкой входа. Блоки main пронумерованы по порядку статьи. Сохрани файл как Coffee.java и запусти из его папки:

java Coffee.java

Java сама скомпилирует файл и выполнит main — ни Maven, ни проекта не нужно. Если вместо русских букв в выводе вопросы или кракозябры, запусти с явной кодировкой — аргументы в кавычках, так их поймёт и PowerShell: java "-Dstdout.encoding=UTF-8" "-Dstderr.encoding=UTF-8" Coffee.java; в командной строке Windows перед этим выполни chcp 65001.

// Coffee.java — учебный пример статьи 2 серии «Алгоритмы на стримах».
// Запуск: java Coffee.java (нужен JDK 25)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

import static java.util.stream.Collectors.*;

/** Позиция заказа: название, цена за штуку в рублях, сколько штук. */
record Item(String name, int price, int qty) {}

/** Заказ: номер, день месяца, номер карты гостя, позиции. */
record Order(int number, int day, int guest, List<Item> items) {

    /** Сумма заказа в рублях. */
    int total() {
        return items.stream().mapToInt(item -> item.price() * item.qty()).sum();
    }
}

/** Меню кофейни «Наковальня»: название и цена в рублях, по одной штуке. */
static final List<Item> MENU = List.of(
        new Item("латте", 250, 1), new Item("капучино", 220, 1), new Item("эспрессо", 150, 1),
        new Item("американо", 170, 1), new Item("раф", 290, 1), new Item("какао", 200, 1),
        new Item("матча", 280, 1), new Item("чай", 120, 1), new Item("круассан", 180, 1),
        new Item("чизкейк", 320, 1), new Item("сырник", 210, 1), new Item("эклер", 190, 1));

/**
 * Заказы {@code guests} гостей за {@code days} дней. Одно и то же зерно —
 * одни и те же заказы на любом компьютере. Генератор — не тема статьи:
 * читать его не обязательно.
 */
List<Order> orders(long seed, int guests, int days) {
    Random random = new Random(seed);
    List<List<Item>> liked = new ArrayList<>();          // у каждого гостя три любимые позиции
    List<Double> chance = new ArrayList<>();             // и своя вероятность зайти в день
    for (int guest = 0; guest < guests; guest++) {
        List<Item> three = new ArrayList<>();
        while (three.size() < 3) {
            Item item = MENU.get(random.nextInt(MENU.size()));
            if (!three.contains(item)) {
                three.add(item);
            }
        }
        liked.add(List.copyOf(three));
        chance.add(0.05 + random.nextInt(12) * 0.05);
    }
    List<Order> orders = new ArrayList<>();
    for (int day = 1; day <= days; day++) {
        for (int guest = 0; guest < guests; guest++) {
            if (random.nextDouble() >= chance.get(guest)) {
                continue;                                 // сегодня этот гость не пришёл
            }
            List<Item> items = new ArrayList<>();
            int positions = 1 + random.nextInt(3);
            for (int i = 0; i < positions; i++) {
                Item pick = random.nextInt(4) < 3
                        ? liked.get(guest).get(random.nextInt(3))       // обычно — любимое
                        : MENU.get(random.nextInt(MENU.size()));       // иногда — что-то ещё
                int qty = random.nextInt(10) == 0 ? 2 : 1;
                if (items.stream().noneMatch(item -> item.name().equals(pick.name()))) {
                    items.add(new Item(pick.name(), pick.price(), qty));
                }
            }
            orders.add(new Order(orders.size() + 1, day, guest + 1, List.copyOf(items)));
        }
    }
    return List.copyOf(orders);
}

/** Комбо заказа — названия его позиций множеством: порядок и количество не важны. */
Set<String> combo(Order order) {
    return Set.copyOf(order.items().stream().map(Item::name).toList());
}

/** Комбо для печати: названия по алфавиту через « + ». */
String label(Set<String> combo) {
    return combo.stream().sorted().collect(joining(" + "));
}

/** Первые {@code n} комбо по числу заказов; при равном счёте — по алфавиту. */
List<String> top(Map<Set<String>, Long> counts, int n) {
    return counts.entrySet().stream()
            .sorted(Map.Entry.<Set<String>, Long>comparingByValue().reversed()
                    .thenComparing(entry -> label(entry.getKey())))   // правило ничьей
            .limit(n)
            .map(entry -> label(entry.getKey()) + " — " + entry.getValue())
            .toList();
}

long lookups = 0;   // сколько раз группировка вызвала функцию ключа — только чтобы увидеть работу

void main() {
    List<Order> orders = orders(42, 300, 30);

    // 1. Комбо первых двух заказов: порядок внутри Set.copyOf не обещан, label — по алфавиту
    IO.println(combo(orders.get(0)) + " " + combo(orders.get(1)));
    IO.println(label(combo(orders.get(0))) + " | " + label(combo(orders.get(1))));

    // 2. Равные множества: equals по содержимому, hashCode один и тот же
    Set<String> a = Set.of("латте", "круассан");
    Set<String> b = new TreeSet<>(List.of("круассан", "латте"));
    IO.println(a.equals(b) + " " + (a.hashCode() == b.hashCode()));

    // 3. Группировка по множеству — все заказы
    Map<Set<String>, Long> byCombo = orders.stream()
            .collect(groupingBy(order -> combo(order), counting()));
    IO.println("разных наборов: " + byCombo.size());
    IO.println(top(byCombo, 3));

    // 4. Комбо — от двух позиций
    Map<Set<String>, Long> combos = orders.stream()
            .filter(order -> order.items().size() >= 2)              // одна позиция — ещё не комбо
            .collect(groupingBy(order -> combo(order), counting()));
    IO.println("комбо: " + combos.size());
    IO.println(top(combos, 3));

    // 5. Изменяемый ключ: положили в карту, потом изменили
    Map<Set<String>, Long> board = new HashMap<>();
    Set<String> key = new HashSet<>(List.of("латте", "круассан"));   // изменяемое множество
    board.put(key, 36L);
    IO.println(board.get(Set.of("латте", "круассан")));
    key.add("раф");                                                  // изменили после put
    IO.println(board.get(Set.of("латте", "круассан")));              // по старому содержимому
    IO.println(board.get(Set.of("латте", "круассан", "раф")));       // по новому содержимому
    IO.println(board.containsKey(key));                              // по тому же объекту
    IO.println(board);

    // 6. Список в ключе: порядок позиций делит одно комбо на два
    Map<List<String>, Long> byList = orders.stream()
            .collect(groupingBy(order -> order.items().stream().map(Item::name).toList(),
                    counting()));
    IO.println("разных списков: " + byList.size());
    IO.println(byList.get(List.of("латте", "круассан")) + " + "
            + byList.get(List.of("круассан", "латте")));

    // 7. Отсортированный список — снова одно комбо
    Map<List<String>, Long> bySorted = orders.stream()
            .collect(groupingBy(order -> order.items().stream().map(Item::name).sorted().toList(),
                    counting()));
    IO.println("разных отсортированных списков: " + bySorted.size());

    // 8. Цена: все со всеми
    List<Set<String>> sets = orders.stream().map(order -> combo(order)).toList();
    long comparisons = 0;
    long equalPairs = 0;
    for (int i = 0; i < sets.size(); i++) {
        for (int j = i + 1; j < sets.size(); j++) {                  // j после i: пара — один раз
            comparisons++;
            if (sets.get(i).equals(sets.get(j))) {
                equalPairs++;
            }
        }
    }
    IO.println("все со всеми: сравнений " + comparisons + ", равных пар " + equalPairs);

    // 9. Цена: одна группировка
    Map<Set<String>, Long> groups = orders.stream()
            .collect(groupingBy(order -> {
                lookups++;                                           // один заказ — один ключ
                return combo(order);
            }, counting()));
    long pairsInGroups = groups.values().stream()
            .mapToLong(count -> count * (count - 1) / 2)             // пары внутри группы
            .sum();
    IO.println("группировка: обращений к карте " + lookups
            + ", равных пар в группах " + pairsInGroups);
}

Сделай руками:

  1. Запусти файл два-три раза. Первая строка может меняться от запуска к запуску — например, [чай, какао] [эклер, капучино] или [какао, чай] [капучино, эклер]; не поменялась — запусти ещё раз. Вторая — всегда какао + чай | капучино + эклер, и все строки ниже от запуска к запуску одинаковые.
  2. В блоке // 4. замени >= 2 на == 3 — останутся комбо из трёх позиций: комбо: 182 и [капучино + матча + сырник — 10, какао + латте + чизкейк — 7, капучино + матча + эклер — 7]. Верни как было.
  3. В блоке // 5. замени new HashSet<>(List.of("латте", "круассан")) на Set.copyOf(List.of("латте", "круассан")) — после первой 36 программа упадёт на key.add("раф") с UnsupportedOperationException. Верни как было.
  4. В блоке // 5. сразу после строки key.add("раф"); добавь key.remove("раф"); — содержимое вернулось, и карта снова находит пару: 36, 36, null, true, {[латте, круассан]=36}. Карта ищет по тому содержимому, какое у ключа в момент поиска. Убери строку.
  5. В первой строке main замени orders(42, 300, 30) на orders(42, 1000, 30) — в двух последних строках будет сравнений 48348861 и обращений к карте 9834, а перед ними — пауза около секунды. С 2000 — сравнений 191443528 и обращений к карте 19568, пауза — несколько секунд. Верни 300.

← Все статьи об алгоритмах

Попробовать руками

В кузницах Hammerhall — задачи по Java, которые проверяет сервер: решаешь в своей IDE, отправляешь одной командой, проверка запускает твои тесты и закрытые. Сложность растёт вместе с решённым, первые задачи бесплатны.

Начать бесплатно Что такое Hammerhall