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

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

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

Итак, на повестке сегодняшнего дня — моноиды и их основное применение для кеширования вычислений в деревьях.

Моноид как концепция

Представьте себе множество чего угодно, множество, состоящее из объектов, которыми мы собираемся манипулировать. Назовём его M. На этом множестве мы вводим бинарную операцию, то есть функцию, которая паре элементов множества ставит в соответствие новый элемент. Здесь и далее эту абстрактную операцию мы будем обозначать "⊗", и записывать выражения в инфиксной форме: если a и b — элементы множества, то c = a ⊗ b — тоже какой-то элемент этого множества.

Например, рассмотрим все строки, существующие на свете. И рассмотрим операцию конкатенации строк, традиционно обозначаемую в математике "◦", а в большинстве языков программирования "+": "John" ◦ "Doe" = "JohnDoe". Здесь множество M — строки, а "◦" выступает в качестве операции "⊗".
Или другой пример — функция fst, известная в функциональных языках при манипуляции с кортежами. Из двух своих аргументов она возвращает в качестве результата первый по порядку. Так, fst(5, 2) = 5; fst("foo", "bar") = "foo". Безразлично, на каком множестве рассматривать эту бинарную операцию, так что в вашей воле выбрать любое.

Далее мы на нашу операцию "⊗" накладываем ограничение ассоциативности. Это значит, что от неё требуется следующее: если с помощью "⊗" комбинируют последовательность объектов, то результат должен оставаться одинаковым вне зависимости от порядка применения "⊗". Более строго, для любых трёх объектов a, b и c должно иметь место:
(a ⊗ b) ⊗ c = a ⊗ (b ⊗ c)
Легко увидеть, что конкатенация строк ассоциативна: не важно, какое склеивание в последовательности строк выполнять раньше, а какое позже, в итоге все равно получится общая склейка всех строк в последовательности. То же касается и функции fst, ибо:
fst(fst(a, b), c) = a
fst(a, fst(b, c)) = a
Цепочка применений fst к последовательности в любом порядке всё равно выдаст её головной элемент.

И последнее, что мы потребуем: в множестве M по отношению к операции должен существовать нейтральный элемент, или единица операции. Это такой объект, который можно комбинировать с любым элементом множества, и это не изменит последний. Формально выражаясь, если e — нейтральный элемент, то для любого a из множества имеет место:
a ⊗ e = e ⊗ a = a
В примере со строками нейтральным элементом выступает пустая строка "": с какой стороны к какой строке её ни приклеивай, строка не поменяется. А вот fst в этом отношении нам устроит подлянку: нейтральный элемент для неё придумать невозможно. Ведь fst(e, a) = e всегда, и если a ≠ e, то свойство нейтральности мы теряем. Можно, конечно, рассмотреть fst на множестве из одного элемента, но кому такая скука нужна? :)

Каждую такую тройку <M, ⊗, e> мы и будем торжественно называть моноидом. Зафиксируем это знание в коде:

public interface IMonoid<T> {
    T Zero { get; }
    T Append(T a, T b);
}

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

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

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

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

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

Введение

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

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

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

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

Интро

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

В своих статьях я буду приводить примеры кода сразу на двух языках: на Java и на Haskell. Благодаря этому можно будет сравнить императивный и функциональный стили программирования и увидить плюсы и минусы того и другого.

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

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

Начну, пожалуй, с очевидного (слева от этого текста). Изображение, приведенное здесь, довольно известно. Оно показывает, что сотрудники Интел обычно носят на пальцах вместо колец процессоры Atom и рисовые зерна.
Оно демонстрирует размер процессора Intel Atom в сравнении с рисовым зерном. А я продемонстрирую вам буквально «на пальцах» простые и, надеюсь, полезные для программистов на С\С++ советы по оптимизации софта для Intel Atom.

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

Внимание! Предполагаются базовые знания утилиты GNU make.

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

Фильмы, сериалы, лекции

Это была кнопка ускорения. Оказалось, что при ускорении в 1.5, а то и в два раза фильм смотреть вполне возможно. И это несмотря на то, что в той, старой, версии VLC, кнопка увеличивала именно скорость, то есть заодно увеличивалась и высота всех звуков. В новых версиях VLC увеличивается темп, а не скорость, то есть искажение высоты звука не чувствуется: просто видео становится короче.
Кино с важным наполнением так смотреть трудно. В некоторых случаях (например, фильм Космическая одиссея 2001 года) просто кощунственно включать ускорение.
А вот большинство мыльных пузырей с большим удовольствием надуваются и лопаются в полтора-два раза быстрее. Преградами могут послужить лишь некачественная озвучка (закадровый перевод) и производительность вашего компьютера.
Остаётся нажать кнопку "+" на клавиатуре, когда VLC откроет файл, и почувствовать на своих ушах, что я описываю. Экспериментируйте! Какое ускорение выдержит ваш мозг? +)

UPD: В VLC можно изменять скорость более плавно, с шагом 0.1x. Для этого используйте клавиши "[" и "]".

Радиопостановки, аудиокниги, подкасты

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

Несколько недель назад мне для некого опыта потребовался источник постоянного напряжения 7V и силой тока в 5A. Тут-же отправился на поиски нужного БП в подсобку, но такого там не нашлось. Спустя пару минут я вспомнил о том, что под руки в подсобке попадался блок питания компьютера, а ведь это идеальный вариант! Пораскинув мозгами собрал в кучу идеи и уже через 10 минут процесс начался.

Продолжая свой предыдущий топик про ремувер от ЛК, как и обещал, расскажу про утилиту удаления продуктов от Dr.Web. В прошлый раз Лаборатория Касперского довольно быстро отреагировала и усложнила капчу, теперь от нее рябит в глазах, а желания писать алгоритм распознавания не возникает. Правда, перед тем как выложить версию с новой каптчей (build 157), они обновили старую, куда добавили удаление новейших продуктов линейки 2011 (build 155)…

Про ремувер от Dr.Web я собирался написать еще в сентябре, но т.к. была обнаружена довольно серьезная уязвимость в модуле самозащиты не только самой утилиты удаления, но и всей линейки антивирусов, пришлось дать время программистам из Dr.Web на ее исправление.

У тебя наверняка не раз возникала ситуация, когда программные логгеры клавы не могли решить поставленных задач. Например, отловить пароль от биоса с помощью программного кейлоггера, загружаемого системой, невозможно. Лично я столкнулся с подобной проблемой, когда мне нужно было узнать админский пароль в локальной сети одной фирмы. Тогда я и подумал, что было бы очень круто сделать «железный» логгер, который бы подключался между клавиатурой и компьютером и ловил все нажатые клавиши, начиная с включения компьютера. В предлагаемой статье изложены принципы работы PS/2 интерфейса, и перехват данных, передаваемых по нему.


Парочка аппаратных логгеров клавиатуры

Принципы

Для того чтобы сконструировать подобное устройство, сначала нужно разобраться с тем, как же работает клавиатура. Есть два основных типа клавиатур: АТ (старый стандарт) и PS/2. Отличаются они только разъемами: АТ имеет DIN, а PS/2 — miniDIN. Первый — большой круглый разъемчик с пятью штырьками, второй — маленький, как у мышки, с шестью пинами. По протоколу обмена они полностью совместимы. Наверняка, ты видел переходники с широких старых разъемов на новые маленькие. Этот стандарт появился еще в 1984 году вместе с первым персональным компьютером IBM PC и используется по сей день, практически не претерпев никаких изменений.

Российский хакер и криптограф Дмитрий Скляров из компании Elcomsoft стал знаменитым ещё после скандала с Adobe, который привёл к его аресту на хакерской конференции Defcon в 2001 году. После мощной общественной кампании Склярова выпустили в 2002 году, но он продолжает заниматься тем же благородным делом под девизом «информация должны быть свободной». То есть, продолжает взламывать различные криптографические алгоритмы.

Очередной жертвой Склярова стал алгоритм аутентификации подлинности фотографий Canon Original Data Security в цифровых камерах Canon. При помощи комплекта инструментов OSK-E3 (специальный софт и смарт-карта) можно было надёжно проверять оригинальность фотографий, считывая цифровую подпись Original Decision Data (ODD), которая записывалась в блок EXIF файлов JPG и содержала зашифрованную информацию о дате и координатах съёмки.

После Vogue истерии появилось множество вопросов, как подключить плату к компьютеру. И многие люди даже не понимают, что же такое UART. И я решил рассказать здесь какой это мощный инструмент.


Роутер превращается в компьютер, если к нему по UART подключить клавиатуру и дисплей

От телеграфа к COM-порту

Протокол UART (Universal asynchronous receiver/transmitter) или, по-русски, УАПП (универсальный асинхронный приемопередатчик) — старейший и самый распространенный на сегодняшний день физический протокол передачи данных. Наиболее известен из семейства UART протокол RS-232 (в народе – COM-порт, тот самый который стоит у тебя в компе). Это, наверное, самый древний компьютерный интерфейс. Он дожил до наших дней и не потерял своей актуальности.

Надо сказать, что изначально интерфейс УАПП появился в США как средство для передачи телеграфных сообщений, и рабочих бит там было пять (как в азбуке Морзе). Для передачи использовались механические устройства. Потом появились компьютеры, и коды ASCII, которые потребовали семь бит. В начале 60-х на смену пришла всем известная 8-битная таблица ASCII, и тогда формат передачи стал занимать полноценный байт, плюс управляющие три бита.

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

В этой заметке я опишу методы увеличения производительности линуксового маршрутизатора. Для меня эта тема стала актуальна, когда проходящий сетевой трафик через один линуксовый маршрутизатор стал достаточно высоким (>150 Мбит/с, > 50 Kpps). Маршрутизатор помимо роутинга еще занимается шейпированием и выступает в качестве файрволла.

Преимущества дивной вёрстки, семантичной разметки и разделения содержимого и дизайна описаны десятки, сотни раз, но все-равно находятся люди, которые не понимают самой идеи html и css, пишут в коде такие ужасные вещи, как

<span style="color:blue">

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

<font color="blue">

, наивно веря в этом деле валидатору. А ведь правильный подход в написании html и css лежит на поверхности. Достаточно просто посмотреть историю развития этого языка, почитать статьи десятилетней давности и проанализировать. Я, при поддержке theshock, постаралась в этот статье упорядоченно и коротко изложить наше видение этого вопроса.

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

В этом выпуске серии «5 вещей …», я представлю некоторые из тонких аспектов многопоточного программирования, в том числе synchronized-методы, volatile переменные и атомарные классы. Речь пойдет в особенности о том, как некоторые из этих конструкций взаимодействуют с JVM и Java-компилятором, и как различные взаимодействия могут повлиять на производительность приложений.

Дорогие хабражители и хабрагости, хочу поделиться с вами своим новым увлечением — 3D-фотографией.
Нет, я не являюсь владельцем 3D-говномыльницы, у меня обычная зеркалка от Sony и далее в этой статье я расскажу о том, как сделать вот такую анаглифную фотографию без специальной техники и за 5 минут времени:

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

Рано или поздно все сталкиваются с проблемами связанными с языковым и культурным разнообразием при написании программ. Я был сильно удивлен узнав, что часть моих знакомых, пишущих на C++, решают эти проблемы своими велосипедами. Для тех, кто еще не знает что такое std::locale я хотел бы кратко на примере показать как c ним работать и что бывает, если о нем забыть…