💡 Красивые алгоритмы медленны при малом n

Красивые алгоритмы с хорошей асимптотикой имеют большие константы. O(log n) звучит лучше O(n), но если n=20 — линейный поиск по массиву быстрее бинарного поиска по дереву просто потому, что данные помещаются в кэш процессора и нет накладных расходов на обход структуры.

Допустим, нужно найти обработчик по типу события. Первый импульс это словарь или дерево:

// "Правильное" решение — O(1) lookup
private readonly Dictionary<string, IHandler> _handlers = new()
{
    ["OrderCreated"] = new OrderCreatedHandler(),
    ["OrderCancelled"] = new OrderCancelledHandler(),
    ["OrderShipped"] = new OrderShippedHandler(),
};

// "Наивное" решение — O(n) linear scan
private readonly (string EventType, IHandler Handler)[] _handlers =
[
    ("OrderCreated", new OrderCreatedHandler()),
    ("OrderCancelled", new OrderCancelledHandler()),
    ("OrderShipped", new OrderShippedHandler()),
];

public IHandler? Find(string eventType)
{
    foreach (var (type, handler) in _handlers)
        if (type == eventType) return handler;
    return null;
}

При 5–20 обработчиках линейный массив часто быстрее словаря: данные лежат последовательно в памяти, нет хеширования, нет разыменования указателей, кэш доволен. Dictionary начинает выигрывать при десятках тысяч элементов и только тогда.

Бенчмарк говорит сам за себя:

[MemoryDiagnoser]
public class LookupBenchmark
{
    private readonly Dictionary<string, int> _dict;
    private readonly (string, int)[] _array;

    public LookupBenchmark()
    {
        var data = Enumerable.Range(0, 10)
            .Select(i => ($"key{i}", i))
            .ToArray();

        _dict = data.ToDictionary(x => x.Item1, x => x.Item2);
        _array = data;
    }

    [Benchmark(Baseline = true)]
    public int DictLookup() => _dict["key7"];

    [Benchmark]
    public int ArrayScan()
    {
        foreach (var (k, v) in _array)
            if (k == "key7") return v;
        return -1;
    }
}

При n=10 массив зачастую быстрее и не аллоцирует ничего лишнего. Измерьте сами.

Когда измерения при реальной нагрузке показывают, что n действительно большой и растёт. Не раньше. Routing-таблица с 15 маршрутами, валидация с 8 правилами, матчинг по 12 паттернам — всё это «малый n», и простой цикл здесь выиграет у любого красивого решения.

📍 Навигация: Вакансии • Задачи • Собесы

🐸 Библиотека шарписта

#il_люминатор