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

Проблем

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

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

var log = LogOf(1000);
var names = new List<string>();
var counts = new List<int>();
long comparisons = 0;
foreach (var item in log)
{
    int i = 0;
    while (i < names.Count)
    {
        comparisons++;
        if (names[i] == item) break;
        i++;
    }
    if (i == names.Count)
    {
        names.Add(item);
        counts.Add(1);
    }
    else
    {
        counts[i]++;
    }
}
Console.WriteLine($"поръчки: {log.Count}");
Console.WriteLine($"продукти: {names.Count}");
Console.WriteLine($"сравнения: {comparisons}");

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

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

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

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

static List<string> LogOf(int n)
{
    int catalog = n / 4 + 1;
    var log = new List<string>();
    for (int i = 0; i < n; i++)
    {
        log.Add($"SKU-{(i * 7919) % catalog}");
    }
    return log;
}

Идеята

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

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

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

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

Виж го

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

List<string> log = [
    "мишка", "слушалки", "мишка", "монитор",
    "клавиатура", "мишка", "слушалки", "монитор",
    "мишка", "слушалки"
];
var counts = new Dictionary<string, int>();
foreach (var item in log)
{
    counts[item] = counts.GetValueOrDefault(item) + 1;
}
var top = counts.OrderByDescending(e => e.Value).Take(3);
foreach (var (item, n) in top)
{
    Console.WriteLine($"{item} {n}");
}

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

var counts = new Dictionary<string, int>();
foreach (var item in log)
{
    counts[item] = counts.GetValueOrDefault(item) + 1;
}
var top = counts.OrderByDescending(e => e.Value).Take(3);
foreach (var (item, n) in top)
{
    Console.WriteLine($"{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.

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

Пробвай

Попълни

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

counts[item] = counts.(item) + 1;

GetValueOrDefault връща стойността или 0 за ключ, който го няма.

Виж го

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

В C# броячът е Dictionary<string, int>. TryGetValue чете без изключение за липсващ ключ. counts[item] = counts.GetValueOrDefault(item) + 1 търси ключа два пъти: веднъж при четене, веднъж при запис. CollectionsMarshal.GetValueRefOrAddDefault дава препратка (ref) към самата стойност в таблицата и я увеличаваш на място, с едно търсене. От .NET 9 LINQ има и готово броене, CountBy, в реда на първото срещане:

List<string> log = [
    "мишка", "слушалки", "мишка", "монитор",
    "клавиатура", "мишка", "слушалки", "монитор",
    "мишка", "слушалки"
];
var counts = new Dictionary<string, int>();
foreach (var item in log)
{
    ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, item, out _);
    slot++;
}
Console.WriteLine($"{counts["мишка"]} {(counts.TryGetValue("таблет", out int t) ? t : 0)}");
foreach (var (item, n) in log.CountBy(x => x))
{
    Console.WriteLine($"{item} {n}");
}

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

Виж го

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

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

var log = LogOf(1000);
var counts = new Dictionary<string, int>();
long updates = 0;
foreach (var item in log)
{
    counts[item] = counts.GetValueOrDefault(item) + 1;
    updates++;
}
Console.WriteLine($"поръчки: {log.Count}");
Console.WriteLine($"продукти: {counts.Count}");
Console.WriteLine($"обновявания на брояча: {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 не пускаме, за да не замръзне страницата.

var counts = new Dictionary<string, int>();
foreach (var item in log)
{
    counts[item] = counts.GetValueOrDefault(item) + 1;
}
var top = counts.OrderByDescending(e => e.Value).Take(3);
foreach (var (item, n) in top)
{
    Console.WriteLine($"{item} {n}");
}

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

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

Ключ от няколко части. Броиш продажби по град и продукт: ключът е двойката. В C# е кортеж (city, item) или record: и двете имат Equals и GetHashCode по полетата.

Идеята

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

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

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

static bool Matches(List<string> kit, List<string> basket)
{
    var need = new Dictionary<string, int>();
    foreach (var item in kit) need[item] = need.GetValueOrDefault(item) + 1;
    foreach (var item in basket) need[item] = need.GetValueOrDefault(item) - 1;
    return need.Values.All(n => n == 0);
}

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

Пробвай

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

List<string> kit = [
    "монитор", "клавиатура", "мишка", "кабел",
    "кабел"
];
List<string> basket1 = [
    "кабел", "мишка", "монитор", "кабел",
    "клавиатура"
];
List<string> basket2 = [
    "монитор", "клавиатура", "мишка", "мишка",
    "кабел"
];
Console.WriteLine($"кошница 1: {(Matches(kit, basket1) ? "пълен комплект" : "не съвпада")}");
Console.WriteLine($"кошница 2: {(Matches(kit, basket2) ? "пълен комплект" : "не съвпада")}");

Отговор

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

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

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

Идеята

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

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

static string? FirstSingle(List<string> customers)
{
    var counts = new Dictionary<string, int>();
    foreach (var c in customers) counts[c] = counts.GetValueOrDefault(c) + 1;
    foreach (var c in customers)
    {
        if (counts[c] == 1) return c;
    }
    return null;
}

List<string> customers = [
    "C-17", "C-4", "C-17", "C-9",
    "C-4", "C-21", "C-9", "C-30"
];
Console.WriteLine($"първият клиент с една поръчка: {FirstSingle(customers)}");

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

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

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

Защо второто минаване е по дневника, а не по речника? Dictionary в днешния .NET обхожда в реда на добавяне, докато нищо не е махнато, но документацията не го обещава. Не разчитай на това.

Идеята

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

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

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

static (int, int)? VoucherPair(int[] prices, int voucher)
{
    var seen = new Dictionary<int, int>();
    for (int i = 0; i < prices.Length; i++)
    {
        if (seen.TryGetValue(voucher - prices[i], out int j)) return (j, i);
        seen[prices[i]] = i;
    }
    return null;
}

int[] prices = { 27, 14, 33, 25, 8, 36, 19 };
var (a, b) = VoucherPair(prices, 50).Value;
Console.WriteLine($"продукти {a} и {b}: {prices[a]} € + {prices[b]} €");

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

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

Пробвай

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

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

int[] prices = { 27, 14, 33, 25, 8, 36, 19 };
var (a, b) = VoucherPair(prices, 50).Value;
Console.WriteLine($"продукти {a} и {b}: {prices[a]} € + {prices[b]} €");

продукти 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)

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

Бисквитки