Как стать автором
Обновить

Комментарии 19

Чисто из спортивного интереса: любопытно, какое место по производительности заняли бы switch-expressions из девятого C#.

Кстати да, их же тоже можно в дерево выстроить. Буду обратно у компа — замерю и напишу.

switch-expressions это сахар для обычного switch и перед компиляцией преобразуется в него

В сишарпе что классический switch, что новый switch expression, что блок последовательных if + return — абсолютно одно и то же. Байт-код генерируется практически идентичный, производительность абсолютно не отличается.

А у Dictionary внутри хеш таблица, или что-то типа дерева?
массивы
Ну не линейный же там поиск по ключу в массиве?

Я почему спросил — меня несколько смущает намеренный автором результат, что набор if быстрее словаря в полтора раза. Набор if — это скорее всего аналог бинарного поиска. В определенных условиях хеш таблица выигрывает у бинарного поиска (и сильно), в каких-то — проигрывает, но как правило не сильно.

Да и вообще, правильно померять быстродействие — дело тонкое, не учесть какой-то фактор — это бывало многократно, у людей с любым уровнем квалификации и опыта.
Конечно там не перебор, но вы ведь спросили что внутри. Внутри два массива. Хэш используется только что бы подсчитать правильный индекс в одном из них.
Сорри, я нечетко сформулировал, конечно имелось в виду, что за поиск там.
правильно померять быстродействие
Это правильное замечание, но в данном случае не зря sixsigma. В данном случае за финальными цифрами стоит и планирование эксперимента показывающее что условия измерения соответствуют реальному использованию, и учет размера кванта измерения, и проверка серией запусков с доказательством n-test что отклонение результатов одного запуска от среднеквадратичного значения меньше статистически значимого.

Выигрыш хэш таблицы дело вполне себе предсказуемое если знать как она устроена внутри.

1) выигрыш по сравнению сложных ключей за счет того что тяжелая операция сравнения заменяется на одноразовое вычисление хеш и серию легких сравнений хеш-значения и вызов тяжелого сравнения значений уже только на небольшую корзину (как правило размер выбирается такой, где линейный поиск оказывается не дольше двоичного дерева, до 6-8 элементов в bucket.

2) Ну и поиск в значительных объемах данных — после N > 10000 никаким сокращением одного O преодолеть разницу между 1 условной операцией и пусть логарифмическим, но ростом в другой — нельзя.

Но статья не про структуры данных, а про то что возможность динамического создания кода открывает возможность воспользоваться динамической модификацией, реализовав выигрыш, который возникает от набора данных, а не заложен изначально в алгоритм. В данном случае, как я и написал в начале — задача просто оказалась возможностью показать на простом примере, обычно кейсы применения Linq генерации кода куда запутаннее, там только на несколько страниц контекст объяснять пришлось бы.
>Это правильное замечание, но в данном случае не зря sixsigma.
Я в общем и не имел в виду, что вы что-то неверно померяли. Просто этот процесс измерения не был тут достаточно подробно описан, а допустить в нем ошибку — ну это вполне типично. Хотя бы — описать данные, на которых меряли, много ли их было или мало.

А сам процесс генерации кода из Expression — он без сомнения интересный (хотя такие статьи тут уже и были), и тема в целом неисчерпаемая.
Так вроде первом абзаце, прошу прощения что не акцентировал на этом внимание. 300 значений в таблице, значения вида
range (double, double)->drag. Поиск drag по попаданию значения ключа внутрь range.
Ну т.е. таблица — 300 строк?
Да.
Хеш-таблица, просто они для небольшого ускорения перераспределения по buckets используют не массив массивов как в книжке, а массив entries и массив указателей на позиции buckets.

Исходный код можно посмотреть тут
github.com/microsoft/referencesource/blob/master/mscorlib/system/collections/generic/dictionary.cs

Ваш вопрос в другом комментарии по поводу сравнения хэш-таблицы с двоичным деревом правильный. Но чтобы понять логику надо учесть один момент — у словаря поиск O(1), у дерева O(log2). Это все помнят и знают, но вот что O говорит только о количестве неких попугаев в которых мериться операция, а не о длительность в выраженной в единицах времени — забывают.

Собственно на размышления как раз и наводят цифры что по O соотношение количество операций 1 к log2(300) примерно 8, а реальное исполнение всего в 4. Именно более тяжелое O словаря и возможность ускорить O двоичного дерева за счет исключения обращения к памяти и открывают окно возможности для оптимизации здесь.

Я правильно понял, что заменили поиск по хэш-таблице с линейной памятью (300 элементов) и константным количеством случайного доступа на код линейного объёма (хотя бы 300 ифов) и логарифмическим количеством операций, но как бы без доступа к памяти? И при этом стало сильно быстрее?


Если да, то это немного удивительно. Возможно, конечно, лучше работает условный branch prediction или кэш для кода больше, чем для данных, или просто так данные уложились компактнее, чем в хэш-таблице.

Я бы не сказал что «сильно», всего в 1.5 раза. Что сравнимо со словарем мы получили структуру легко реализуемую на микроконтроллере.

А чем удивительно? Обращение к памяти всегда стоило дорого, по сравнению с теми же самыми операциями, но с аргументами в виде константы с команде. Посмотрите первые две строки в таблице, которые натолкнули меня на мысль — там тоже сравнение совершенно аналогичное, только сравнивается линейный поиск в массиве с линейной же цепочкой if.
к сожалению, “отладчиком в IDE” по такому коду не походишь

Это не совсем так. Если добавить код для сохранения отладочной информации, то становится возможной пошаговая отладка в псевдокоде. Пример кода. Конечно, вручную привязывать выражения к номерам строк — сомнительное удовольствие, но это вполне поддаётся автоматизации. Не так давно появилась библиотека ExpressionDebugger, позволяющая добавить отладку одной строкой кода.

О, спасибо!
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.