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

Пары «все со всеми»: почему n² не взлетает

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

Для кого. Ты прочитал «Стримы по шагам» или знаешь то же сам: flatMap, IntStream.range и boxed, компараторы и min, счётчик-поле из статьи 9 «Стримов». Из этого цикла пригодятся статьи 1 и 2: множества и группировка по ключу.

Что будет. Как перебрать все пары без повторов и почему их n·(n−1)/2; почему вдвое больше гостей — вчетверо больше работы; как найти двух гостей с самыми близкими тратами перебором и как сортировкой: на месяце она дешевле в 18 раз, на 8000 гостях — в 309; что делать с ничьей и с переполнением int; что спросить себя, прежде чем перебирать пары.

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

Зачем считать пары#

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

Первое решение приходит сразу: сравнить каждого гостя с каждым и запомнить пару с самой маленькой разницей. Это перебор пар «все со всеми»: несколько строк, ответ верный, на 294 гостях — миллисекунды. Но пар становится больше гораздо быстрее, чем гостей: на 8000 гостях их уже тридцать миллионов.

Часть 1. Все пары без повторов

Траты гостя#

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

/** Траты гостя за месяц: номер карты и сумма всех его заказов в рублях. */
record Spending(int guest, int sum) {}

/** Траты каждого гостя, у которого были заказы, — по возрастанию номера карты. */
List<Spending> spending(List<Order> orders) {
    return orders.stream()
            .collect(groupingBy(Order::guest, TreeMap::new, summingInt(Order::total)))
            .entrySet().stream()
            .map(entry -> new Spending(entry.getKey(), entry.getValue()))
            .toList();
}

Сумма в группе — summingInt из статьи 6 «Стримов» (коллекторы — через import static, как там), стрим по entrySet — из статьи 7 «Стримов», TreeMap выстраивает гостей по номеру карты. Ответ — список: гостей будем брать по месту.

Четыре гостя — шесть пар#

Первые четыре гостя — список four, это spending.stream().limit(4).toList():

[Spending[guest=1, sum=5240], Spending[guest=2, sum=2480], Spending[guest=3, sum=320], Spending[guest=4, sum=5160]]

Сколько у них пар? Гость 1 встаёт в пару с каждым из трёх остальных: 1–2, 1–3, 1–4. Гость 2 — с гостями 3 и 4: пара 1–2 уже есть. Гость 3 — только с гостем 4. Гостю 4 новых пар не осталось. Всего 3 + 2 + 1 = 6.

То же формулой. Каждый из n гостей встаёт в пару с n − 1 остальными: 4 · 3 = 12. Но так каждая пара посчитана дважды — «1–2» и «2–1» одна и та же пара, — значит, делим пополам. Пар без повторов — n·(n−1)/2: 4 · 3 / 2 = 6.

Пары стримом#

Код повторяет счёт руками:

/** Все пары без повторов: гость i — с каждым, кто стоит в списке после него. */
Stream<Pair> allPairs(List<Spending> spending) {
    int n = spending.size();
    return IntStream.range(0, n).boxed()
            .flatMap(i -> IntStream.range(i + 1, n)
                    .mapToObj(j -> pair(spending.get(i), spending.get(j))));
}

IntStream.range(0, n) — места 0, 1, …, n − 1, как цикл for (int i = 0; i < n; i++) (статья 8 «Стримов»). Для каждого i внутренний range(i + 1, n) даёт места после него, mapToObj превращает пару мест в пару гостей, а flatMap из статьи 4 «Стримов» сливает всё в один стрим. boxed() — ради flatMap: у IntStream он разворачивает только в числа, а нам нужны пары.

Всё решает начало внутреннего диапазона — i + 1. Места до i уже были: пара 2–1 — та же, что 1–2. А место i — сам гость. Начни с 0 — и получишь n² пар вместо n·(n−1)/2: каждую дважды и ещё n пар «гость сам с собой».

Пара и одно сравнение:

/** Пара гостей: номера карт, меньший — первым, и разница их трат в рублях. */
record Pair(int first, int second, int diff) {}

long comparisons = 0;   // сколько раз сравнили двух гостей — только чтобы увидеть работу

/** Сравнить двух гостей: пара с разницей их трат. Каждый вызов — одно сравнение. */
Pair pair(Spending a, Spending b) {
    comparisons++;
    return new Pair(Math.min(a.guest(), b.guest()), Math.max(a.guest(), b.guest()),
            Math.abs(a.sum() - b.sum()));
}

Math.abs — разница без знака: и 5240 − 5160, и 5160 − 5240 дают 80. Меньший номер карты — первым: тогда «124 и 2» и «2 и 124» — одна и та же запись, и equals записи их не различит. Счётчик — поле, как в статье 9 «Стримов»: каждый вызов pair — одно сравнение двух гостей. Сравнениями и будем мерить работу: их число одинаково на любом компьютере.

allPairs(four).forEach(IO::println);
Pair[first=1, second=2, diff=2760]
Pair[first=1, second=3, diff=4920]
Pair[first=1, second=4, diff=80]
Pair[first=2, second=3, diff=2160]
Pair[first=2, second=4, diff=2680]
Pair[first=3, second=4, diff=4840]

Шесть пар, как руками. Ближе всех из четверых — гости 1 и 4: 5240 и 5160 ₽, разница 80.

Часть 2. Сколько это стоит#

Пары месяца#

IO.println("гостей с заказами: " + spending.size() + ", пар: " + allPairs(spending).count());
гостей с заказами: 294, пар: 43071

По формуле: 294 · 293 / 2 = 43 071. Прогон сошёлся с ней до единицы.

Вдвое больше гостей — вчетверо больше пар

Генератор умеет любой размер: orders(42, n, 30) — месяц для n гостей. Посчитаем пары для n от 300 до 8000 и засечём время:

for (int n : List.of(300, 1000, 2000, 4000, 8000)) {
    List<Spending> many = spending(orders(42, n, 30));
    long start = System.nanoTime();                      // показание часов до подсчёта
    long pairs = allPairs(many).count();
    long ms = (System.nanoTime() - start) / 1_000_000;   // прошло: наносекунды → миллисекунды
    IO.println("гостей " + many.size() + ": пар " + pairs + ", " + ms + " мс");
}
гостей 294: пар 43071, 5 мс
гостей 982: пар 481671, 12 мс
гостей 1950: пар 1900275, 45 мс
гостей 3916: пар 7665570, 196 мс
гостей 7821: пар 30580110, 493 мс

Гостей с заказами чуть меньше n: кто-то за месяц не зашёл ни разу. От 294 к 982 гостей стало в 3,3 раза больше, а пар — в 11 раз: 3,3 · 3,3 ≈ 11. Дальше гостей каждый раз вдвое больше, а пар — вчетверо. Почему: n·(n−1)/2 — почти n²/2, при большом n единица ничего не меняет. Удвой n — квадрат вырастет в 2 · 2 = 4 раза. Это O(n²), квадратичный рост, — та же O(n·m) из статьи 9 «Стримов», только обе коллекции здесь — одни и те же гости.

🔑 Перебор пар растёт как квадрат: вдвое больше данных — вчетверо больше работы, в десять раз больше — в сто.

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

Миллион гостей — полтриллиона пар: при миллионе сравнений в секунду это пять дней, десять миллионов — больше года (прикидка курса CS246).

Квадрат «не взлетает» не потому, что компьютер медленный: на каждое удвоение данных ему нужен вчетверо более быстрый компьютер.

⚠️ Где кончается int#

Числа нашего прогона помещаются в int с большим запасом: 30 580 110 пар против предела 2 147 483 647 из статьи 8 «Стримов». Но формула числа пар в int ломается раньше, чем кажется:

int guests = 50_000;
IO.println("int:  " + guests * (guests - 1) / 2);
IO.println("long: " + (long) guests * (guests - 1) / 2);
int:  -897508648
long: 1249975000

Пар 1 249 975 000 — такое число в int помещается. Сломался промежуточный шаг: Java сначала умножает — выходит 2 499 950 000, больше предела, — и только потом делит. Умножение переполнилось молча, как выручка сети в статье 8 «Стримов».

Лекарство — тот же long. Приведение (long) guests выполняется раньше умножения, а по спецификации Java, если у целой операции хотя бы одно число long, считают в 64 битах.

Формула в int врёт уже с 46 342 гостей, а с 65 537 не влезает и само число пар — поэтому счётчик comparisons объявлен long, и count() стрима отвечает long.

Часть 3. Ближе всего: перебор и сортировка

Перебором#

Вопрос хозяйки перебором — одна строка: из всех пар взять ту, у которой разница меньше всех.

/** Самые близкие траты перебором всех пар. */
Pair closestByAllPairs(List<Spending> spending, Comparator<Pair> closer) {
    return allPairs(spending).min(closer).orElseThrow();
}

min с компаратором — из статьи 3 «Стримов», orElseThrow — из статьи 2 «Стримов»: у одного гостя пар нет. Какую пару считать ближе, решает компаратор; он приходит параметром — ещё поменяется. Пока — просто по разнице:

Comparator<Pair> byDiff = Comparator.comparingInt(Pair::diff);
comparisons = 0;
IO.println("перебор:    " + closestByAllPairs(spending, byDiff) + ", сравнений: " + comparisons);
перебор:    Pair[first=2, second=124, diff=0], сравнений: 43071

Разница — ноль: гости 2 и 124 потратили за месяц поровну, по 2480 ₽. Работа — 43 071 сравнение, по одному на пару.

Сортировкой#

Разложи траты на числовой прямой по возрастанию. Самая близкая пара всегда найдётся среди соседей: если между a и c стоит b, то b к a не дальше, чем c. Значит, хватит отсортировать траты и сравнить каждого гостя только с соседом справа: n − 1 сравнение вместо n·(n−1)/2.

Руками на четырёх гостях. По возрастанию: 320 (гость 3), 2480 (гость 2), 5160 (гость 4), 5240 (гость 1). Соседи: 3 и 2 — разница 2160, 2 и 4 — 2680, 4 и 1 — 80. Три сравнения вместо шести, ответ тот же: гости 1 и 4.

/** Порядок для сортировки: по тратам, при равных тратах — по номеру карты. */
static final Comparator<Spending> BY_SUM = Comparator.comparingInt(Spending::sum)
        .thenComparingInt(Spending::guest);

/** Самые близкие траты сортировкой: отсортировать и сравнить только соседей. */
Pair closestBySorting(List<Spending> spending, Comparator<Pair> closer) {
    List<Spending> sorted = spending.stream()
            .sorted((a, b) -> {
                comparisons++;                       // сравнения сортировки — тоже работа
                return BY_SUM.compare(a, b);
            })
            .toList();
    return IntStream.range(0, sorted.size() - 1)
            .mapToObj(i -> pair(sorted.get(i), sorted.get(i + 1)))   // каждый — с соседом справа
            .min(closer)
            .orElseThrow();
}

BY_SUM — компаратор-константа файла, как MENU (thenComparingInt — из статьи 3 «Стримов»; зачем второй ключ, станет ясно ниже). Сортировка тоже сравнивает гостей, поэтому компаратор обёрнут в лямбду со счётчиком.

comparisons = 0;
IO.println("сортировка: " + closestBySorting(spending, byDiff) + ", сравнений: " + comparisons);
сортировка: Pair[first=7, second=42, diff=0], сравнений: 2351

2351 сравнение вместо 43 071 — в 18 раз меньше. Из них 293 — соседи, остальные 2058 — сортировка.

Сколько стоит сортировка? Объекты JDK сортирует слиянием — так описывает свою реализацию примечание к List.sort (описание, не обещание): на перемешанных данных это порядка n·log₂ n сравнений. Откуда: список делят пополам, пока не останутся одиночки, — это log₂ n уровней, и на каждом уровне слияние делает не больше n сравнений. Для 294 гостей log₂ n ≈ 8,2, 294 · 8,2 ≈ 2400 — сортировке хватило 2058, ровно столько же, сколько List.sort на тех же данных. Удвой n — добавится один уровень, и сортировка подорожает чуть больше чем вдвое, а не вчетверо.

Только ответ другой.

Ответы разные: ничья#

Перебор назвал гостей 2 и 124, сортировка — 7 и 42. Ошибки нет: гости 7 и 42 тоже потратили поровну, по 400 ₽. Пар с нулевой разницей несколько, и каждая — честный ответ. Это ничья.

Какую из равных пар вернёт min, документация не говорит. На JDK 25 — первую встреченную. Перебор идёт по номерам карт, и первой ему попадается пара 2–124. Сортировка идёт по возрастанию трат, и первыми ей попадаются траты по 400 ₽.

⚠️ Беда не в коде, а в вопросе: он не говорит, что делать при ничьей. Пока это не сказано, ответ зависит от способа. Замени перебор сортировкой — и десерт достанется другим гостям, а тест, который ждал «2 и 124», покраснеет, хотя оба способа верны.

Правило ничьей — часть вопроса. Решим так: при равной разнице выигрывает пара с меньшим номером карты первого гостя, при равном первом — второго. Номер карты у гостя один и не меняется, значит, и ответ один. Годится и другое правило, лишь бы одно на оба способа. В коде это запасные ключи компаратора, как в статье 7 «Стримов»:

/** Правило ничьей: меньше разница; при равной — меньше номер первого гостя, потом второго. */
static final Comparator<Pair> CLOSER = Comparator.comparingInt(Pair::diff)
        .thenComparingInt(Pair::first)
        .thenComparingInt(Pair::second);
IO.println("перебор:    " + closestByAllPairs(spending, CLOSER));
IO.println("сортировка: " + closestBySorting(spending, CLOSER));
перебор:    Pair[first=2, second=124, diff=0]
сортировка: Pair[first=2, second=124, diff=0]

💡 Почему соседи не теряют этот ответ? Равные траты стоят подряд, а внутри них — по номеру карты: для этого у BY_SUM второй ключ. Значит, два меньших номера среди равных — соседи. А без равных трат любая ближайшая пара — соседи: стой между ними третий, он был бы ближе.

На росте#

Блок // 7. — тот же цикл, что в части 2, только на каждом месяце работают оба способа с правилом ничьей, а их ответы сравниваются через equals:

гостей 294: перебор 43071, сортировка 2351, ответы совпали
гостей 982: перебор 481671, сортировка 9474, ответы совпали
гостей 1950: перебор 1900275, сортировка 20731, ответы совпали
гостей 3916: перебор 7665570, сортировка 45597, ответы совпали
гостей 7821: перебор 30580110, сортировка 98853, ответы совпали

Ответы совпали на всех размерах. На каждом удвоении перебор растёт вчетверо, сортировка — в 2,2 раза. Разрыв растёт вместе с данными: сортировка дешевле в 18 раз на 294 гостях и в 309 раз — на 7821.

Часть 4. Прежде чем перебирать пары — спроси, нельзя ли без них

Сортировка ответила на вопрос «кто ближе» без перебора пар. Это не частный трюк, а привычка: прежде чем писать вложенный range(i + 1, n), спроси, что именно ты сравниваешь.

Равенство — множество и ключ#

Хозяйка спрашивает проще: есть ли вообще два гостя с одинаковыми тратами? Пары для этого не нужны:

Set<Integer> sums = new HashSet<>(spending.stream().map(Spending::sum).toList());
IO.println("гостей: " + spending.size() + ", разных сумм: " + sums.size());
гостей: 294, разных сумм: 258

HashSet не хранит повторов: разных сумм меньше, чем гостей, — значит, у кого-то суммы совпали. Работа — 294 добавления, каждое в среднем за постоянное время, сколько бы элементов уже ни лежало в множестве (документация HashSet; цена множеств — в статье 1). Перебор ответил бы тем же anyMatch по парам: повезёт — наткнётся на совпадение рано, а если совпадений нет — пройдёт все 43 071 пару, чтобы сказать «нет».

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

Близость числа — сортировка#

«У кого почти одинаково» — сортировка и соседи, как в части 3.

Общее — обратный индекс#

«У кого есть общие позиции» — тоже не повод сравнивать всех со всеми. Карта «позиция → гости, которые её брали» строится за один проход, и сравнивать можно только гостей из одного её списка — если списки короткие. Такая карта — обратный индекс, о нём статья 4.

Когда пары всё-таки нужны#

Пары «все со всеми» остаются, когда сравнение не сводится ни к ключу, ни к порядку, ни к общему элементу. Тогда перебор — честный выбор, если заранее прикинуть n·(n−1)/2 и на данных в десять раз больше.

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

🔑 Перед парами — вопрос «что я сравниваю?». Равенство — группируй. Близость числа — сортируй. Общее — обратный индекс, если списки короткие. Не подошло ни одно — перебирай, но сначала посчитай пары.

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

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

  1. Сколько пар у пяти гостей? Посчитай руками и по формуле. Откуда в формуле деление на 2?
  2. Зачем внутренний диапазон начинается с i + 1? Что будет, если начать его с 0?
  3. Гостей стало вдвое больше. Во сколько раз больше станет пар и почему?
  4. Почему главная мера работы — число сравнений, а миллисекунды — только иллюстрация?
  5. Почему n * (n - 1) / 2 в int ошибается на 50 000 гостях, хотя ответ в int помещается? Как это починить?
  6. Почему после сортировки достаточно сравнить только соседей? Входит ли сама сортировка в работу?
  7. Перебор и сортировка назвали разные пары. Кто ошибся? Что добавить к вопросу, чтобы ответ был один?
  8. Что спросить себя, прежде чем перебирать пары? Какой приём подходит, если сравниваешь на равенство, на близость числа, на общее?

Что дальше#

Статья 4 — пары внутри записи и обратный индекс: как найти тех, кто брал и латте, и эклер, не обходя всех гостей, и сколько пар остаётся сравнить.

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

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

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

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

java Coffee.java

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

Файл работает несколько секунд: в блоках // 3. и // 7. перебираются десятки миллионов пар.

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

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;
import java.util.stream.IntStream;
import java.util.stream.Stream;

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

/** Траты гостя за месяц: номер карты и сумма всех его заказов в рублях. */
record Spending(int guest, int sum) {}

/** Траты каждого гостя, у которого были заказы, — по возрастанию номера карты. */
List<Spending> spending(List<Order> orders) {
    return orders.stream()
            .collect(groupingBy(Order::guest, TreeMap::new, summingInt(Order::total)))
            .entrySet().stream()
            .map(entry -> new Spending(entry.getKey(), entry.getValue()))
            .toList();
}

/** Пара гостей: номера карт, меньший — первым, и разница их трат в рублях. */
record Pair(int first, int second, int diff) {}

long comparisons = 0;   // сколько раз сравнили двух гостей — только чтобы увидеть работу

/** Сравнить двух гостей: пара с разницей их трат. Каждый вызов — одно сравнение. */
Pair pair(Spending a, Spending b) {
    comparisons++;
    return new Pair(Math.min(a.guest(), b.guest()), Math.max(a.guest(), b.guest()),
            Math.abs(a.sum() - b.sum()));
}

/** Все пары без повторов: гость i — с каждым, кто стоит в списке после него. */
Stream<Pair> allPairs(List<Spending> spending) {
    int n = spending.size();
    return IntStream.range(0, n).boxed()
            .flatMap(i -> IntStream.range(i + 1, n)
                    .mapToObj(j -> pair(spending.get(i), spending.get(j))));
}

/** Самые близкие траты перебором всех пар. */
Pair closestByAllPairs(List<Spending> spending, Comparator<Pair> closer) {
    return allPairs(spending).min(closer).orElseThrow();
}

/** Порядок для сортировки: по тратам, при равных тратах — по номеру карты. */
static final Comparator<Spending> BY_SUM = Comparator.comparingInt(Spending::sum)
        .thenComparingInt(Spending::guest);

/** Самые близкие траты сортировкой: отсортировать и сравнить только соседей. */
Pair closestBySorting(List<Spending> spending, Comparator<Pair> closer) {
    List<Spending> sorted = spending.stream()
            .sorted((a, b) -> {
                comparisons++;                       // сравнения сортировки — тоже работа
                return BY_SUM.compare(a, b);
            })
            .toList();
    return IntStream.range(0, sorted.size() - 1)
            .mapToObj(i -> pair(sorted.get(i), sorted.get(i + 1)))   // каждый — с соседом справа
            .min(closer)
            .orElseThrow();
}

/** Правило ничьей: меньше разница; при равной — меньше номер первого гостя, потом второго. */
static final Comparator<Pair> CLOSER = Comparator.comparingInt(Pair::diff)
        .thenComparingInt(Pair::first)
        .thenComparingInt(Pair::second);

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

    // 1. Четыре гостя — шесть пар
    List<Spending> four = spending.stream().limit(4).toList();
    IO.println(four);
    allPairs(four).forEach(IO::println);

    // 2. Все пары месяца
    IO.println("гостей с заказами: " + spending.size() + ", пар: " + allPairs(spending).count());

    // 3. Рост: вдвое больше гостей — вчетверо больше пар
    for (int n : List.of(300, 1000, 2000, 4000, 8000)) {
        List<Spending> many = spending(orders(42, n, 30));
        long start = System.nanoTime();                      // показание часов до подсчёта
        long pairs = allPairs(many).count();
        long ms = (System.nanoTime() - start) / 1_000_000;   // прошло: наносекунды → миллисекунды
        IO.println("гостей " + many.size() + ": пар " + pairs + ", " + ms + " мс");
    }

    // 4. Самые близкие траты перебором: ближе — меньше разница
    Comparator<Pair> byDiff = Comparator.comparingInt(Pair::diff);
    comparisons = 0;
    IO.println("перебор:    " + closestByAllPairs(spending, byDiff) + ", сравнений: " + comparisons);

    // 5. То же сортировкой
    comparisons = 0;
    IO.println("сортировка: " + closestBySorting(spending, byDiff) + ", сравнений: " + comparisons);

    // 6. С правилом ничьей ответы совпадают
    IO.println("перебор:    " + closestByAllPairs(spending, CLOSER));
    IO.println("сортировка: " + closestBySorting(spending, CLOSER));

    // 7. Перебор против сортировки на росте
    for (int n : List.of(300, 1000, 2000, 4000, 8000)) {
        List<Spending> many = spending(orders(42, n, 30));
        comparisons = 0;
        Pair byPairs = closestByAllPairs(many, CLOSER);
        long pairsWork = comparisons;
        comparisons = 0;
        Pair bySort = closestBySorting(many, CLOSER);
        IO.println("гостей " + many.size() + ": перебор " + pairsWork + ", сортировка " + comparisons
                + (byPairs.equals(bySort) ? ", ответы совпали" : ", ответы разные"));
    }

    // 8. Число пар по формуле: в int умножение переполняется раньше деления
    int guests = 50_000;
    IO.println("int:  " + guests * (guests - 1) / 2);
    IO.println("long: " + (long) guests * (guests - 1) / 2);

    // 9. Есть ли вообще одинаковые траты? Пары не нужны — хватит множества
    Set<Integer> sums = new HashSet<>(spending.stream().map(Spending::sum).toList());
    IO.println("гостей: " + spending.size() + ", разных сумм: " + sums.size());
}

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

  1. Запусти файл. Первые строки — четыре гостя и шесть их пар; дальше гостей с заказами: 294, пар: 43071, рост пар, ответы перебора и сортировки — сначала разные, с правилом ничьей одинаковые — и в конце гостей: 294, разных сумм: 258. Миллисекунды у тебя будут свои, остальное — до символа то же.
  2. В блоке // 1. замени limit(4) на limit(8) — пар станет 28: 8 · 7 / 2. Верни как было.
  3. В allPairs замени IntStream.range(i + 1, n) на IntStream.range(0, n). У четырёх гостей выйдет 16 пар, первая — Pair[first=1, second=1, diff=0]: гость в паре с самим собой. Пар месяца станет 86436 — это 294². Перебор объявит ближайшей парой гостя и его самого, а на росте все строки скажут ответы разные. Верни i + 1.
  4. В блоке // 3. добавь в список 16000 — появится строка гостей 15660: пар 122609970: снова вчетверо больше, чем строкой выше. Время вырастет тоже, с поправкой на шум. Верни как было.
  5. В блоке // 8. поставь guests = 46_341 — обе строки покажут 1073720970. Теперь 46_342: строка int станет отрицательной, -1073716337, а long покажет 1073767311. Верни 50_000.

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

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

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

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