#prog #amazingopensource

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

github.com/donnemartin/system-design-primer

#prog #article

Мы всё ещё не умеем программировать.

This paper presented an in-depth analysis of 198 user-reported failures in five widely used, data-intensive distributed systems in the form of 12 findings. We found that the error manifestation sequences leading to the failures to be relatively complex. However, we also found that for the most catastrophic failures, almost all of them are caused by incorrect error handling, and 58% of them are trivial mistakes or can be exposed by statement coverage testing.

https://www.eecg.toronto.edu/~yuan/papers/failure_analysis_osdi14.pdf

#prog

Челлендж закончился, и что же Leetcode предлагает теперь? Вы не поверите — ещё один месячный челлендж.
С другой стороны, мне мероприятие понравилось, так что в майском варианте я также буду участвовать. Тем более что теперь я смогу решать все задачи в тот же день, что они появились, и таким образом получить шанс на выигрыш призов.

https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/

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

Сделал. Был доволен собой (очень уж там много граничных случаев было). А потом увидел, что моё решение хоть и быстрое, но далеко не лучшее по скорости. Открыл топовое решение — там двухсвязный список на сырых указателях :(

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

#prog #моё

Ещё одна вещь, которая мне запомнилась — это решение задачи про подсчёт количества островов. Всё просто: есть двухмерный массив из 1 и 0 ("суша" и "вода" соответственно), требуется подсчитать количество связных (в смысле окрестности фон Неймана) областей из единиц. Простейший способ решить задачу — это бахнуть depth first search (и в силу того, что вход дан как Vec<Vec<char>>, его даже можно спокойно менять), но этот вариант я сразу отмёл — ведь это же медленно, это же надо прыгать нелинейно по памяти и портить кеш (не говоря уже о том, что там нужно возиться с индексами, что я страшно не люблю делать)! Так что я решил пойти умным путём и решить задачу путём однократного сканирования каждой строки.

Идея была относительно простой: мы проходимся по каждой строке. Нули ("воду") мы просто пропускаем. Для единиц же мы проверяем соседей слева и сверху у текущего элемента. Если оба соседа — "вода", то создаётся новая территория, и текущей единице приписывается идентификатор этой территории. Если сосед-"земля" только один, то мы приписываем этой клетке ту же территорию, что и у соседа. Если соседа-"земли" — два, причём с разными идентификаторами, то нам нужно объединить эти две территории. В отдельной табличке под территории для каждого id записано, является ли территория самостоятельной или же частью другой территории (в таком случае там лежит id этой другой территории). Очевидно, нужно для одной из территорий записать, что одна является частью другой, но какую из них модифицировать? Я решил, что стоит всегда территорию с бо́льшим id делать частью территории с меньшим id. Таким образом, все связи (ссылки на "родительскую" территорию) могут перемещаться только ближе к нулю, но никогда дальше от него. Я убедил себя, что этого (вкупе с тем фактом, что id строго возрастают при создании) достаточно для корректного решения задачи. Прогнал своё решение на тестовых примерах, получил правильный ответ и отправил своё решение, будучи уверен, что пройду полный набор тестов.

Ага, щас.

Мне прилетел случай, когда моё решение давало ответ, на единицу отличающийся от правильного. Это выглядело странно, потому что это не могло быть эффектом ошибки на единицу — в противном случае более простые примеры давали бы ту же ошибку. Я внимательно изучил пример, пытался его модифицировать и смотреть, как меняется ответ — и в итоге свёл его до минимального примера, ломающий мой алгоритм (для наглядности я обозначил воду точками и сушу решётками):

#..#
#.##
###.

Видите ли вы тут проблему? Я вот понял её благодаря своему отладочному выводу. Перерисуем этот пример, показав, какой номер территории приписывается каждой ячейке на очередном шаге:

0..1
0.21
000.

Во время обработки второй строки появляется территория с id = 2, которая сразу же становится частью территории с id = 1. После обработки второй строки связи между территориями выглядят следующим образом (стрелочкой показано отношение "является частью"):

[ 0 | 1 | 2 ]
      ^   |
      |   |
      \---/

С другой стороны, во время обработки третьей строки эта же территория становится частью территории с id = 0, и в итоге связи становятся такими:

[ 0 | 1 | 2 ]
  ^       |
  |       |
  \-------/

Здесь и кроется проблема: так как у территории с id = 1 нет никаких связей, она считается отдельным островом, а не частью острова, образованного территорией с id = 0. В итоге алгоритм ошибочно считает, что на карте два острова вместо одного. В принципе, тут примерно понятно, что нужно исправить: нужно менять не только связь у территории 2, но и у территории 1, на которую первая указывает...

...И тут я понял, что это как-то слишком походит по описанию на структуру непересекающихся множеств (disjoint sets aka union-find), про которую я когда-то читал в Википедии. В принципе, это структура данных напрашивалась с самого начала, но я рассчитывал, что смогу обойтись чем-то более простым. Ну что ж — делаю эту структуру (что, кстати, как ни странно, упростило код), фиксю пару мелких багов, отправляю на проверку — и — о чудо! — все тесты пройдены!

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

Depth first search.

Я уже говорил тебе, что такое безумие? Безумие — это раз за разом заходить на свой собственный канал, надеясь увидеть там новые посты

#prog #rust #meme

#prog #article #rust #cpp

C++ быстрее и безопаснее Rust, Yandex сделала замеры!

От создателя Go быстрее Rust, Mail.Ru Group сделала замеры

Комментарии, конечно, замечательные

Тем временем число комментариев перевалило за тысячу. Ух.

#prog #c #article

Как коротенькая программа выявила ошибки в трёх компиляторах C.

blog.regehr.org/archives/482

#article

How To Criticize Computer Scientists or Avoiding Ineffective Deprecation And Making Insults More Pointed

cs.purdue.edu/homes/dec/essay.criticize.html