Богдан Стефанюк

Нотатки про програмування, музику, подорожі та плівку
Про мене  •  Список нотаток  •  Плівка

Push Notification via ASP.NET Core

Недавно запустили на роботі новий функціонал інбоксів. Якщо коротко, то це універсальний месенджер з підтримкою різних платформ та каналів що дозволяє вести комунікацію з кінцевими клієнтами в одному місці.

Для кращого UX треба було добавити пуш нотифікації. На цей момент у нас уже були підключені веб сокети по яким ганяли різні дані, в тому числі і про нові повідомлення. Але такі сповіщення можна відобразити тільки коли відкрита сторінка в браузері.

Тому вирішили добавити підтримку браузерних пушів. Саме про те як їх підключити та використовувати в звʼязці з ASP.NET Core я хочу розказати.

Як це працює?

Процес роботи технології пуш нотифікацій у браузері досить простий. Спочатку ми запрошуємо права на отримання сповіщень у користувача. Браузер покаже йому модалку із запитанням «Do you want to receive push notifications?».

Після того як він підтвердить вибір нам потрібно підписати користувача на отримання нотифікацій використовуючи Push API браузера. Під капотом браузер робить запит на спеціальний push service та повертає нам обʼєкт PushSubscription в якому є вся необхідна інформація для відправки пушів:

{
  "endpoint": "https://fcm.googleapis.com/fcm/send/c1KrmpTuRm…",
  "expirationTime": null,
  "keys": {
    "p256dh": "BGyyVt9FFV…",
    "auth": "R9sidzkcdf…"
  }
}

Далі ми берем цей обʼєкт і відправляємо на наш сервер, де кладемо його у базу даних або зберігаємо іншим способом щоб використовувати його в подальшому.

Якщо придивитися до структури PushSubscription, можна помітити адрес ендпоінта. Суть в тому, що наш сервер не відправляє сповіщення напряму в браузер. Для цього використовується спеціальний push service, який у кожного розробника браузера свій.

Нам повезло, що браузери змогли домовитись і стандартизувати протокол push сервіса, тому нам можна не паритись за формат даних для кожного вендора. Усі вони приймають один формат даних, який містить:

  • Контент повідомлення
  • Кому його відправити
  • Як саме його відправити, з яким пріорітетом, в який топік та з яким таймаутом.

Кожне повідомлення шифрується за допомогою ключів, що були створені при генерації підписки. Крім цього, потрібно також підписувати повідомлення за допомогою приватного ключа, щоб підтвердити, що це саме наш сервер відправляє повідомлення. Виглядає це ось так:

  1. Генеруємо пару публічного та приватного ключа, які ще називають VAPID ключами. Цей крок треба зробити всього один раз. В інтернеті купа онлайн сервісів де можна згенерувати ключі.
  2. Публічний ключ використовуємо при створенні підписки на стороні браузера. Дальше цей ключ асоціюється з ендпоінтом для конкретної підписки.
  3. Приватний ключ використовуємо для підписки повідомлення на стороні нашого сервера.
  4. Дальше за допомогою публічного ключа ми можемо перевірити що повідомлення було відправлено саме нашим сервером а не кимось іншим.

Структура VAPID ключа:

{
    "sub": "mailto:[email protected]",
    "public_key": "sdgdklsnvi2f0m-12dgsg...",
    "private_key": "1fn0ASFfnaksf..."
 }

Але, як в тому жарті, є нюанс. Subject в VAPID ключі є опціональним і його не обовʼязково відправляти разом з запитом на push сервіс. Проте Сафарі так не вважає, ще й вимагає специфічний формат. Коли я генерував ключі, то мав ось такий sub mailto: <[email protected]>.

В хромі все працювало чудово, а сафарі кидав помилку, що запит невалідний. Виявилось, що вони не підтримують пробіли та кутові лапки, замінив sub на mailto:[email protected] і все запрацювало.

Реалізація бекенду

Якщо у вас macOS, то ви не зможете локально протестувати сповіщення. Проблема в тому що .NET не підтримує шифрування AesGcm на маках, тому при відправці вилетить ексепшен. Поки я не знайшов як це обійти.

На стороні сервера будемо використовувати бібліотеку Lib.Net.Http.WebPush яка під капотом буде шифрувати, підписувати та відправляти наші сповіщення. Для цього вона дає декілька базових модельок та один клас для відправки пушів.

Почнемо з реалізації створення та видалення підписок та зберігання їх в БД. Для цього добавимо клас ApplicationPushSubscription, який описує структуру таблиці та підключимо його в Entity Framework контекст:

public class ApplicationPushSubscription
{
    [Key]
    public string P256Dh { get; set; }
    public string Endpoint { get; set; }
    public string Auth { get; set; }
    public Guid UserId { get; set } // Id користувача в нашій системі
}

public class DatabaseContext : DbContext
{
    public DbSet<ApplicationPushSubscription> PushSubscriptions { get; set; }
}

Тепер створимо клас PushNotificationsService в який добавимо методи для створення та видалення підписок. Метод створення буде приймати екземпляр класу PushSubscription з бібліотеки Lib.Net.Http.WebPush.

Його можна було б змінити на свій клас, щоб логіка бібліотеки не просочувалась в інші модулі але задля простоти залишимо так як є.

public class PushNotificationsService
{
    private readonly DatabaseContext _context;
    private readonly PushServiceClient _pushClient;
    
    public PushNotificationsService (DatabaseContext context, PushServiceClient pushClient)
    {
        _context = context;
        _pushClient = pushClient;
    }
    
    public async Task CreateSubscription(Guid userId, PushSubscription pushSubscription)
    {
        var subscription = new ApplicationPushSubscription()
        {
            UserId = userId,
            AccountId = currentUser.AccountId,
            Endpoint = subscription.Endpoint,
            P256Dh = subscription.GetKey(PushEncryptionKeyName.P256DH),
            Auth = subscription.GetKey(PushEncryptionKeyName.Auth)
        };
        
        if (await _context.PushSubscriptions.AnyAsync(x => x.P256Dh == subscription.P256Dh))
        {
            return;
        }
        
        _context.PushSubscriptions.Add(subscription);
    
        try
        {
            await _context.SaveChangesAsync();
        }
        catch (DbUpdateException)
        {
            var alreadyExists = await _context.PushSubscriptions.AnyAsync(x => x.P256Dh == subscription.P256Dh);
            if (!alreadyExists)
            {
                throw;
            }
        }
    }
    
    public async Task DeleteSubscription(Guid userId, string endpoint)
    {
        var subscription = await _context.PushSubscriptions
            .FirstOrDefaultAsync(x => x.UserId == userId && x.Endpoint == endpoint);
        
        if (subscription == null)
        {
            return;
        }
        
        _context.PushSubscriptions.Remove(subscription);
        await _context.SaveChangesAsync();
    }
}

Реалізовуємо метод для відправки сповіщень нашим користувачам. Він буде приймати Id користувача якому ми відправляємо повідомлення і модель з даними.

Нам залишається отримати підписку з БД, серіалізувати повідомлення в JSON і скормити це все бібліотеці.

public async Task SendNotificationAsync(Guid userId, PushNotificationModel model)
{
    try
    {
        var applicationPushSubscriptions = await _context.PushNotifications
            .Where(x => x.UserId == userId)
            .ToList();
            
        foreach(var applicationPushSubscription in applicationPushSubscriptions)
        {
            var pushSubscription = new PushSubscription();
            pushSubscription.Endpoint = applicationPushSubscription.Endpoint;
            pushSubscription.SetKey(PushEncryptionKeyName.P256DH, applicationPushSubscription.P256Dh);
            pushSubscription.SetKey(PushEncryptionKeyName.Auth, applicationPushSubscription.Auth);
            
            var settings = new JsonSerializerSettings { ContractResolver = new CamelCasePropertyNamesContractResolver() };
            var payload = JsonConvert.SerializeObject(model, settings);
    
            var pushMessage = new PushMessage(payload);
            await _pushClient.RequestPushMessageDeliveryAsync(
                pushSubscription,
                pushMessage,
                _pushClient.DefaultAuthentication,
                VapidAuthenticationScheme.WebPush);
        }
    }
    catch (PushServiceClientException exception)
    {
        if (exception.StatusCode is HttpStatusCode.NotFound or HttpStatusCode.Gone)
        {
            _context.PushSubscriptions.Remove(subscription);
            await _context.SaveChangesAsync();
        }
        else
        {
            // Re-Throw exception or log
        }
    }
    catch (Exception exception)
    {
        // Re-Throw exception or log
    }
}

Структура класу PushNotificationModel досить проста та універсальна. Я передаю заголовок сповіщення, текст та додаткові дані:

public class PushNotificationModel
{
    public string Title { get; set; }
    public string Body { get; set; }
    public object AdditionalData { get; set; }
}

Підключаємо наш сервіс в ендопінт:

[Route("api/push-notifications")]
[Authorize]
[ApiController]
public class PushNotificationsController : ControllerBase
{
    private readonly PushNotificationService _pushNotificationService;

    public PushNotificationsController(PushNotificationService pushNotificationService)
    {
        _pushNotificationService = pushNotificationService;
    }
    
    [HttpPost("subscriptions")]
    public async Task<IActionResult> CreateSubscription([FromBody] PushSubscription subscription)
    {
        var user = HttpContext.GetCurrentUser(); // Our custom method to get current logged-in user
        await _pushNotificationService.CreateSubscription(user.Id, subscription);
        return Ok();
    }

    [HttpDelete("subscriptions")]
    public async Task<IActionResult> DeleteSubscription([FromQuery] string endpoint)
    {
        var user = HttpContext.GetCurrentUser();
        await _pushNotificationService.DeleteSubscription(user.Id, endpoint);
        return Ok();
    }
}

Все що залишається — підключити наші класи в DI і все готово. Для простоти підключення можемо добавити ще один пакет Lib.AspNetCore.WebPush.

services.AddTransient<PushNotificationService>();
services.AddMemoryVapidTokenCache();
services.AddPushServiceClient(options =>
{
    var clientOptions = configuration.GetSection(nameof(PushServiceClient));
    options.Subject = clientOptions.GetValue<string>(nameof(options.Subject));
    options.PublicKey = clientOptions.GetValue<string>(nameof(options.PublicKey));
    options.PrivateKey = clientOptions.GetValue<string>(nameof(options.PrivateKey));
});

Реалізація фронтенда

Підтримка технології Web Push була додана в Сафарі тільки в версії MacOS 13 та вище.

Перше, що потрібно реалізувати на стороні клієнта — це запит прав на отримання сповіщень. Для цього використовуємо обʼєкт Notification:

// Запит у браузера прав на підключення пушей
async function askPermission() {
    const permissionPromiseResult = await new Promise(function (resolve, reject) {
        const permissionResult = Notification.requestPermission(function (result) {
            resolve(result);
        });

        if (permissionResult) {
            permissionResult.then(resolve, reject);
        }
    });
    
    if (permissionPromiseResult !== 'granted') {
        alert("We weren't granted permission.");
    } else {
        await subscribeUserToPush();
    }
}

Після того, як отримали права, нам потрібно зареєструвати service worker в якому буде логіка відображення сповіщень, створити підписку та відправити її на наш сервер.

При створенні підписки необхідно передати наш публічний ключ. Але він повинен бути в форматі масиву байтів, тому треба спочатку його декодувати і вже тоді передавати.

В результаті отримуємо обʼєкт pushSubscription, який ми відправляємо на створений раніше ендпоінт. Крім цього, ще відправляємо Bearer токен, щоб розуміти до якого користувача привʼязати підписку.

const publicKey = "vapid-public-key";

async function subscribeUserToPush() {
    const registration = await navigator.serviceWorker.register('/service-worker.js');
    const subscribeOptions = {
        userVisibleOnly: true,
        applicationServerKey: urlBase64ToUint8Array(publicKey),
    };

    var pushSubscription = await registration.pushManager.subscribe(subscribeOptions);
   
    fetch('http://localhost:5000/api/push-notifications/subscriptions', {
        method: 'POST',
        headers: {
            'Content-Type': 'application/json',
            'Authorization': 'Bearer 1245'
        },
        body: JSON.stringify(pushSubscription)
    }).then(function (response) {
        if (response.ok) {
            alert('Successfully subscribed for Push Notifications');
        } else {
            alert('Failed to store the Push Notifications subscription on server');
        }
    }).catch(function (error) {
        console.log('Failed to store the Push Notifications subscription on server: ' + error);
    });
    
    return pushSubscription;
}

function urlBase64ToUint8Array(base64String) {
    var padding = '='.repeat((4 - (base64String.length % 4)) % 4);
    var base64 = (base64String + padding).replace(/\-/g, '+').replace(/_/g, '/');

    var rawData = window.atob(base64);
    var outputArray = new Uint8Array(rawData.length);

    for (var i = 0; i < rawData.length; ++i) {
        outputArray[i] = rawData.charCodeAt(i);
    }
    return outputArray;
};

Наш сервіс воркер буде максимально простим. Для початку додамо логіку відображення пушей та передачі в них додаткових даних з сервера.

Також необхідно додати логіку обробки кліку по сповіщенню. Ми будемо перевіряти чи відкритий сайт в браузері. Якщо ні, то відкривати його в новій вкладці. А якщо у нас вже є вкладка з сайтом, то переключаємось на неї і робимо редірект на потрібну сторінку.

self.addEventListener('push', function (event) {
    var data = event.data.json();
    // {
    //     "title": "New Notification",
    //     "body": "This is the body of the notification"
    //     "additionalData": {
    //         "pageId": "12512515"
    //     }
    // }

    event.waitUntil(self.registration.showNotification(data.title, {
        body: data.body,
        icon: '/logo.png',
        data: {
            pageId: data.additionalData?.pageId,
        },
    }));
});

self.addEventListener('notificationclick', function (event) {
    var notification = event.notification;

    event.waitUntil(
        self.clients.matchAll().then(function (allClients) {
            if (allClients.length === 0) {
                self.clients.openWindow(
                    `${self.location.origin}/page/${notification?.data?.pageId}`,
                );
                notification.close();
                return;
            }

            allClients[0]?.navigate(`/page/${notification?.data?.pageId}`);
            allClients[0]?.focus();
            notification.close();
        }),
    );
});

В результаті всіх цих маніпуляцій у нас є сервер, який вміє відправляти сповіщення та клієнт, який вміє створювати підписки, відображати сповіщення та обробляти кліки.

Окремо ще можна поговорити про топіки та пріоритети сповіщень, але це виходить за рамки цієї статті. Можливо, розкажу про це пізніше :)

Ресурси

Пам’ять про минуле Землі, Liu Cixin

Недавно я захотів почитати якусь фантастику. Чекнув свій список книг, там була «Загадна трьох тіл» від Liu Cixin. Багато хто її рекомендував і після прочитання було зрозуміло чому. Тоді я ще не знав, що наступні одинадцять днів шукатиму будь-яку можливість прочитати бодай декілька сторінок.

До цього мене тільки двічі так втягувало в книги, це були «Мартен Іден» Джека Лондона та «На західному фронті без змін» Ремарка. Я не міг спокійно ходити в магазин, гуляти та навіть в приймати душ. Читав в транспорті, в чергах, коли йшов по вулиці, перед сном і після сну. Тобто всюди, де була така можливість.

В цей період я дуже зацінив синхронізацію Kindle, коли читаєш дома з рідера, а вже в метро продовжуєш з того ж місця, але в телефоні.

Щодо самої трилогії, то її дії починаються десь в 60-х роках минулого століття під час культурної революції в Китаї. В центрі історії донька відомого вченого, яка пішла по слідам свого батька після того, як його вбили за антиреволюційні погляди. Далі книга декілька разів змінює головних героїв, а закінчується все через десятки мільйонів років.

В книзі широко використовується велика кількість концепцій з сучасної науки, такі як астрономія, квантова фізика та математика. Це сприяє більшому зануренню в історію, адже ти починаєш вірити у реальну правдивість історії.

Єдиною проблемою для мене стали персонажі. Їх в якийсь момент з’явилось дуже багато і майже всі з китайськими іменами. На початку було важко тримати в голові хто є хто і що зробив, але згодом в контексті стає зрозуміло.

Також я для себе підмітив цікаві аналогії з сучасними подіями, а саме відношення звичайних громадян ЄС та США до війни в Україні. Досить точно передані люди, для яких війна це щось далеке, про що не хочеться думати. І, звісно, зображені прямі наслідки такої «позиції».

Післясмак для мене залишився доволі приємним, та головне — відкривається інше бачення події, проблем та їх масштабу.

Однозначно рекомендую!

EDC

Every Day Carry це рух, учасники якого постійно діляться речами які вони носять з собою кожного дня, радять один одному що купити, колекціонують різні штуки, пишуть гайди і т. д.

Я досить довго спостерігав за цією тусовкою і з часом сам вирішив в неї влитися. Все починається з простих та зручних наборів і чим глибше поринаєш в цю тему, тим більше ти відкриваєш для себе скільки всього люди з собою носять. Там цілі набори для виживання в міському, та не тільки, середовищі. В них і пили, і ножі, і великі аптечки, і запаси їжі, і десятки метрів паракорду, і рації, і набори для рибалки тощо

Це все виглядає дуже круто та цікаво, але я не уявляю як це все можна носити з собою кожного дня. Тому мій набір виглядає досить скромно, в ньому тільки необхідний мінімум речей. На фото мій максимальний комплект, який я можу брати з собою, але в основному ношу тільки частину цього.

На фото:

  • Bellroy Ventura Sling 6L — бананка на 6 літрів в якій можна носити все необхідне.
  • Olympus Superzoom 70G — проста та надійна плівкова мильниця.
  • Bellroy Flip Case 2 — мінімалістичний гаманець з правами, декількома карточками та мінімальною кількістю кеша.
  • Nitecore TINI 2 — мініатюрний фонарик з максимальною потужністю 500 люмен.
  • Мікро аптечка з пластирами, дезінфікуючими салфетками та таблетками від голови.
  • Apple AirPod 3
  • Apple AirTag
  • Victorinox Climber — швейцарський ніж, зручно відкривати пиво, вино чи щось підзірати.
  • Пару сухих серветок та серветки для виведення плям.
  • Звичайні сонцезахисні окуляри.
  • Універсальний кабель inCharge X з всіма можливими розʼємами.
  • Блокнот Moleskine яким я рідко користуюсь, тому, скоріше за все, перестану його носити.
  • iPhone 13 Mini
  • Годинник Casio — мій основний годинник, ношу його частіше ніж Apple Watch

В поїздки я завжди кидаю в рюкзак свій мультитул Leatherman Rebar. Це такий собі кишеньковий ящик з інструментами яким можна відремонтувати все що захочеш. Я ним пилив невелику ялинку на новий рік, підкручував меблі, знімав розряджений акумулятор в машині, а потім встановлював його назад. І багато чого ще робив.

Також в будь-якій поїздці зі мною якась із плівкових камер, тому разом з нею я беру ось такий невеликий контейнер на три катушки. Купив його в Берліні.

Щоб заряджати все своє електронне барахло в мене є GaN зарядка UGREEN Nexode 65W з набором змінних вилок під різні розетки. Нею можна одночасно заряджати до трьох пристроїв, мені вона замінила зарядку для ноутбука.

Це в прицнипі все, на останок залишу пару посилань по темі:

Про нотатки

Софт який пройшов через мене

Не так давно з’явився великий тренд на ведення нотаток. Майже кожен місяць, якщо не частіше, виходять нові програми чи нові методики для ведення, групування та організації нотаток.

В ютубі сотні відосів де всі хвалять той чи інший підхід: зетелькастен, evergreen notes, PARA, другий мозок, персональна вікі, сотні їх. Це стало новою модою. Популярність настільки велика, що їй важко чинити опір. Тож і я залюбки став пасажиром цього хайп-трейну.

Як тільки виходила нова апка, то я обов’язково качав її, дивився відгуки й переносив все своє добро в нове місце. Витрачаючи велику кількість сил та часу, щоб все по новій організувати. Ця погоня за ідеальним блокнотом замінила собою саму суть створення нотаток.

В якийсь момент починається автоматичне створення нотаток заради нотаток. І все тільки для того, щоб це красиво виглядало і вписувалось у нову модель організації. В мене було з сотню нотаток про C#, хоча вся ця інформація легко гуглиться і лежить в документації. Тому я ними не користувався, а одразу йшов в гугл.

Складність інструментів та методик, з часом, приводили до того, що пропадало будь-яке бажання робити записи. Кожен раз, відкриваючи апку, я замість створення нотатки думав над тим яка в неї повинна бути структура, куди її треба покласти, щоб це відповідало методиці.

Також, за час постійних переїздів, вискочила ще одна проблема — проприєтарний софт. Кожен другий стартап старається завʼязати вас на свою екосистему без можливості вивантажити свої дані, а якщо така можливість є, то це зроблено настільки погано, що просто немає бажання влазити в це. Коли ж мова йде про нотатки, то не хочеться, щоб вони пропали разом зі збанкрутілою компанією.

Тому я на довго забив та вів записи як попало. Проте десь пів року назад я вирішив спробувати заново, але кардинально змінивши підхід.

Першим ділом під видалення попали майже всі нотатки, що стосувалися програмування. Я вибрав найпростіший інструмент, який був мені доступним із коробки — Apple Notes. Коли у вас вся екосистема від Apple, то створювати та синхронізувати нотатки стає набагато легше.

Наступним кроком була відмова від бездумного накопичування нотаток. Додаю тільки ту інформацію, яка рідко змінюється або важко гуглиться. Сюди можна віднести різні концепції із computer science чи system design. Зазвичай це важко нагуглити або інформація розкидана по різних книжках чи статтях. В такому випадку буде корисним зібрати все до купи й описати це зрозумілою для себе мовою.

Все, що стосується мов програмування, бібліотек, функцій та методів зазвичай дуже легко гуглиться і немає сенсу додавати це до себе.

Проте, одного разу мені стало тісно в Apple Notes, тоді під руку трапилась програма Nota. Власне кажучи, це звичайний редактор Markdown файлів без наворотів. Тому все, що стосується програмування та IT, переїхало туди.

І тут я хочу підмітити одну важливу думку: не кидайтесь на першу-ліпшу програму. Почніть з самого простого і розвиньте звичку просто вести нотатки. Візьміть за правило не змінювати інструмент раніше шести місяців. Користуйтесь та відмічайте те, чого вам не вистачає. Вже потім шукайте інструмент який зможе закрити саме ваші проблеми, а не навʼязані.

Зараз мій сетап виглядає максимально просто. Всі персональні нотатки живуть в Apple Notes, а все що стосується ІТ живе в Nota.

Я не проти Obsidian, Roam чи іншого подібного софта. Для когось вони дійсно ідеальні та закривають всі потреби. Я лише хочу застерегти вас від хайпу та навʼязування вам проблем чи потреб, яких ви не мали. Можливо, зрештою, найкомфортнішою програмою саме для вас стане Obsidian, але це буде чітке та кайфове рішення, яке закриватиме необхідні потреби.

Найцікавіше, що це стосується не тільки блокнотів, але і софта для todo-списків. Я мав ті ж самі проблеми, що описав. В якийсь момент був модним GTD і я намагався максимально інтегрувати його у своє життя. Правда потім дивувався чому система не працює, а насправді вона просто не була потрібна мені. Я міг обійтись звичайним текстовим файлом, але піддався хайпу і пробував натягнути сову на глобус.

Як підсумок, бажаю вам знайти ідеальні для вас інструменти, які будуть закривати ваші потреби та допомагатимуть кожного дня.

Фото-нотатки за літо

Очередь с приоритетом

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

Такой список достаточно просто реализовать с помощью обычного массива. Задачи будем хранить в случайном порядке, а в момент получения текущей задачи будем искать самую приоритетную. В таком случае добавление новой задачи будет иметь сложность O(1), а вот получение O(n), потому что каждый раз нужно искать элемент с самым большим приоритетом.

Второй вариант тоже использует обычный массив, только элементы в нем хранятся уже в отсортированном виде. В таком случае сложность меняется зеркально. Добавление нового элемента будет занимать O(n), а получение O(1).

Оба варианта не совсем эффективны, особенно когда очень много данных. Здесь на помощь приходят очереди с приоритетом.

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

Двоичная куча

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

Для хранения данных кучи удобно использовать обычные массивы. Такой подход занимает мало места и сам по себе достаточно элегантный. На как определить какой элемент массива на какой ссылается? Для этого есть две простые формулы.

  • 2i + 1 — позволяет найти позицию левого дочернего элемента
  • 2i + 2 — позволяет найти позицию правого дочернего элемента

Сортировка дерева

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

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

Как это выглядит в коде:

private void SortHeap(int i)
{
	var size = values.Count;
	var left = 2 * i + 1;
	var right = 2 * i + 2;
	var largest = i;
	
	if (left < size && values[left] > values[largest])
		largest = left;
		
	if (right < size && values[right] > values[largest])
		largest = right;
		
	if (largest != i)
	{
		var temp = values[i];
		values[i] = values[largest];
		values[largest] = temp;
		SortHeap(largest);
	}
}

Делаем кучу из обычного массива

Мы умеем сортировать элементы в поддеревьях, теперь применим этот метод для того, чтобы с обычного массива сделать кучу. Так как потомки гарантированно есть у первых (n/2 — 1) элементов, то достаточно только для них вызвать метод SortHeap.

private void MakeHeap()
{
	for (int i = values.Count / 2 - 1; i >= 0; i--)
	{
		SortHeap(i);
	}
}

Добавление нового элемента

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

if (values.Count == 0)
{
	// Просто добавляем в элемент в массив, если он пустой
	values.Add(value);
}
else
{
	// Добавляем элемент в конец массива и запускаем сортировку дерева
	values.Add(value);
	for (int i = values.Count / 2 - 1; i >= 0; i--)
	{
		SortHeap(i);
	}		
}

Удаление элемента

Чтобы удалить элемент нужно поменять его с последним элементов в куче, потом удалить и запустить сортировку кучи. Так как мы делаем очередь, то будем всегда удалять первый (корневой) элемент кучи.

var size = values.Count;
		
var last = values.Count - 1;
var temp = values[0];
values[0] = values[last];
values[last] = temp;
values.RemoveAt(last);

for (int i = size / 2 - 1; i >= 0; i--)
	SortHeap(i);

return temp;

Итого

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

  • Enqueue — обычная вставка в кучу, ничего даже менять не нужно.
  • Dequeue — обычное удаление элемента с кучи, только удаляем мы всегда элемент с 0 индексов.

Посмотреть полную реализацию можно на dotnetfiddle.
 

Последнее прочитанное

Редко пишу о книгах, которые читал или читаю. В этот раз решил рассказать сразу о нескольких прочитанных книгах. Они из разных жанров, но каждая чем-то меня зацепила.

Стив Джобс

Пока что это самая интересная биография из всех, которые я читал. В ней описана вся история Джобса начиная со школьных времён и заканчивая смертью. Больше всего мне понравилось описания принципов, которыми он руководствовался при создании продуктов. Очень интересно было прочитать про создание Macintosh, iPod и iPhone. Книгу прочитал с большим удовольствие и думаю что еще перечитаю спустя какое-то время.

Книга большая, за один раз не проглотить. Читал в бумажном виде и держал на столе, чтобы читать в свободную минуту. Определенно 5/5.

Твой лучший друг, желудок

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

В книге подробно рассказывается про то, как работает вся наша система пищеварения, за что отвечает каждый орган, как вообще пища влияет на жизнь. Вся эта информация подкреплена современными научными исследованиями, на которые много ссылок. Мне больше всего понравилась критика современных диет, БАДов и прочее. Также интересно было узнать про влияние пищи на долголетие.

Заметил только один минус — иногда встречается слишком много медицинской терминологии. Но я понимаю, что без нее никуда, да и в принципе на ней можно не заострять внимание. Главное это понять идеи, которые там заложены и общее понимание работы организма. Советую прочитать тем, кто худеет (как я) и тем, кто переживает по поводу еды.

Твой первый трек

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

Для меня таким конспектом и гайдом стала книга «Твой первый трек». В ней полностью разбирается процесс написание музыки, от наброска простого бита до мастеринга и психологической составляющей творчества.

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

Статья о том как создавалась книга: https://maximilyahov.ru/blog/all/maskeliade-design/

Грокаем алгоритмы

Это классика, это знать надо. Лучшая книга по алгоритмам и структурам данных. Пока читал, несколько раз словил «Aha moment». Каждая идея, каждый концепт очень подробно расписан и приправлен иллюстрациями. Такого качества материала я еще не встречал.

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

Бинарный поиск и бинарное дерево поиска

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

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

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

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

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

А теперь живой пример. Есть отсортированный массив и нужно найти число 9. Берем элемент из середины — 8, сравниваем, 9 больше 8, значит нужно продолжить поиск в правой части.

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

Берем элемент из середины — 9, сравниваем, элементы равны, число 9 есть в массиве и храниться по индексу 4. Мы нашли нужный элемент всего за 3 шага.

Если пробовать оценить скорость работы алгоритма, то получается что она равна O(log n). Для сравнения, обычный поиск перебором имеет скорость O(n), это значит что нужно перебрать все элементы массива. Что это значит на практике?

Посмотреть реализацию на C# можно на dotnetfiddle.

Как оптимизировать сортировку?

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

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

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

Как работает поиск в дереве?

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

Вставка нового элемента работает так же как и поиск. Сравниваем новый элемент с текущим и опускаемся по дереву вниз пока не найдем подходящее место. В итоге при каждом добавлении у нас будет отсортированный набор данных.

Но что будет если всегда добавлять элементы с все большим и большим значением? Наше дерево будет выглядеть вот так:

По сути для поиска значения на нужно обойти все элементы дерева, а это значит что скорость работы упадет до O(n). Получается что бинарное дерево поиска в среднем работает со скоростью O(log n), а в худшем O(n).

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

Итог

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

Если тема интересная, то можно копнуть дальше и разобраться с:

  • Красно черными деревьями
  • Кучами
  • B-деревьями
  • и т. д.

Бонус

На сайте https://idea-instructions.com есть объяснения разных алгоритмов в стиле инструкций с икеи. Например AVL дерево

Kindle

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

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

Что мне понравилось в Kindle? Небольшой размер, думал купить большую читалку, но понял что маленький размер намного оптимальнее. Ее удобно держать одной рукой и при этом она не устаёт. Также она помещается в карманы куртки или в бананке.

Подсветка, спасает в темное время суток. Тут Амазон постарался и сделал качественно, минимальная яркость не выжигает глаза ночью, как в некоторых других ридерах.

Минусы. Заметил только один — собственный формат mobi. Если покупать книги онлайн, то проблемы с форматами не будет, почти все магазины позволяют скачать книгу в любом удобном формате. Если же качать книги с других сайтов, то могут быть проблемы, потому что не все есть в формате mobi.

На днях амазон анонсировал что будет уходить от mobi в сторону epub, но я пока не пробовал как оно работает. Обновление еще не пришло.

В общем электронная книга это крутая альтернатива тупежу в телефон. С ней реально хочется больше читать.

Транзакции в базах данных и ACID

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

Базы данных гарантируют что все запросы в рамках транзакции выполняться как одно целое или не выполняться вообще. Отталкиваясь от этой концепции был придуман набор требований к транзакциям и системам, которые их используют. Эти правила гарантируют надежную работу транзакций. Такой набор требований называется ACID.

ACID гарантирует что данные в БД будут целостные независимо от любых сбоев.

Всего есть четыре свойства у транзакций:

  • Atomicity (атомарность) — команды внутри транзакции буду выполнены все вместе или ни одной. То есть транзакция это атомарная команда. Достигается это за счет системы откатов и журнала транзакций. Если внутри транзакции какой-то запрос выполнился с ошибкой, то все изменения, сделанные в рамках этой транзакции откатываются.
  • Сonsistency (консистентность) — данные должны быть консистентными после выполнения транзакции. Это значит что в них нету логических и технических противоречий. Например: суммарный баланс счетов должен оставаться неизменным, это логическая целостность. Записи в таблицах не ссылаются на удаленные идентификаторы в другой таблице — техническая целостность.
  • Isolation (изолированность) — транзакции зачастую обрабатываются параллельно, это значит что они не должны влиять друг на друга. Так если два человека одновременно пересылают деньги третьему, то одна транзакция может переписать данные другой и деньги потеряются. На практике изоляция достигается за счет уровней изоляции.
  • Durability (стойкость) — если транзакция завершена успешно, то она не может быть отменена даже при авариях, внезапном отключении света в датацентре и проблем в сети. В этом случае база данных должна сама восстановить последние изменения.

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

  • read uncommited — позволяет избежать потерянных обновлений, когда две транзакции изменяют одни и те же данные. Для этого одна транзакция блокирует данные, которые хочет изменить для других UPDATE операций в других транзакциях.
  • read committed — решает проблему грязного чтения, когда вычитываем данные во время их обновления. Это может привести к тому что мы получим частично обновленные данные. В таком случае UPDATE операции в транзакции блокируют UPDATE и SELECT операции в других транзакциях. Именно этот уровень изоляции используется по умолчанию в большинстве БД.
  • repeatable read — внутри транзакции может быть несколько операций SELECT, которые читают одни и те же данные. Repeatable read гарантирует что это операции внутри одной транзакции будут возвращать одинаковые данные. Даже если другие транзакции хотят их удалить или изменить. В таком случает транзакция блокирует все строчки, которые затрагивают операции UPDATE и SELECT.
  • serializable — исключает проблему «фантомных чтений», которые возникают при вставке новой строки между двумя операциями SELECT внутри одной транзакции. Больше всего эта проблема влияет на агрегационные запросы. Такой уровень изоляции является самым строгим, все транзакции выполняются так, будто других параллельных транзакций не существует.
Раніше Ctrl + ↓