Если в одном из моих прошлых постов речь шла о довольно современном подходе к построению сбалансированных деревьев поиска, то этот пост посвящен реализации АВЛ-деревьев — наверное, самого первого вида сбалансированных двоичных деревьев поиска, придуманных еще в 1962 году нашими (тогда советскими) учеными Адельсон-Вельским и Ландисом. В сети можно найти много реализаций АВЛ-деревьев (например, тут), но все, что лично я видел, не внушает особенного оптимизма, особенно, если пытаешься разобраться во всем с нуля. Везде утверждается, что АВЛ-деревья проще красно-черных деревьев, но глядя на прилагаемый к этому код, начинаешь сомневаться в данном утверждении. Собственно, желание объяснить на пальцах, как устроены АВЛ-деревья, и послужило мотивацией к написанию данного поста. Изложение иллюстрируется кодом на С++.

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

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


Рис. 1 Бинарное дерево

Привет, хабр!



Меня зовут Глеб, я долгое время работаю в ритейловой аналитике и сейчас занимаюсь применением машинного обучения в данной области. Не так давно я познакомился с ребятами из MLClass.ru, которые за очень короткий срок довольно сильно прокачали меня в области Data Science. Благодаря им, буквально за месяц я стал активно сабмитить на kaggle. Поэтому данная серия публикаций будет описывать мой опыт изучения Data Science: все ошибки, которые были допущены, а также ценные советы, которые мне передали ребята. Сегодня я расскажу об опыте участия в соревновании The Analytics Edge (Spring 2015). Это моя первая статья — не судите строго.

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

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

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

В данной статье я хочу поделиться библиотеками, позволяющими упростить работу c wkhtmltopdf в Node.JS.

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

Оглавление

1. Введение (vim_lib)
2. Менеджер плагинов без фатальных недостатков (vim_lib, vim_plugmanager)
3. Уровень проекта и файловая система (vim_prj, nerdtree)
4. Snippets и шаблоны файлов (UltiSnips, vim_template)
5. Компиляция и выполнение чего угодно (vim-quickrun)
6. Работа с Git (vim_git)
7. Деплой (vim_deploy)
8. Тестирование с помощью xUnit (vim_unittest)
9. Библиотека, на которой все держится (vim_lib)
10. Другие полезные плагины

Мне нравится, когда клиент может сразу увидеть результаты моих трудов. Я могу корректировать развитие проекта согласно желаниям заказчика, что сильно спасает от недопонимания. Думаю и клиенты не против быть в курсе, куда уходит бюджет и на каком этапе их проект. Добиться этого достаточно просто, благо есть даже целая методология, называемая «Непрерывной интерграцией», позволяющая в кратчайшие сроки деплоить мелкие изменения, но как сделать, чтобы это было достаточно удобно для программиста? Ведь никому не хочется писать код, а после переключаться в контекст системы деплоя или даже использовать ssh соединение чтобы развернуть мелкие изменения на продакшене (или на dev сервере).

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

Qucs — это симулятор электронных схем с открытым кодом. О нём рассказывают мои предыдущие статьи на хабре.

Сейчас наш проект готовится к следующему релизу 0.0.19, который выйдет в ближайшие недели. Данная заметка содержит обзор наиболее ожидаемого за все последние годы нововведения: поддержки моделирования схем Qucs в SPICE-совместимых симуляторов.

Qucs использует ядро моделирования Qucsator, разработанное с нуля. Это ядро имеет много преимуществ (моделирование S-параметров, расширенный постпроцесоор), но также имеет многочисленные баги, связанные с моделированием во временной области (Transient analysis). Эти баги в частности не позволяют моделировать в Qucs силовую электронику. Теперь в Qucs можно смоделировать, например такую схему:



Скачать пакеты для Linux и Windows с поддержкой Ngspice можно здесь:
github.com/ra3xdh/qucs/releases/tag/0.0.19S-rc1

UPD от 21.10.15: сейчас доступен RC3: github.com/ra3xdh/qucs/releases/tag/0.0.19S-rc3

Буква «S» в номере релиза означает SPICE. По-видимому вместе с релизом 0.0.19 выйдет два набора пакетов: с индексом «S» и с обычной нумерацией, так как дальнейшая судьба spice4qucs неясна.

Документация для spice4qucs находится здесь: qucs-help.readthedocs.org/en/spice4qucs

Под катом будет кратко рассмотрено использование spice4qucs.

Cтэнфордский курс CS183B: How to start a startup. Стартовал в 2012 году под руководством Питера Тиля. Осенью 2014 года прошла новая серия лекций ведущих предпринимателей и экспертов Y Combinator:

Содержание

1. Что такое тензор и для чего он нужен?
2. Векторные и тензорные операции. Ранги тензоров
3. Криволинейные координаты
4. Динамика точки в тензорном изложении
5. Действия над тензорами и некоторые другие теоретические вопросы
6. Кинематика свободного твердого тела. Природа угловой скорости
7. Конечный поворот твердого тела. Свойства тензора поворота и способ его вычисления
8. О свертках тензора Леви-Чивиты
9. Вывод тензора угловой скорости через параметры конечного поворота. Применяем голову и Maxima
10. Получаем вектор угловой скорости. Работаем над недочетами
11. Ускорение точки тела при свободном движении. Угловое ускорение твердого тела
12. Параметры Родрига-Гамильтона в кинематике твердого тела
13. СКА Maxima в задачах преобразования тензорных выражений. Угловые скорость и ускорения в параметрах Родрига-Гамильтона
14. Нестандартное введение в динамику твердого тела
15. Движение несвободного твердого тела
16. Свойства тензора инерции твердого тела
17. Зарисовка о гайке Джанибекова
18. Математическое моделирование эффекта Джанибекова

Введение

Это было очень давно, когда я учился классе в десятом. Среди довольно скудного в научном плане фонда районной библиотеки мне попалась книга — Угаров В. А. «Специальная теория относительности». Эта тема интересовала меня в то время, но информации школьных учебников и справочников было явно недостаточно.

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

Привет, Хабр!
Большинство разработчиков знает, что такое Nested Sets, их сильные и слабые стороны. Сегодня я хочу представить на суд общественности реализацию модификации этой методики, которая частично решает недостатки оригинального алгоритма, правда имеет и свои отрицательные стороны.

Господа! Я рад сообщить, что наконец-то все желающие могут загрузить бесплатный учебник на более чем 1600 страниц, над переводом которого работало более полусотни человек из ведущих университетов, институтов и компаний России, Украины, США и Великобритании. Это был реально народный проект и пример международной кооперации.

Учебник Дэвида Харриса и Сары Харрис «Цифровая схемотехника и архитектура компьютера», второе издание, 2012, сводит вместе миры программного обеспечения и аппаратуры, являясь одновременно введением и в разработку микросхем, и в низкоуровневое программирование для студентов младших курсов. Этот учебник превосходит более ранний вводный учебник «Архитектура компьютера и проектирование компьютерных систем» от Дэвида Паттерсона и Джона Хеннесси, причем соавтор предыдущего учебника Дэвид Паттерсон сам рекомендовал учебник от Харрисов как более продвинутый. Следуя новому учебнику, студенты строят реализацию подмножества архитектуры MIPS, используя платы с ПЛИС / FPGA, после чего сравнивают эту реализацию с индустриальными микроконтроллерами Microchip PIC32. Таким образом вводится вместе схемотехника, языки описания аппаратуры Verilog и VHDL, архитектура компьютера, микроархитектура (организация процессорного конвейера) и программирование на ассемблере — в общем все, что находится между физикой и высокоуровневым программированием.

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

Сегодня мы публикуем седьмую лекцию из курса «Анализ изображений и видео», прочитанного Натальей Васильевой в петербургском Computer Science Center, который создан по совместной инициативе Школы анализа данных Яндекса, JetBrains и CS-клуба.



Всего в программе девять лекций, из которых уже были опубликованы:

1. Введение в курс «Анализ изображений и видео»;
2. Основы пространственной и частотной обработки изображений;
3. Морфологическая обработка изображений;
4. Построение признаков и сравнение изображений: глобальные признаки;
5. Построение признаков и сравнение изображений: локальные признаки;
6. Поиск по подобию. Поиск нечетких дубликатов.

Под катом вы найдете план новой лекции и слайды.

Введение

В предыдущей статье мы изучили, как создать тему для WordPress. Давайте сегодня на основе этого же шаблона Corporate Blue попробуем создать сайт на второй по популярности CMS – Joomla! Поскольку в статье описывается в основном вёрстка, будем считать, что Joomla! у вас уже установлена. Если вы не знаете, как установить Joomla!, то инструкцию можно найти здесь. В данном руководстве мы не будем подробно описывать CSS стили и HTML код – это было сделано в самой первой статье. Вместо этого рассмотрим детально особенности создания шаблона именно для Joomla!

Интернет на волне всеобщей прослушки и связанной с этим паранойи постепенно переходит на тотальный SSL. К сожалению, пока это сделать не очень просто и обычно не бесплатно. Из бесплатных сервисов годные сертификаты, поддерживаемые всеми браузерами, предоставляет сервис StartSSL. В середине 2015 года при поддержке Mozilla, Cisco и других уважаемых организаций будет организована раздача бесплатных сертификатов в автоматическом режиме.

Magento Enterprise: Что такое Full Page Cache и почему он нужен.

Для тех, кто знаком с Magento, не секрет, что этот e-commerce движок довольно требователен к железу. Но разработчики этого интернет-магазина попытались решить эту проблему и придумали много различного рода «ускорялок», без которых, пожалуй, запускать магазин на движке Magento в продакшн не стоит. Слишком долго Magento будет отдавать конечному пользователю страницу. Среди таких «ускорялок» кеши, индексы, компиляция, объединение JS/CSS в один сжатый файл и др.

Одной из основных «фишек» Magento Enterprise является Full Page Cache (далее FPC). Эту «фишку» реализует модуль Enterprise_PageCache, входящий в состав пакета Magento Enterprise.

В статье рассматривается самая свежая на момент написания статьи версия Magento Enterprise: 1.13.1.

FPC позволяет отдавать серверу страницу за считанные миллисекунды, практически не нагружая сервер. Я провел замеры времени отдачи страницы продукта сервером (в одном из проектов, над которым работал), вот результаты:

• 65 ms при включенном FPC (когда все блоки были закешированы);
• 1250 ms при выключенном FPC (при этом все остальные виды кеша включены);
• 2500 ms при отключенном кеше всех видов.

Почему разница настолько велика? Давайте разберёмся.

Данная статья продемонстрирует возможность легко написать свою нейронную сеть на языке Javа. Дабы не изобретать велосипед, возьмем уже хорошо проработанную библиотеку Fast Artificial Neural Network. Использование нейронных сетей в своих Java-проектах — реально. Часто можно услышать упреки в адрес Java касательно скорости выполнения. Хотя разница не так велика — подробно об этом можно узнать в публикации «Производительность C++ vs. Java vs. PHP vs. Python. Тест «в лоб»». Мы будем использовать обертку вокруг библиотеки FANN.

На днях Даниэль Штенберг, один из участников группы HTTPbis IETF, которая ведёт разработку протокола http2, опубликовал в своём блоге крайне интересный документ «http2 explained». Небольшой PDF-документ на 26 страницах весьма доступным языком рассказывает о предпосылках и деталях реализации протокола http2.

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

Привет, %username%! Итак, продолжим написание нашего бота. Сегодня мы внедрим наш код в игровой процесс (не без помощи ассемблера), а позже позаботимся и о том, что бы его было не так просто найти, ведь наказывают не за то что жульничаешь, а за то что попался. И если быть до конца честным то даже не совсем в сам процесс игры будем его внедрять, да и 1 раз только за весь жизненный цикл.

Но обо всем по порядку, так что жду Вас под катом!

Здравствуйте, уважаемые читатели Хабра.

После долгого перерыва с вами опять я и мы продолжаем копаться во внутренностях UEFI. На этот раз я решил показать несколько техник, которые позволяют упростить реверс и отладку исполняемых компонентов UEFI на примере устаревшего-но-все-еще-популярного PEI-модуля SecureUpdating, который призван защищать прошивку некоторых ноутбуков HP от модификации.

Предыстория такова: однажды вечером мне написал знакомый ремонтник ноутбуков из Беларуси и попросил посмотреть, почему ноутбук с замененным VideoBIOS'ом не хочет стартовать, хотя такой же точно рядом успешно стартует. Ответ оказался на поверхности — не стартующий после модификации ноутбук имел более новую версию UEFI, в которую добрые люди из HP интегрировали защиту от модификации DXE-тома (а там и находится нужный нам VideoBIOS вместе с 80% кода UEFI), чтобы злобные вирусы и не менее злобные пользователи ничего там не сломали ненароком. Тогда проблема решилась переносом PEI-модуля SecureUpdating из старой версии UEFI в новую, но через две недели тот же человек обратился вновь, на этот раз на похожем ноутбуке старая версия модуля работать отказалась, и моя помощь понадобилась вновь.
Если вас заинтересовали мои дальнейшие приключения в мире UEFI PEI-модулей с дизассемблером и пропатченными переходами — добро пожаловать под кат.