yet another dev

😀 Качаем бинарный поиск

Составил список из 15 задач на LeetCode, решив которые вы постигните дзен в понимании бинарного поиска.

Полезно также прочитать вот это обсуждение. Там вы найдёте:
- объяснение, как определить, что в задаче необходим бинарный поиск;
- как правильно вычислять среднее значение, чтобы избежать переполнения при арифметических операциях.
- примеры решений.

Советую решать задачи в следующем порядке:

🟠 Koko Eating Bananas
🟠 Maximum Candies Allocated to K Children
🟠 Minimum Number of Days to Make m Bouquets
🟠 Capacity To Ship Packages Within D Days
🟠 Minimum Speed to Arrive on Time
🟠 Minimum Limit of Balls in a Bag
🟠 Minimum Time to Repair Cars
🟠 Find the Smallest Divisor Given a Threshold
🟠 Minimized Maximum of Products Distributed to Any Store
🟠 Minimum Time to Complete Trips
🟠 Maximum Tastiness of Candy Basket
🟠 Magnetic Force Between Two Balls
🟠 Sell Diminishing-Valued Colored Balls
🔴 Split Array Largest Sum
🔴 Maximum Running Time of N Computers

🟠 – medium, 🔴 – hard.

– Бобрята, а что это у вас?
– Плотина…
– логи

Год назад я рассказывал о налогах, которые платит работник в России и Сербии. Время обновить информацию, так как с 2025 года айтишникам-мажорам в России придётся платить больше налогов из-за прогрессивной шкалы НДФЛ (рис. 1). Сравним зарплаты условных айтишников трёх уровней:

1. 150 тыс. ₽/мес или 1,8 млн ₽/год.
2. 300 тыс. ₽/мес или 3,6 млн ₽/год.
3. 450 тыс. ₽/мес или 5,4 млн ₽/год.

Ставки 20% и 22% не рассматриваются, так как среднестатистический айтишник не зарабатывает больше 20 млн ₽ в год.

Налог на годовой доход

Сперва работа над ошибками. В прошлый раз забыл рассказать о налоге на годовой доход (рис. 2). В Сербии этим налогом облагается доход, превышающий 3 средние годовые зарплаты. В прошлом году средняя годовая зарплата составляла 1 423 188 динаров или примерно 12 112 €. Следовательно, с доходов свыше 36 337 € нужно было уплатить дополнительный налог.

Особенности этого налога:

1. Если вы моложе 40 лет, планка необлагаемого дохода повышается ещё на 3 средние годовые зарплаты.

2. За каждого несовершеннолетнего члена семьи можно получить 15% вычет, но не более 50% суммарно.

Пока ты молод и с доходом выше среднего, то государство не будет дополнительно обременять налогами – зарабатывай. Но к 40 годам будь добр заведи детей. Тогда налогов будешь платить меньше. Видимо тут такая логика? 🤷

Сравнение NET дохода в России и Сербии

Вернёмся к нашим айтишникам. Повторяться с расчётами не будем, а воспользуемся калькуляторами для расчётов налогов в Сербии и РФ. Подробная математика есть в предыдущем посте. Результаты расчётов на рис. 3.

Разработчику в Сербии с зарплатой эквивалентной 450 тыс. ₽/мес также пришлось бы уплатить налог на годовой доход, при условии, что ему минимум 40 лет. При средней ежемесячной зарплате за 1 квартал 2024 года (131 893 динар), 3 средние годовые зарплаты составят 4 748 148 динар или 40 410 €. Значит, ему придётся заплатить ещё почти 1 700 € налогов.

Таким образом, с точки зрения налогов, быть работником в России всё ещё выгоднее – налоги одни из самых низких.

readonly, readonly everywhere

Сегодня с коллегой зашёл разговор про ключевое слово readonly. После разговора, решил вспомнить в C# всё, что содержит в себе readonly и написал такого монстра:

public readonly struct SomeStruct(int val)
{
  public string SomeField { get; init; } 
    = "Hello, World!";
  public readonly int SomeProperty = val;
  public readonly IReadOnlyCollection<int> SomeCollection = [];
  public readonly ReadOnlySpan<char> SomeMethod() => SomeField;
}

Этот код компилируется и работает. Естественно, в C# ещё много чего с readonly, но, наверно, и этого достаточно, чтобы запутать C# разработчика.

Кстати, сможете объяснить что значит readonly в каждом из случаев?

Начало тут 👆

SmallValueTypeComparableFrozenDictionary и SmallValueTypeDefaultComparerFrozenDictionary

Строго говоря, два этих класса и не хэш-таблицы вовсе. Поиск значения в них осуществляется не через FrozenHashTable, а простым сравнением элементов в цикле for. Поэтому эти реализации используются, когда в исходном словаре не более 10 элементов.

При этом, SmallValueTypeComparableFrozenDictionary применяется, если тип ключа – это встроенный примитивный значимый тип: int, long, double, enum и т.д. Если же тип ключа, к примеру, record struct, то будет использован тип SmallValueTypeDefaultComparerFrozenDictionary.

Такое разделение разработчики .NET объясняют тем, что у встроенных типов 100% реализован интерфейс IComparable и поэтому можно немного оптимизировать поиск, отсортировав массивы ключей и значений при инициализации словаря:

// ctor
_keys = source.Keys.ToArray();
_values = source.Values.ToArray();

Array.Sort(_keys, _values);
_max = _keys[_keys.Length - 1];

К примеру, если бы нам нужно было найти значение для ключа 10 в словаре как на рисунке 3, то без сортировки пришлось бы обойти весь массив _keys и убедиться, что такого значения в словаре нет. При наличии сортировки достаточно же сравнить с максимальным значением. В данном случае – 9.

Кроме того, поскольку массив ключей _keys отсортирован, можно осуществлять поиск пока искомое значение ключа больше текущего значения _keys[i].

// GetValueRefOrNullRefCore method
if (Comparer<TKey>.Default
  .Compare(key, _max) <= 0)
{
  TKey[] keys = _keys;
  for (int i = 0; i < keys.Length; i++)
  {
    int c = Comparer<TKey>
        .Default.Compare(key, keys[i]);
    if (c <= 0)
    {
      if (c == 0)
      {
        return ref _values[i];
      }
      break;
    }
  }
}
return ref Unsafe.NullRef<TValue>();

Реализация SmallValueTypeDefaultComparerFrozenDictionary похожа на предыдущую, с тем лишь отличием, что в ней не используется сортировка. Соответственно, линейный поиск по массиву ключей _keys будет осуществлён всегда.

Несмотря на все оптимизации в этих двух классах, результаты бенчмарка не выглядят впечатляющими (рис. 4). Даже то небольшое ускорение, которое может дать SmallValueTypeDefaultComparerFrozenDictionary – это всего лишь несколько наносекунд.

На сегодня всё. Код и результаты бенчмарка лежит тут. В следующей части рассмотрим ссылочные типы. Самое интересное там связано со ключами типа string.

FrozenDictionary в C#: насколько он быстрее Dictionary. Часть 1. Значимые типы.

С релизом .NET 8 в арсенале C# разработчиков появился новый тип коллекций – FrozenDictionary. В серии статей рассмотрим, что представляет собой этот словарь и насколько он быстрее.

FrozenDictionary<TKey, TValue> – это абстрактный класс. У этого класса есть множество реализаций, зависящих от типа ключа, размера коллекции, компаратора. Создаются они при помощи extension-метода ToFrozenDictionary. Стратегия выбора подходящей реализации реализована в статическом классе FrozenDictionary, а именно в методе CreateFromDictionary.

В этой части рассмотрим реализации с ключом значимого типа и с компаратором по умолчанию. Для таких словарей предусмотрены 4 реализации FrozenDictionary:

1. Int32FrozenDictionary.
2. ValueTypeDefaultComparerFrozenDictionary.
3. SmallValueTypeComparableFrozenDictionary.
4. SmallValueTypeDefaultComparerFrozenDictionary.

Int32FrozenDictionary

Для словарей, с количеством элементов больше 10 и ключом типа Int32 используется класс Int32FrozenDictionary. Эта, как и большинство других реализаций FrozenDictionary, основаны на структуре FrozenHashTable. Это основа «замороженных» словарей. Подробнее о ней я расскажу в последней статье о FrozenDictionary. Пока же достаточно знать, что эта структура содержит в себе множество оптимизаций, которые позволяют быстро производить чтение.

Особенность Int32FrozenDictionary в том, что когда тип ключа – целое число, то его хэш равен его значению и коллизии в таком словаре не возможны в принципе. Нельзя, например, добавить 2 элемента с ключом 123 – будет выброшено исключение. Значит при чтении можно пропустить расчёт хэша и использовать значение ключа напрямую. А при создании словаря, например, пропустить удаление дублирующихся хэшей.

Благодаря этому, чтение из Int32FrozenDictionary быстрее на 36% – 42% (рис. 1).

ValueTypeDefaultComparerFrozenDictionary

Для словарей, с количеством элементов больше 10 и ключом любого другого значимого типа, кроме Int32 используется ValueTypeDefaultComparerFrozenDictionary. В этом случае коллизии могут быть, поэтому при чтении необходим расчёт хэша ключа. Но реализация всё так же основана на FrozenHashTable.

Чтение из ValueTypeDefaultComparerFrozenDictionary может быть до 80% быстрее (рис. 2).

Продолжение тут 👇

Начал готовить материал для новой статьи про производительность FrozenDictionary

Для тех, кто не в курсе, что такое FrozenDictionary, – это новая read-only generic-коллекция, которая появились в .NET 8. Его особенностью является улучшенная производительность на чтение, по сравнению с обычными коллекциями.

Что уже нашёл интересного:

1. FrozenDictionary – это абстрактный класс. Его конкретная реализация зависит от исходного словаря. Например, от типа ключа (значимый тип, string, int) или размера коллекции.

2. Некоторые реализации «‎замороженного»‎ словаря вообще не содержат хэш-таблицы. Вместо этого для поиска значения используется линейный поиск через цикл for. Видимо, для некоторых случаев это быстрее, чем считать хэш.

3. Частое используется ключевое слово ref и агрессивный инлайн методов. Возвращение по ссылке позволяет избежать копирования значимых типов. А инлайн позволяет избежать оверхеда, связанного с вызовом методов.

В скором времени узнаем, насколько быстро всё это работает.

👆 Предыдущий опрос я затеял, чтобы узнать, достаточно ли встроенных возможностей вашей IDE для повседневных задач.

Пишет ли кто-нибудь, например, кастомные сниппеты кода, кроме меня? Я их создаю, когда замечаю, что пишу много boilerplate-кода. К примеру, для тестов у меня есть 4 сниппета:

- test-method (скрин 1);
- test-data-method;
- test-data;
- test-class.

Другой пример: часто добавляю required init-only свойства в классы кастомным сниппетом propreq (скрин 2). В самом популярном расширении для C# таких сниппетов нет (скрин 3).

Собственно, вопрос к тем, кто работает с Visual Studio и Rider: занимаетесь ли вы таким задротством или там уже всё «из коробки»‌‎, и я зря страдаю?

P.S. Про даже Vim не спрашиваю. И так понятно, что тоже нужно настраивать всё под себя, как и в VS Code. 😄

P.P.S. Результаты опроса удивили. Не думал, что так много людей работает с Rider и так мало с VS Code.

Прокаченные params в C# 13

На днях Microsoft анонсировала новую версию C#. В ней есть фича, касающаяся params. Если вы не в курсе, что это такое, то вот простой пример:

public void SomeMethod() {
    ArrayParams(1);
    ArrayParams(1, 2, 3);
}

public void ArrayParams(params int[] values) {
    // some work
}

Ключевое слово params – это синтаксический сахар, позволяющий вызывать метод ArrayParams с любым количеством параметров. Но за сахар надо платить, в данном случае – ненужными аллокациями. После компиляции в методе SomeMethod на каждый вызов ArrayParams создаётся экземпляр массива int[].

public void SomeMethod() {
    int[] array = new int[1]; // аллокация 1
    array[0] = 1;
    ArrayParams(array);
    int[] array2 = new int[3]; // аллокация 2
    RuntimeHelpers.InitializeArray(array2, (RuntimeFieldHandle)/*OpCode not supported: LdMemberToken*/);
    ArrayParams(array2);
}

Но в новой версии C# можно использовать Span<T> и ReadOnlySpan<T> вместо массива.

public void SomeMethod() {
    SpanParams(1);
    SpanParams(1, 2, 3);
}

public void SpanParams(params ReadOnlySpan<int> values) {
    // some work
}

В итоге, в теле метода SomeMethod аллокаций уже не будет. То есть, если вы любите писать высокопроизводительный код, то params вместе с ReadOnlySpan<T> — ваш бро.

public void SomeMethod() {
    SpanParams(RuntimeHelpers.CreateSpan<int>((RuntimeFieldHandle)/*OpCode not supported: LdMemberToken*/));
    SpanParams(RuntimeHelpers.CreateSpan<int>((RuntimeFieldHandle)/*OpCode not supported: LdMemberToken*/));
}

Но также стоит учесть, что использование Span<T> накладывает ограничения – метод нельзя сделать асинхронным.

// valid
public async Task ArrayParams(params int[] values) {
    // some work
}

// error CS4012: Parameters or locals of type 'ReadOnlySpan<int>'
// cannot be declared in async methods or async lambda expressions.
public async Task SpanParams(params ReadOnlySpan<int> values) {
    // some work
}

🖥 Code coverage

Очень короткий пост о том, как начать отслеживать покрытие кода тестами на примере MSTest.

1. Устанавливаем расширение Coverage Gutters для VS Code. Пользователи vim и neovim простите, сегодня пост не для вас.

2. Переходим в проект с тестами и добавляем библиотеку coverlet.msbuild.

dotnet add package coverlet.msbuild --version 6.0.2

3. Выполняем команду.

dotnet test /p:CollectCoverage=true /p:CoverletOutputFormat=cobertura

4. Смотрим отчёт.

Calculating coverage result...
  Generating report '..\coverage.cobertura.xml'

+-------------+------+--------+--------+
| Module      | Line | Branch | Method |
+-------------+------+--------+--------+
| SomeProject | 100% | 100%   | 100%   |
+-------------+------+--------+--------+

+---------+------+--------+--------+
|         | Line | Branch | Method |
+---------+------+--------+--------+
| Total   | 100% | 100%   | 100%   |
+---------+------+--------+--------+
| Average | 100% | 100%   | 100%   |
+---------+------+--------+--------+

5. Жмём кнопку Watch в тулбаре VS Code (рис. 1) и изучаем покрытые и непокрытые участки кода. Они подсвечиваются зелёным и красным соответственно (рис. 2).

Поздравляю, вы великолепны!

При необходимости, результаты отчёта можно прикрутить в CI/CD в GitLab и отслеживать насколько хорошо покрыт тестами новый код из мердж реквестов (рис. 3).

💰 Зарплаты в Сербии

Недавно сербский портал N1 выпустил статью о самых высокооплачиваемых профессиях в Сербии. Как вы уже наверное догадались, больше всех зарабатывают в IT — средняя зарплата составляет 200 000 динар или 1707€. Диапазон колеблется от 587€ до 2143€, в зависимости от образования.

Вообще, в Сербии есть сайт HelloWorld, который похож на Хабр Карьеру. Там тоже вакансии, информация об IT-компаниях, отзывы и можно оставить данные о своей зарплате. Я сравнил доходы айтишников в Белграде и Москве на основе информации HelloWorld и Хабр Карьеры. На диаграммах значения после вычета налогов и без учёта премий.

Если смотреть по всем IT-специализациям, то зарплаты младших специалистов в Белграде выше или как минимум не хуже. А вот зарплаты опытных специалистов уступают на 13 – 20%.

Зарплаты разработчиков ПО тоже отличаются. В Белграде зарплаты интернов и джунов выше на 72% и 32% соответственно. Зарплаты мидлов и сеньоров ниже на 4% и 11%. Разница уже не такая большая.