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

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

В ютубі сотні відосів де всі хвалять той чи інший підхід: зетелькастен, 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 дерево

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

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

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

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

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

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

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

ASP.NET, как и большинство других фреймворков, предлагают использовать свою структуру организации файлов в проекте. Почти всегда используется folder by type подход. Он предполагает разделение файлов по типу. Так все контроллеры лежать в одной папке, вьюхи в другой и т. д.

com.example
├── Domain
│    ├── User.cs
│    └── Pet.cs
├── Controllers
│    ├── UserController.cs
│    └── PetController.cs
├── Repositories
│    ├── UserRepository.cs
│    └── PetRepository.cs
├── Services
│    ├── UserService.cs
│    └── PetService.cs
│   // and everything else in the project
└── Startup.cs

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

Альтернативой является folder by feature подход, при котором все файлы одной фичи лежат в отдельной папке. В таком случае все необходимое для конкретной фичи лежит под рукой и нет ничего лишнего.

Это позволяет:

• Упростить навигацию в проекте.
• Построить высокоуровневую абстракцию — открываешь проект и сразу понятно что он из себя представляет, из чего состоит.
• Выделить вертикальные слои.

com.example
├── Pet
│    ├── Pet.cs
│    ├── PetController.cs
│    ├── PetRepository.cs
│    └── PetService.cs
├── User
│    ├── User.cs
│    ├── UserController.cs
│    ├── UserRepository.cs
│    └── UserService.cs
│   // and everything else in the project
└── Startup.cs

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

Ссылки:
Folder-by-type or Folder-by-feature

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

Choose Boring Technology — статья-презентация от одного из первых разработчиков Etsy. Рассказывает про выбор технологий для проекта. Основная идея в том чтобы выбирать «скучные», а если быть точнее, то хорошо изученные и устоявшиеся технологии. Горячо советую почитать.

Introduction to architecting systems for scale — кратко о том из чего состоят приложения, которые рассчитаны для масштабирование.

Celebrate tiny learning milestones — не совсем техническая статья. Вместо того чтобы придумывать себе большие цели на год, лучше придумать набор небольших целей «майлстоунов» и идти по ним.

Get your work recognized: write a brag document — очень частая проблема это распознавание того что ты сделал на проекте. Когда приходит перформанс ревью, то бывает сложно вспомнить все что ты сделал за год. Автор советует завести документ в который нужно записывать результаты своей работы, а именно то, что было сделано и к чему это привело.

Good Logging — коротко о том какими должны быть логи чтобы ими было удобно пользоваться. Ну и сразу еще две статьи от этого же автора: Great Programmers Write Debuggable Code и Finding Bugs: Debugger versus Logging

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

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

Хочу обратиться к читателям с белоруссии и россии. Чтобы вам там не говорили по телевизору, здесь настоящая война, здесь настоящий ад на земле. И это дело рук ваших «доблестных» солдат. В первой версии этого поста я просил выйти вас на улицу, поднимать шум. Сейчас я понимаю что это бессмысленно. Часть вас просто боится, а второй части пофиг. Попрошу вторых забыть этот блог и никогда на него не заходить.

Ниже просто подборка фото и видео, напоминание об этой войне. О том что здесь происходит.

Победа будет за нами! Слава Україні!