Первая статья из цикла «Теория магии» носит обзорный характер. Ее цель — сформулировать основные вопросы рассматриваемой дисциплины преимущественно на качественном уровне, а так же разъяснить, какие принято выделять субдисциплины, и как аспекты, находящиеся в центре их внимания, связаны между собой.

«Как автоматизировать сочинение музыки?» — этот вопрос тревожит умы музыкантов еще со времен средневековья. Кеплер превращал траектории движения планет в музыку; Моцарт и его современники изобрели игру в «музыкальные кости» — они броском кубиков выбирали из большой таблицы такты и составляли из них менуэты. Но только с появлением компьютеров алгоритмическая генерация музыки получила настоящее развитие. Теория вероятности, марковские цепи, искусственные нейронные сети — все это стало инструментами создания музыки.

Моему сыну, как и многим мальчишкам, нравятся автомобили. Причём чем они больше и необычнее — тем больше нравятся. Когда мы идём по улице, а мимо проезжает эвакуатор или снегоуборочная машина, он неизменно дёргает меня за руку, указывает на заинтересовавший его объект и говорит: «Папа, б-р-р!». Говорит он так потому, что ему один год и вышеуказанные два слова составляют 40% его словарного запаса. Тем ни менее, в общем мысль понятна — обратить внимание на автомобиль. Давайте подумаем, каким образом ребёнок в возрасте 8-10 лет сказал бы своему сверстнику то же самое. Что-то вроде «Ух ты, смотри какая крутая тачка!», да? Мысль та же, но обратите внимание — уже шесть слов вместо двух. И, наконец, представьте, каким образом то же самое скажет человек лет в тридцать: «Эй, смотри, да это же Ferrari California 2008-го года выпуска с двигателем V8 мощностью в 454 лошадиных силы и 7-ми скоростной коробкой-автоматом! Она до сотни разгоняется за 3.9 секунды!». Да, здесь уже больше деталей, но, если вы не автомеханик или фанат Ferrari — они вам скорее всего не нужны и не важны. Основная же мысль — всё та же, что и в «Ух ты, смотри какая крутая тачка!» или «Папа, б-р-р!». Но выражена она уже в 30 слов.

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

В продолжении статьи о кроссплатформенной и кросс-аппаратной оптимизации, на примере задачи поиска полным проходом по таблице из 5 полей и 10 000 000 строк, и неизбежности этой задачи даже при индексном поиске, я покажу как ускорить такой поиск в 3.5-5.3 раза с использованием C++ независимо от аппаратной платформы.
В предыдущей статье нам удалось ускорить поиск в 1.3 раза: GitHub.com
Мы не будем банально описывать конструкции языка, а покажем преимущества C++ при решении одного из этапов реальной задачи.
Мы по-прежнему пишем кроссплатформенно под MSVC11(MSVS2012) и GCC 4.7.2, и используем в них C и частично реализованный стандарт C++11.
Для упрощения понимания мы все ещё пишем без индексного поиска, но это решение в дальнейшем будет использоваться при индексном поиске.

Существует мнение, что C++ имеет заметные накладные расходы по сравнению с C и поэтому он медленнее. Помимо этого, даже, существуют статьи показывающие преимущества в скорости языков с компиляцией налету (JIT — Just-in-time compilation), таких как Java и C#. Сравнить последние мы оставим тем, кто считает их быстрыми, но мы объясним почему это не так. А C и C++ мы сравним на примере задачи поиска данных.
Задача поиска данных часто встречается в: веб-сервисах, системах управления баз данных (СУБД), гео-поиске и аналитике.
Сначала для простоты объяснения поставим задачу поиска элементов полным проходом по массиву из 10 000 000 элементов (структур), содержащих 5 полей с диапазонами значений: amount_of_money(0-1000000), gender(0-1), age(0-100), code(0-1000000), height(0-300). А в следующих статьях добавим в решение индексный поиск.
Мы будем писать кроссплатформенно под MSVC11(MSVS2012) и GCC 4.7.2, и использовать в них частично реализованный стандарт C++11.

Эта статья рассказывает о том, как я, внезапно для себя, перешел с уровня простого пользователя GNU/Linux на уровень контрибьютора в мир open source. Надеюсь что она сможет послужить еще кому-то примером для собственного роста.

Начало

Все началось с того, что я, как всегда, перешел на новый релиз Ubuntu, на этот раз на 13.04. У меня оказалась не самая удачная материнка для линуксоида, так как в дистрибутивах из коробки редко есть дрова для ее сетевой карты (RLT8168E). Но ведь это не большая беда, верно? Раздобыв сопутствующие для компилирования пакеты, скачал с офф сайта последние дрова на Linux. Я уже делал так с Ubuntu 12.10 и ничто не предвещало подвоха.

Подвох

Внезапно эти «дрова» не компилируются. Немного повтыкая в текст ошибок, я пошел просить совета на linux@conference.jabber.ru. Там мне рассказали, что брать дрова с сайта — не всегда хорошая идея и что для моей сетевой карты в репозитории есть пакет. Приятный сюрприз. И действительно, стоило начать с поиска пакета с дровами в репозитории. Но, как оказалось, в нем код того же модуля и при компиляции он точно так же падает.

День добрый, уважаемые хабражители.
Писать игры хотел ещё с того момента, когда только начал программировать. И вот, решил всё-таки попробовать себя в написании игр на Android.
Игру осенью сделал ещё и выложил в маркет. Правда её удалили, так как права на Bomberman'а у Konami. Но статья, естественно, не об этом.

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

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

Я постараюсь донести основные идеи, показать как эта VCS помогает разрабатывать проект. Надеюсь, что после прочтения вы сможете ответить на вопросы:

• можно ли git «подстроить» под тот процесс разработки, который мне нужен?
• будет ли менеджер и заказчик удовлетворён этим процессом?
• будет ли легко работать разработчикам?
• смогут ли новички быстро включиться в процесс?
• можно ли процесс относительно легко и быстро изменить?

Конечно, я попытаюсь рассказать обо всём по-порядку, начиная с основ. Поэтому, эта статья будет крайне полезна тем, кто только начинает или хочет разобраться с git. Более опытные читатели, возможно, найдут для себя что-то новое, укажут на ошибки или поделятся советом.

Эпоха путешествий во времени еще не наступила, а человечество уже давно пытается разрешить сопутствующие им парадоксы. Мы поговорим о самом очевидном из них: что же все-таки произойдет при вмешательстве в ход истории? Существует несколько вариантов того, как поток времени реагирует на действия путешественника из будущего. Эти модели можно увидеть в фантастических фильмах, о них все больше начинают говорить ученые, но какая модель ближе к истине — единого мнения пока нет. Мы только начинаем проникать в тайны времени, и еще не обладаем возможностью экспериментировать с перемещениями в прошлое. Что же можно прояснить в данном вопросе уже сейчас? Под катом нас ждет экскурсия по основам механики времени, мы порассуждаем о парадоксах, и проведем небольшой эксперимент. Да, это будет испытание виртуальной машины времени, построенной на основе алгоритма «Жизнь»!

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

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

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

Данный пост будет более продвинутой версией.

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

Если у Вас есть mp3-файлы с тегами в windows-1251 кодировке, то Amarok в своей базе данных такие файлы показывает криво.

Этот пост — для тех, кто ранее использовал Rus-Xmms
проект для быстрого и удобного избавления от головной боли, связанной с кодировкой mp3-тегов и получил ее снова с выходом KDE4 и
нового Amarok.

Этот пост — также для тех, кто не совсем понимает, как в Linux можно корректно и рекурсивно перекодировать теги у
множества mp3 файлов в юникод и версию ID3v2.4.

Постараюсь преподнести это максимально лаконично, поэтому не буду описывать установку программы в [здесь подставить
название Вашего любимого дистрибутива].

Рецепт приготовления прост и находится под катом.

Сегодня в журнале Science публикована научная работа (pdf) с описанием нового метода автоматической реконструкции изображений из мозга человека. Авторы научной работы считают, что их метод более точный, чем предыдущие работы в этой области: хорошо распознаются символы алфавита и простые контрастные фигуры.

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

Undistract-Me — простая, но чрезвычайно полезная в хозяйстве утилита, которая делает одну вещь — выводит уведомление, когда длинная команда (по умолчанию 10 секунд, но можно настроить) завершила свое исполнение.



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

В данной статье речь пойдет о принципах вычисления баланса в нашей игре жанра Tower Defense (TD), которую мы выпустили летом 2012г. для платформ iOS и Android. Мы расскажем, c какими сложностями и ограничениями пришлось столкнуться, каков был ход мыслей геймдизайнера при выборе того или иного решения, и как был получен конечный результат.

Достижения игры
1. побывала в топ6 и топ7 в категориях US Appstore;
2. занимала топ1 категорий и топ7 overall в RU Appstore;
3. «письмо счастья» от Apple;
4. 425 000 закачек;
5. 5 звезд (средняя оценка для всех магазинов);
6. множество положительных комментариев;
7. обзоры на ведущих мировых мобильных порталах.

В этом топике я постараюсь рассказать о работе с API вконтакте из расширения для Google Chrome.

По сути, самая сложная часть это получение токена для доступа к API вконтакте, но обо всём по порядку. Для пущей наглядности я приведу пример минимально полезного расширения (что бы оно хоть что-то полезное делало, а вообще оно было сделано для удобного рехостинга гифок). И так расширение будет простое, но рабочее.

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

Описание задачи

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

Бор для произвольного набора строк строится за O (суммы длин этих строк). Очевидно, что сумма длин всех суффиксов строки пропорциональна квадрату длины самой строки. Таким образом, построение суффиксного дерева тривиальным алгоритмом работает за O(N²). И тут возникает резонный вопрос, можно ли построить суффиксное дерево быстрее?

На самом деле можно.

На хабре много статей посвященных редактору Sublime Text 2. Обычно они рождают за собой множество комментариев, где сторонники ST2 и всевозможных других редакторов (а также полноценных IDE) предаются веселому процессу «достоинствометрии».
Однако, среди комментариев мне лично ни разу не встречалось упоминаний о плагине SublimeClang, который кардинально меняет работу C++ программиста в этом редакторе. Поиск по хабру выдал всего 4 упоминания плагина в комментариях.
Не знаю, чем вызвано такое игнорирование. Хорошие вещи не обсуждаются? ST2 не используют C и С++ разработчики? Своей статьей я хочу исправить ситуацию. Я расскажу о некоторых, возможно не очевидных, особенностях установки и настройки, а также поделюсь парой собственных приемов и скриптов.

О плагине

Итак, плагин обеспечивает автодополнение кода и проверку ошибок прямо по ходу написания программы. Для файлов C/C++/ObjC/ObjC++ плагин заменяет стандартное автодополнение редактора на свое собственное. Для этого, плагин в фоне прогоняет исходник через компилятор clang, который формирует AST. Полученную информацию плагин использует для интеллектуальных подсказок автодополнения.
Ближайший аналог, который я могу подобрать — это функция IntelliSense в MS Visual Studio.
Использование информации из первых рук — от компилятора — позволяет плагину правильно узнавать, какие переменные, функции, типы и т.п. доступны в данной конкретной точки программы. Так же, в какой-то мере работают Go to definition (alt + d, alt + d) и Go to implementation (alt + d, alt + i). Список остальных горячих клавиш доступен на странице проекта.

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

Sublime Text 2 — это платный текстовый редактор, написанный на C++, который:

• Работает в Linux, OS X и Windows
• Обладает приличной скоростью работы
• Приятным интерфейсом (включая всевозможные анимации)
• Гибко настраиваем (правда, не в GUI, а в json-конфигах)
• Имеет множество плагинов, число которых растёт как на дрожжах
• Поддерживает VIM-режим
• Использует fuzzy-поиск

Один мой друг, историк по профессии, подкинул мне замечательную идею об использовании древней мнемонической и счетной систем в современной криптографии. В процессе его рассказов об узелковой письменности Инков, я начал соображать, что все новое — хорошо забытое старое и было бы не плохо как-то применить древний опыт в современном мире. Первое, что пришло в голову — криптография. Это самое очевидное — просто сконвертировать узлы с ниток в байты и шифр готов. С одной стороны все казалось понятным, но потом я вспомнил про криптостойкость и другие параметры шифров и понял, что не обладаю достаточным опытом и знаниями в области криптографии, чтобы в одиночку разработать новый шифр.

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

Четвертая версия языка оказалось удачной: я написал факториал, затем генерацию последовательности Фибоначи и дюжину простых примерчиков аля “сумма чисел от 0 до 99”. Язык получился что надо: необычный и в тоже время с простой понятной идеей. Главное — язык может решить любую (ну или почти любую) задачу которую можно выразить в виде вычислимой функции.

В q&a разделе Хабра присутствует довольно много вопросов от людей, выбирающих open source проект, в котором они хотели бы поучаствовать: раз, два, три, четыре, пять.

Думаю, многие слышали про браузер Google Chrome и про то, что он основан на open source проекте Chromium. Так получилось, что в течении прошедшего года мне удалось внести небольшой вклад в этот проект в качестве независимого разработчика (то есть я не имею никакого отношения к Google и занимаюсь этим проектом в свободное от работы время). В процессе мне, естественно, пришлось разобраться с некоторыми техническими и организационными моментами, чем и хотелось бы поделиться.

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