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

Уже тысячи и тысячи мужчин и женщин по всему миру используют этот современный подход, который гарантирует потрясающие выигрыши в производительности и эффективности по сравнению с устаревшими методиками, такими, как Scrum, Agile, Kanban.

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

Итак, встречайте — Porozhnyak!

Думаю многим известна ситуация, когда собственный изобретенный велосипед нигде потом не используется. Поэтому я долго не решался опубликовать эту разработку, пока не обратил внимание, что таскаю его из проекта в проект. И так, одним из неотъемлемых элементов современной разработки являются так называемые таск раннеры – это Grunt/Gulp для nodejs, Rake для Ruby, Make для C/C++ и т.п. А для главного инструмента разработчика – консоли – ничего подобного нет. Точнее есть, но, как это обычно бывает, не совсем то. В результате изысканий, на свет появился инструмент Bake – таскраннер написанный на bash с поддержкой модульной структуры.

Основные особенности:

• Таски в виде функции.
• Поддержка аргументов.
• Модули.

Несколько месяцев назад мы запустили серию интервью Oh, My Code на канале Технострим. Пришло время нового выпуска. На этот раз мы расскажем о том, как сделано Облако Mail.Ru, почему Perl не умер и что такое хороший программист.

Ведущий программы — технический директор медиапроектов Павел Щербинин, гость — архитектор Облака Mail.Ru Владимир Перепелица. Ниже перечислены ключевые вопросы, ответы на которые вы найдете в очередном выпуске Oh, My Code:

• Умер ли Perl?
• Как написать крутое резюме?
• Каких программистов берут в Облако?
• Как пройти собеседование, чтобы получать 200 000 рублей?
• Зачем становиться техническим директором и снова уходить в разработку?

Зачем разработчикам изучать Spark? Как освоить технологию в домашних условиях? Что умеет, а чего не умеет Spark и что ждет его в будущем? Об этом – в интервью с тренером по Java и Big Data в ЕРАМ Алексеем Зиновьевым.

Леность ли моя тому причиной или болезненная неприязнь к комбайнам, но у меня как-то не сложились отношения с большими толстыми довольными IDE. Довольствуюсь простым ламповым Geany и несколькими самописными скриптами, количество коих растёт по мере необходимости.

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

О некоторых таких скриптах решил попробовать писать сюда. Может, кому пригодятся (да и заточить под себя какой-нибудь из них всегда можно). Если нет — ругайтесь в комментариях, учту. Итак.

Всем счастья и добра!

Эволюционно так получилось, что в моем личном владении оказался не маленький зоопарк различных серверов: от дешевого Supermicro до топового (на момент выпуска) HP Gen 8. Все конечно связано оптикой и прочими радостями жизни.

Но сказ не про то, как сеть класть, и даже не про то, как сервера настраивать, а про то, как правильно просто на всем этом деле docker-compose сервисы поднимать и радоваться.

Shinken

Согласно официальному сайту, Shinken — фреймворк мониторинга; переписанный с нуля на питоне Nagios Core, с улучшенной поддержкой больших окружений и более гибкий.

Масштабируемость

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

Двое отважных разработчиков Ивэн Грин и Крис Стивенс решились на смелый шаг. Они написали с нуля совершенно новую операционную систему Minoca OS и опубликовали её исходный код под свободной лицензией GNU GPL v3.

Это 625 000 строк отлично документированного кода, преимущественно на языке программирования Си, частично на C++ и Ассемблере. Ядро ОС для x86 имеет размер около 750 КБ. С драйверами, сетевым стеком и видеобуфером свежезагруженная система использует 5−7 МБ оперативной памяти.

Иллюстрация @alvaro_sanchez

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

Естественно, в реальности все оказалось совсем наоборот. Когда смотришь назад, на произошедшее, то зрение оказывается ближе к 100%, чем когда смотришь с надеждой в будущее.

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

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

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Декартово дерево (cartesian tree, treap) — красивая и легко реализующаяся структура данных, которая с минимальными усилиями позволит вам производить многие скоростные операции над массивами ваших данных. Что характерно, на Хабрахабре единственное его упоминание я нашел в обзорном посте многоуважаемого winger, но тогда продолжение тому циклу так и не последовало. Обидно, кстати.

Я постараюсь покрыть все, что мне известно по теме — несмотря на то, что известно мне сравнительно не так уж много, материала вполне хватит поста на два, а то и на три. Все алгоритмы иллюстрируются исходниками на C# (а так как я любитель функционального программирования, то где-нибудь в послесловии речь зайдет и о F# — но это читать не обязательно :). Итак, приступим.

Введение

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

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

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

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

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

Привет. Ей! Не говорите “Да блин! Я знаю, чем отличается список от вектора, мне не нужна эта статья”. Прошу, загляните под кат и освежите свои знания. Я надеюсь, однако, что вы сможете почерпнуть из этой статьи намного больше и, некоторые, возможно, наконец-то разберутся, почему существует так много типов данных для коллекций объектов.

Пару недель назад, необходимо было освежить информацию в голове информацию по структурам данных и алгоритмам для собеседования. Первым делом полез на www.coursera.org, где хотел пробежаться по некоторым лекциям курса Алгоритмы, там же были две сводные таблички, которые в процессе изучения курса взял на заметку — отлично помогали запомнить сложность операций. Но, к моему удивлению, материалы пройденного курса стали недоступны. Быстрое гугление, в надежде, что кто-нибудь выложил лекции на торрентах, к сожалению, не дало результатов. В итоге, я нашел полную коллекцию слайдов по данному курсу. Спешу поделиться. Самое главное, что взял из этих слайдов, — это вышеупомянутые сводные таблички. Думаю многим пригодится.

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

Вопрос: Почему поиск в python dict на больших объемах данных быстрее чем итерация по индексированному массиву?

Ответ: В dict хранятся хэши от ключей. Каждый раз, когда мы ищем в dict значение по ключу, мы сначала вычисляем его хэш, а потом (внезапно), выполняем бинарный поиск. Таким образом, сложность составляет O(lg(N))!

На самом деле никакого бинарного поиска тут нет. И сложность алгоритма не O(lg(N)), а Amort. O(1) — так как в основе dict питона лежит структура под названием Hash Table.

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

Решил немного описать на мой взгляд самую полезную древовидную структуру. AVL дерево это бинарное дерево (у каждой вершины не более 2 сыновей), в котором каждой вершине присвоен идентификатор (как раз его и хранит дерево), идентификаторы подчиняются следующему правилу: ID левого сына<ID родителя<ID правого сына.
Т.е. если обходить дерево рекурсивно слева направо получим отсортированный по возрастанию список ID, справа налево – по убыванию.
Причем дерево максимально сбалансировано: высота левого поддерева отличается от высоты правого максимум на 1.

Интересно в нем то, что тогда на проверку существования элемента в дереве уходит log(N) N – количество ID. Ведь надо пройти от корня вниз, а поскольку дерево максимально симметрично то его высота — log(N)+1
Хорошая новость – нам никто не запрещает прикрепить к вершине еще какие-то полезные данные и тогда выборка произвольных данных по ID будет занимать log(N) времени
Плохая новость – одинаковые ID как следует из определения в нем существовать не могут. Придется делать финт ушами, один способ сделать вместо каждой вершины список вершин с одинаковым ID, другой – изменить алгоритм балансировки.

Введение

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

Основные операции в деревьях выполняются за время пропорциональное его высоте. Сбалансированные деревья минимизируют свою высоту (к примеру, высота бинарного сбалансированного дерева с n узлами равна log n). Большинство знакомо с такими сбалансированными деревьями, как «красно-черное дерево», «AVL-дерево», «Декартово дерево», поэтому не будем углубляться.

В чем же проблема этих стандартных деревьев поиска? Рассмотрим огромную базу данных, представленную в виде одного из упомянутых деревьев. Очевидно, что мы не можем хранить всё это дерево в оперативной памяти => в ней храним лишь часть информации, остальное же хранится на стороннем носителе (допустим, на жестком диске, скорость доступа к которому гораздо медленнее). Такие деревья как красно-черное или Декартово будут требовать от нас log n обращений к стороннему носителю. При больших n это очень много. Как раз эту проблему и призваны решить B-деревья!

B-деревья также представляют собой сбалансированные деревья, поэтому время выполнения стандартных операций в них пропорционально высоте. Но, в отличие от остальных деревьев, они созданы специально для эффективной работы с дисковой памятью (в предыдущем примере – сторонним носителем), а точнее — они минимизируют обращения типа ввода-вывода.

Двоичная куча (binary heap) – просто реализуемая структура данных, позволяющая быстро (за логарифмическое время) добавлять элементы и извлекать элемент с максимальным приоритетом (например, максимальный по значению).

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

Введение

Двоичная куча представляет собой полное бинарное дерево, для которого выполняется основное свойство кучи: приоритет каждой вершины больше приоритетов её потомков. В простейшем случае приоритет каждой вершины можно считать равным её значению. В таком случае структура называется max-heap, поскольку корень поддерева является максимумом из значений элементов поддерева. В этой статье для простоты используется именно такое представление. Напомню также, что дерево называется полным бинарным, если у каждой вершины есть не более двух потомков, а заполнение уровней вершин идет сверху вниз (в пределах одного уровня – слева направо).

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы покажутся чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он будет полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Введение

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

Тем не менее, знание теории тоже имеет свои преимущества и может оказаться весьма полезным. В этой статье, предназначенной для программистов, которые являются хорошими практиками, но имеют слабое представление о теории, я представлю один из наиболее прагматичных программистских инструментов: нотацию «большое О» и анализ сложности алгоритмов. Как человек, который работал как в области академической науки, так и над созданием коммерческого ПО, я считаю эти инструменты по-настоящему полезными на практике. Надеюсь, что после прочтения этой статьи вы сможете применить их к собственному коду, чтобы сделать его ещё лучше. Также этот пост принесёт с собой понимание таких общих терминов, используемых теоретиками информатики, как «большое О», «асимптотическое поведение», «анализ наиболее неблагоприятного случая» и т.п.

Первая статья цикла

Интро

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