🖥 Задача: быстрое возведение в степень (⭐️)

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

double x = 3;
int n = 3;
double result = FastPow(x, n);

👉 27

double x = 3;
int n = 1;
double result = FastPow(x, n);

👉 1

double result = FastPow(2, 18);

👉 262144

FastPow(2, 51);

👉 2251799813685248

FastPow(3, 32);

👉 1853020188851841

FastPow(9, 13);

👉 2541865828329

FastPow(5, 16);

👉 152587890625

Пишите варианты в комментариях. Решение будет сегодня вечером новым постом в канале.

#Задача #Lvl1

🖥 Фильтр Блума

Представим, что мы крупный сайт — какой-нибудь маркетплейс — и нам нужно определять количество уникальных посетителей. Как мы это сделаем? Вполне логичным решением будет сохранение нового IP-адреса из потока сетевого трафика в список, а общее количество элементов такого списка и будет сообщать нам количество уникальных посетителей.

Вопреки такому решению, хранение всех этих данных (IP`шки) для нас может быть лишним. Мы не будем их использовать в дальнейшем, но каждый хранимый объект в памяти будет непременно "раздувать" его общее заполнение. В оптимизации такой задачи нам и поможет фильтр Блума, который мы сегодня рассмотрим на примере поставленной задачи.

➡️ Что это и как он работает
Фильтр Блума проверяет принадлежность конкретного элемента к множеству данных без необходимости его хранения. Он использует массив битов (0 — false, 1 — true), а также несколько хеш-функций. Когда новый объект попадает в базу, его хеш-коды вычисляются, заполняя соответствующие биты массива в значении 1. Например, если хеш-функция возвращает число 50, то 50 бит (он же индекс) массива устанавливается в 1. Так происходит добавление IP-адреса в фильтр.

Если при получении нового IP-адреса все нужные биты уже установлены в значение 1, то это значит, что он уже встречался ранее. Но важно помнить, что фильтр Блума не даёт 100% гарантии, что IP-адрес был уже замечен. Всегда есть небольшой риск ложноположительного результата. Эта вероятность зависит от размера массива битов, количества хеш-функций и количества уникальных IP-адресов.

Фильтр Блума экономит память системы, особенно при работе с большими множествами, ускоряя операции добавления/проверки. Он подходит для задач проверки принадлежности, особенно когда требуется скорость при работе системы в условиях ограниченной памяти. Несмотря на небольшой процент ложноположительных результатов, он широко используется в разных приложениях.

➡️ Снижение вероятности коллизий
Коллизии возникают, когда несколько различных элементов имеют одинаковые хеш-коды, что может привести к ложноположительным результатам при проверке.

Стратегии снижения вероятности коллизий:
⏺Увеличение размера массива битов;
⏺Увеличение количества хеш-функций;
⏺Выбор качественных хеш-функций.

➡️ Простая реализация

public class BloomFilter<T>
{
    public BloomFilter(int capacity, int hashFunctionCount)
    {
        if (capacity < 1) throw new ArgumentOutOfRangeException(nameof(capacity), "Размер должен быть положительным");
        if (hashFunctionCount < 1) throw new ArgumentOutOfRangeException(nameof(hashFunctionCount), "Количество хеш-функций должно быть положительным");

        bitArray = new(capacity);
        hashCount = hashFunctionCount;
    }

    private readonly BitArray bitArray;
    private readonly int hashCount;

    public void Add(T item)
    {
        foreach (int hash in GetHashValues(item))
        {
            bitArray[hash] = true;
        }
    }

    public bool Contains(T item)
    {
        foreach (int hash in GetHashValues(item))
        {
            if (!bitArray[hash]) return false;
        }

        return true;
    }

    public void Clear() => bitArray.SetAll(false);

    private IEnumerable<int> GetHashValues(T item)
    {
        for (int i = 0; i < hashCount; i++)
        {
            int seed = i * 31;
            int hash = (item?.GetHashCode() ?? 0) ^ seed;
            yield return Math.Abs(hash) % bitArray.Length;
        }
    }
}

Проверим:

var filter = new BloomFilter<string>(1000, 5);
var apple = "apple";
var banana = "banana";

filter.Add(apple);
filter.Add(banana);
Check(apple);
Check(banana);
Check("date");
Check("grape");

filter.Clear();
Check(apple);
Check(banana);

void Check(string item) => Console.WriteLine(filter.Contains(item));

Вывод:

True
True
False
False
False
False

Отмечу, что реализация сильно простая. Рекомендую заменять GetHashCode на хеш-функцию MurmurHash2, MD5 или др. Ставьте реакции на пост, если хотите посмотреть на лучшую реализацию — напишу в комментариях.

#Полезно #Хеширование #GetHashCode #Array

🖥 BenchmarkDotNet: измерение производительности

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

➡️ Пример использования
Рассмотрим базовое использование библиотеки. Для этого создадим новый проект консольного приложения и через Nuget добавим пакет BenchmarkDotNet.

Рассмотрим примитивную программу, которая склеивает строки:

using System.Text;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkRunner.Run<StringTest>();

public class StringTest
{
    public StringTest() { }

    private string[] numbers = { "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten" };

    [Benchmark]
    public string StringBuilder()
    {
        StringBuilder stringBuilder = new StringBuilder();

        foreach (string str in numbers)
        {
            stringBuilder.Append(str);
            stringBuilder.Append(' ');
        }

        return stringBuilder.ToString();
    }

    [Benchmark]
    public string Concatenation()
    {
        string result = "";

        foreach (string str in numbers) result = result + str + " ";

        return result;
    }

    [Benchmark]
    public string Interpolation()
    {
        string result = "";

        foreach (string str in numbers) result = $"{result}{str} ";

        return result;
    }
}

Мы определили класс StringTest, который определяет массив numbers из 10 строк и три метода. Методы используют разные техники, склеивая все эти строки в одну и возвращая её в качестве результата.

Для тестирования все методы должны иметь модификатор public и к ним должны применяться атрибуты [Benchmark]. Сам класс, который содержит эти методы, тоже должен иметь модификатор public.

Для запуска теста вызывается метод BenchmarkRunner.Run, который типизируется нашим классом:

BenchmarkRunner.Run<StringTest>();

Особенности запуска такого проекта:
⏺Следует запускать проект в Release конфигурации;
⏺Для большей точности рекомендуется выключить все остальные приложения, кроме текущего и стандартных процессов ОС;
⏺Если для тестирования используется ноутбук, то лучше его подключить к электросети и использовать наиболее производительный режим.

По завершению теста консоль отобразит нам результаты. Нас интересует следующая таблица:

| Method        | Mean     | Error   | StdDev   |
|-------------- |---------:|--------:|---------:|
| StringBuilder | 313.5 ns | 6.31 ns | 17.49 ns |
| Concatenation | 427.0 ns | 8.51 ns |  7.96 ns |
| Interpolation | 428.7 ns | 5.10 ns |  4.26 ns |

Здесь столбец "Mean" представляет среднее время выполнения в наносекундах. Так, мы видим, что выполнение метода StringBuilder завершилось немногим быстрее, чем у других методов.

Инструмент имеет множество различных настроек и возможностей конфигурации. Полная документация библиотеки.

#Полезно #Benchmark

🖥 Задача: гномья сортировка (⭐️)

Написать метод, который принимает массив целочисленного типа и сортирует его алгоритмом гномьей сортировки. Ниже приведены примеры.

int[] arr = { 21, -53, 75, -49, -80, 100, -48, 27, 38, -47, -42, -72 };
GnomeSort(arr);

👉 [-80, -72, -53, -49, -48, -47, -42, 21, 27, 38, 75, 100]

int[] arr = { 175, 136, 138, 300, 147, 252, 204, 91 };
GnomeSort(arr);

👉 [91, 136, 138, 147, 175, 204, 252, 300]

int[] arr = { 61, 45, 25, 31, 110, 48, 90, 114, 70, 60, 18, 112, 7, 82, 41, 39, 115, 84, 26, 29, 21, 57, 116, 65, 45 };
GnomeSort(arr);

👉 [7, 18, 21, 25, 26, 29, 31, 39, 41, 45, 45, 48, 57, 60, 61, 65, 70, 82, 84, 90, 110, 112, 114, 115, 116]

int[] arr = { 6, 18, -7, -9, -12, -16, 0, 8, 7, 3, -2, -10, 1, -9, 9, -6, 11, 4 };
GnomeSort(arr);

👉 [-16, -12, -10, -9, -9, -7, -6, -2, 0, 1, 3, 4, 6, 7, 8, 9, 11, 18]

int[] arr = { 8, 7, 6, 4, 3, 1 };
GnomeSort(arr);

👉 [1, 3, 4, 6, 7, 8]

Пишите варианты в комментариях. Решение будет сегодня вечером новым постом в канале.

#Задача #Lvl1

🖥 Выражение stackalloc

Ранее я уже немного писал о stackalloc, однако сейчас хочу разобрать более детально этот вопрос.

Ключевое слово позволяет выделить память под массив в стеке. Смысл выделения памяти в стеке — это повышение быстродействия кода. Выделенный стеком блок памяти автоматически удаляется при выходе из этого метода, поэтому он не подлежит сборке мусора.

➡️ Убедимся в этом
Конструкторы ссылочных типов, используя оператор new, выделяют память в куче, а значит мы можем убедиться в том, что stackalloc не занимает память в куче.

Напишем класс:

[MemoryDiagnoser]
public class MemoryBenchmark
{
    public MemoryBenchmark() { }

    [Benchmark]
    public void HeapArray()
    {
        decimal[] arr = new decimal[100];
        
        for (int i = 0; i < 100; i++) arr[i] = 123;
    }

    [Benchmark]
    public unsafe void StackArray()
    {
        decimal* arr = stackalloc decimal[100];
        
        for (int i = 0; i < 100; i++) arr[i] = 123;
    }
}

Метод HeapArray создаёт массив в привычном нам виде, а метод StackArray создаёт массив через аллокацию памяти в стеке. Для бенчмарка мы помечаем класс и методы соответствующими атрибутами.

Специально для примера берём самый объёмный тип decimal, который занимает 16 байт и 100 его элементов. Из этого следует, что мы ожидаем ~1600 занятых байтов в памяти (16 * 100). Запустим тест:

BenchmarkRunner.Run<MemoryBenchmark>();

Дождавшись результатов, я получил следующий отчёт:

| Method     | Mean     | Error   | StdDev   | Gen0   | Allocated |
|----------- |---------:|--------:|---------:|-------:|----------:|
| HeapArray  | 322.1 ns | 6.39 ns | 12.00 ns | 0.7763 |    1624 B |
| StackArray | 228.7 ns | 3.15 ns |  2.95 ns |      - |         - |

Столбец "Allocated" сообщает, что метод HeapArray занял 1624 байта, что мы и ожидали. Метод же StackArray ни аллоцировал и байта, что свидетельствует поставленной задаче.

А теперь посмотрим на столбец "Mean": 322.1 наносекунд против 228.7 — разница в скорости заметная.

➡️ Некоторая особенность
При выделении слишком большого объёма памяти в стеке возникает исключение StackOverflowException.

Рекомендуется ограничить объём памяти, выделяемый под стек, например, как в следующем коде:

int length = 1000;
Span<byte> buffer = length <= 1024 ? stackalloc byte[length] : new byte[length];

Поскольку объём доступной памяти на стеке зависит от среды, в которой выполняется код, при определении фактического предельного значения следует использовать консервативное значение.

➡️ Проверим очистку стека
Хоть это и ни к чему, но давайте убедимся в очистке стека после выхода из метода. Напишем и запустим следующий код:

var t = new Test();
t.Print();

public unsafe class Test
{
    public Test()
    {
        int* ptr = stackalloc int[length];
        pointer = ptr;

        for (int i = 0; i < length; i++) ptr[i] = i + 1;

        Print();
    }

    private const int length = 5;
    private int* pointer;

    public void Print()
    {
        for (int i = 0; i < length; i++) Console.WriteLine(pointer[i]);
        Console.WriteLine("------------");
    }
}

Вывод:

1
2
3
4
5
------------
1
0
2100389455
2046
5
------------

При первом выводе массива на экран всё работает как и ожидается, ибо вызов метода Print происходит внутри конструктора, где была выделена память.

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

#Полезно #Array #Unsafe #Pointers #Benchmark

🖥 Валидация объектов

Валидация — это процесс проверки данных различных типов по критериям корректности и полезности для конкретного применения.

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

Фреймворк .NET предлагает удобный функционал в виде атрибутов из пространства имён System.ComponentModel.DataAnnotations. Я же люблю ручную самовалидацию, что мы и разберём ниже.

➡️ Разбор на примере
Рассмотрим крайне популярный процесс валидации на сегодняшний день — это корректность создаваемого пароля.

Сперва напишем интерфейс для валидации объектов. Я предпочитаю использовать сразу две версии, классическую и с обобщением, что расширит его гибкость:

public interface IValidatable
{
    bool IsValid(object context);
}

public interface IValidatable<Tin, TOut> : IValidatable
{
    TOut Validate(Tin context);
}

Теперь вспомним о современных требованиях к паролю. По классике — это 8+ символов, минимум 1 цифра, минимум 1 заглавная буква и минимум 1 специальный символ. В связи с этим мы можем реализовать структуру с обязательными требованиями к паролю:

public struct PasswordRequirements
{
    public int MinLength { get; }
    public int MinUppercase { get; }
    public int MinDigits { get; }
    public int MinSpecialChars { get; }

    public PasswordRequirements() : this(8, 1, 1, 1) { }
    public PasswordRequirements(int minLength, int minUppercase, int minDigits, int minSpecialChars)
    {
        MinLength = minLength;
        MinUppercase = minUppercase;
        MinDigits = minDigits;
        MinSpecialChars = minSpecialChars;
    }
}

Теперь нам нужен класс, который и реализует валидацию нашего пароля. Я предпочитаю извлекать методы валидации в отдельные объекты, что позволяет более гибко тестировать фактические типы данных. Дополнительно класс-валидации мы можем использовать как временный объект с некоторой доп. инфой — оценка сложности пароля (слабый/средний/хороший) и т. п. —, без нужды вечного хранения такой информации. Напишем же такой класс:

public class PasswordValidation : IValidatable<string, bool>
{
    public static PasswordRequirements Requirements { get; }
    // Здесь можно добавить свойство
    // оценки сложности пароля

    static PasswordValidation() => Requirements = new();
    public PasswordValidation() { }

    public bool IsValid(object password) => Validate(password?.ToString());
    public bool Validate(string password)
    {
        if (string.IsNullOrWhiteSpace(password) || password.Length < Requirements.MinLength) return false;
        
        int uppercases = 0, digits = 0, specialChars = 0;
        foreach (char c in password)
        {
            if (char.IsUpper(c)) uppercases++;
            else if (char.IsDigit(c)) digits++;
            else if (!char.IsLetterOrDigit(c)) specialChars++;
        }

        return uppercases >= Requirements.MinUppercase && digits >= Requirements.MinDigits && specialChars >= Requirements.MinSpecialChars;
    }
}

Поскольку требования к паролю у нас для всех юзеров одинаковы свойство Requirements у меня статическое.

Финалим наш пример фактическим типом пароля:

public class Password
{
    public string Hash { get; }

    static Password() => validator = new();
    public Password(string value)
    {
        if (!validator.Validate(value)) throw new FormatException();

        // Hash = ComputeMd5Hash(value);
        // ...
    }

    private static readonly PasswordValidation validator;
}

Таким образом пароль будет проверяться сразу при инициализации и выбрасывать исключение при несоответствии требований:

Password p1 = new("qwerty"); // Ошибка
Password p2 = new("123qwerty"); // Ошибка
Password p3 = new("Qwerty123@"); // Успех

Валидацию пароля можно проверять и до инициализации фактического класса, ибо классы независимы друг от друга — это одна из гибкостей, о которой я писал выше.

#Полезно #Пароль #Generics

🖥 Задача: постоянная Капрекара (⭐️⭐️)

Написать метод, который принимает число, реализует алгоритм нахождения постоянной Капрекара и выводит итерации на экран. Метод должен уметь работать с трёхзначными и четырёхзначными числами. Ниже приведены примеры.

KaprekarConstant(5621);

👉 6521 - 1256 = 5265
👉 6552 - 2556 = 3996
👉 9963 - 3699 = 6264
👉 6642 - 2466 = 4176
👉 7641 - 1467 = 6174

KaprekarConstant(796);

👉 976 - 679 = 297
👉 972 - 279 = 693
👉 963 - 369 = 594
👉 954 - 459 = 495

KaprekarConstant(3412);

👉 4321 - 1234 = 3087
👉 8730 - 378 = 8352
👉 8532 - 2358 = 6174

KaprekarConstant(6389);

👉 9863 - 3689 = 6174

KaprekarConstant(123);

👉 321 - 123 = 198
👉 981 - 189 = 792
👉 972 - 279 = 693
👉 963 - 369 = 594
👉 954 - 459 = 495

Пишите варианты в комментариях. Решение будет сегодня вечером новым постом в канале.

#Задача #Lvl2