💲Медианный net доход семьи до 35 лет в США около 287к рублей

Это не байт, а выдержка из статьи про средний доход американских домохозяйств основанный на данных свежего опроса ФРС США (см. рис. 1).

Net worth – это все доходы минус все расходы. К доходам относят зарплату, доход от вкладов и сдачи в аренду имущества и т.д. К расходам – арендную плату, ипотечные платежи, платежи по другим кредитам и другие обязательства.

🇺🇸 Стоимость жилья в США

Интересно также отметить стоимость жилья (см. рис. 2 и 3). Люди, которые приобрели жильё в ипотеку или арендовали квартиру после 2022 года, платят на 25% – 65% больше по сравнению с теми, кто успел сделать это раньше. Ничего не напоминает? :)

🇪🇺🇷🇸 Европа и Сербия в тренде

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

🇷🇺 Россия в тренде

В этом плане, Россия тоже движется в рамках мирового тренда. Спасибо льготной ипотеке, из-за которого жильё стало настолько доступным, что с 2020 года подорожало минимум в 2 раза.

Предыдущий пост тут.

FrozenDictionary в C#: насколько он быстрее Dictionary. Часть 2. Строки.

Продолжаем изучать, что у FrozenDictionary под капотом. Сегодня начнём говорить о словарях с ключом типа string. Для таких словарей предусмотрены аж 12 реализаций FrozenDictionary. Естественно, рассмотрим только принципиальные отличия.

LengthBucketsFrozenDictionary

При создании «замороженных» словарей с ключом типа string, FrozenDictionary в первую очередь попытается создать класс LengthBucketsFrozenDictionary, поэтому начнём именно с него. LengthBucketsFrozenDictionary оптимизирован для ситуаций, когда ключи имеют разную длину. Достигается это распределением ключей по бакетам (корзинам). Алгоритм напоминает блочную сортировку. Для каждой уникальной длины ключа создаётся бакет вместимостью MaxPerLength = 5 элементов.

💡 Чтобы стало понятнее, разберём пример словаря с 6 элементами (рис. 1). В словаре есть ключи длиной 3, 4 и 5 символов. Следовательно, их можно распределить в 3 бакета:

- бакет для ключей длиной 3: fig;
- бакет для ключей длиной 4: lime и kiwi;
- бакет для ключей длиной 5: apple, grape и lemon.

Поскольку известна минимальная (3) и максимальная (5) длина ключей, нет смысла создавать 3 отдельных бакета. Можно всё хранить в одном массиве _lengthBuckets. В таком случае индекс рассчитывается так: (key.Length - minLength) * MaxPerLength.

🔍 Поиск осуществляется в 3 шага (рис. 2):

1. Определяется бакет в массиве _lengthBuckets.
2. Линейным поиском в бакете определяется индекс искомого ключа в _keys.
3. Возвращается значение.

🚫 У LengthBucketsFrozenDictionary есть 2 ограничения:

1. Количество ключей с одинаковой длиной не должно превышать MaxPerLength (принцип Дирихле).
2. Количество пустых бакетов должно быть < 20%. Иначе реализация становится неэффективна с точки зрения использования памяти.

Если одно из этих условий не выполняется, то будет выбрана другая реализация FrozenDictionary. О ней я расскажу в следующей части.

📊 Результаты бенчмарка показывают, что чтение из LengthBucketsFrozenDictionary может быть до 99% быстрее обычного Dictionary. Но если в словаре количество ключей с одинаковой длиной достигает 5, то производительность небольших словарей (до 100 элементов) может быть хуже (рис. 3).

👩‍💻 150 дней LeetCode

Уже больше 150 дней в этом году решаю задачи на LeetCode. На данный момент решено 200 задач, из которых 60% – задачи уровня Medium, 35% – Easy, 5% – Hard.

Сейчас я сосредоточен на улучшении своих слабых сторон, таких как dynamic programming, backtracking, bit manipulation, greedy. Поэтому редко принимаю участие в daily challenge. Вместо этого, решаю задачи из готовых списков, разбитых по темам.

Предыдущий пост тут.

FrozenDictionary в C#: насколько он быстрее Dictionary. Часть 3. Ещё строки.

Сегодня рассмотрим оставшиеся реализации FrozenDictionary с ключом типа string. Напомню, что у LengthBucketsFrozenDictionary есть ограничения: если невозможно распределить ключи по бакетам, будет использоваться одна из 11 реализаций абстрактного класса OrdinalStringFrozenDictionary.

Не стоит пугаться большого количества этих реализаций. Все они основаны на одном и том же принципе – расчёте хэш-кода строки. Отличия заключаются в выборе оптимального алгоритма в зависимости от наличия не-ASCII символов, заданных правил сравнения строк (StringComparison) и наличия в ключах уникальных подстрок. Что это всё значит рассмотрим далее.

💡Выбор оптимальной реализации OrdinalStringFrozenDictionary начинается с анализа ключей классом KeyAnalyzer. Очевидно, что чем длиннее строка, тем медленнее выполняется расчёт хэш-кода. Поэтому KeyAnalyzer пытается найти подстроки наименьшей длины, позволяющие однозначно идентифицировать ключ. Для лучшего понимания рассмотрим пример с фруктами: apple, grape, fig, lime, lemon и kiwi.

Сперва KeyAnalyzer анализирует подстроки длиной в 1 символ при левостороннем выравнивании ключей (рис. 1). В нашем примере есть повторяющиеся подстроки. Например, 0-й символ lime и lemon, 1-й символ fig и lime и 2-й символ в lime и lemon. То есть невозможно при левостороннем выравнивании однозначно идентифицировать ключ по одному символу. Поэтому поиск подстроки продолжается при правостороннем выравнивании. В этом случае при использовании 2-го или 1-го символа с конца подстроки будут уникальны. То есть, зная выравнивание, индекс начала и длину подстроки можно однозначно идентифицировать строку рассчитав хэш-код её подстроки.

Если уникальных подстрок длиной в 1 символ нет, то поиск продолжится для подстрок в 2 символа, 3 символа, вплоть до максимальной длины подстроки. Это значение рассчитывается как минимальное между minLength (минимальная длина ключа) и MaxSubstringLengthLimit = 8. Такое ограничение сделано специально, чтобы не анализировать слишком длинные подстроки, так как их использование не даёт прироста в производительности.

Если уникальных подстрок нет вообще, то расчёт хэш-кода будет производиться для всей строки.

🔍 Поиск в словарях, основанных на OrdinalStringFrozenDictionary, происходит следующим образом:

1. Проверяется, находится ли длина ключа в пределах допустимого диапазона. Это нужно для быстрого определения ключей, которые явно не подходят по длине.
2. Рассчитывается хэш-код подстроки и осуществляется поиск в хэш-таблице.
3. В случае коллизии, осуществляется линейный поиск.

📊 В качестве ключей для бенчмарка я использовал GUID. При инициализации FrozenDictionary, KeyAnalyzer выбрал класс OrdinalStringFrozenDictionary_LeftJustifiedSubstring.

По результатам бенчмарка, FrozenDictionary размером до 75 тыс. элементов быстрее обычного Dictionary. Однако при дальнейшем увеличении размера словаря скорость поиска снижается (рис. 2).

Высокая скорость FrozenDictionary обусловлена быстрым расчётом хэш-кода ключей (рис. 3). Алгоритм FrozenDictionary на 90% – 75% быстрее обычного Dictionary.

Падение производительности в словарях размером 75 тыс. элементов и более вызвано возрастающим количеством коллизий хэша при увеличении размера словаря (рис. 4).

Как видно из графиков, алгоритм, используемый в FrozenDictionary, позволяет ускорить расчёт хэш-кода строки, улучшая производительность до 70%. Но в то же время, такой подход негативно сказывается на производительности поиска в относительно больших словарях.

Со словарями с ключом типа string мы закончили. В FrozenDictionary осталось ещё 2 реализации, которые используются для всех остальных случаев, но в них нет ничего примечательного. Их рассмотрим в заключительном посте в серии про FrozenDictionary. Также, как и обещал, в заключительном посте рассмотрим класс FrozenHashTable – основу большинства «замороженных» словарей.