Мы все знакомы с различными супергероями и их уникальными способностями, хотим мы того или нет. Потому вопрос о том, какую бы вы хотели иметь суперспособность, не такой и редкий. Кто-то хотел бы быть невероятно сильным, как Халк, кто-то — быстрым, как Флеш, а кто-то не отказался бы от суперспособности Бэтмена — денег. А вот те, кто хоть раз находился в пробке длиной от Марса до Венеры, все бы отдали за возможность телепортироваться. Концепция телепортации звучит весьма увлекательно с точки зрения научной фантастики, однако в реальности эта суперспособность также существует, но наделены ею далеко не люди. Сегодня мы с вами познакомимся с исследованием, в котором ученые из Йокогамского университета (Япония) смогли телепортировать информацию внутри алмаза. Как ученые это сделали, каким боком тут квантовая физика, и что это значит для будущего технологий хранения данных? Ответы ждут нас в докладе ученых. Поехали.

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

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

RAII – одна из наиболее важных и полезных идиом в C++. RAII освобождает программиста от ручного управления ресурсами, без неё крайне затруднено написание безопасного с точки зрения исключений кода. Возможно, самое популярное использование RAII – это управление динамически выделяемой памятью с помощью умных указателей, но она также может с успехом применяться и к другим ресурсам, особенно в мире низкоуровневых библиотек. Примеры включают в себя дескрипторы Windows API, файловые дескрипторы POSIX, примитивы OpenGL и тому подобное.

«Пожалуйста, напишите на C++ функцию, которая получает диаметр круга как float и возвращает длину окружности как float».

Звучит как задание на первой неделе курса по C++. Но это только на первый взгляд. Сложности возникают уже на первых этапах решения задачи. Предлагаю рассмотреть несколько подходов.

Студент: Как вам такой вариант?

#include <math.h>
float CalcCircumference1(float d)
{
    return d * M_PI;
}

Преподаватель: Да, этот код может нормально откомпилироваться. А может и нет.

Как известно, многие Android-приложения можно нативно запускать на Chrome OS благодаря библиотеке Chrome App Runtime.

С помощью расширений chromeos-apk и ARChon запуск Android APK стал возможен и на других ОС.

В этой публикации я расскажу, как установить произвольное Android-приложение на Ubuntu 14.04.

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

Посмотрите на это фото.



Это совершенно обычная фотография, найденная в Гугле по запросу «железная дорога». И сама дорога тоже ничем особенным не отличается.

Что будет, если убрать это фото и попросить вас нарисовать железную дорогу по памяти?

Если вы ребенок лет семи, и никогда раньше не учились рисовать, то очень может быть, что у вас получится что-то такое:

1. Введение

В этой статье я попытаюсь исследовать и развенчать пять популярных мифов про C++:

1. Чтобы понять С++, сначала нужно выучить С
2. С++ — это объектно-ориентированный язык программирования
3. В надёжных программах необходима сборка мусора
4. Для достижения эффективности необходимо писать низкоуровневый код
5. С++ подходит только для больших и сложных программ

Если вы или ваши коллеги верите в эти мифы – эта статья для вас. Некоторые мифы правдивы для кого-то, для какой-то задачи в какой-то момент времени. Тем не менее, сегодняшний C++, использующий компиляторы ISO C++ 2011, делает эти утверждения мифами.

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

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

Все началось с данного топика на сайте gamedev.ru. Топикстартер предложил найти сортировку, которая обладает следующими свойствами:

1. Время выполнения — гарантированные O(nlogn).
2. Использование O(1) дополнительной памяти.
3. Применимость для сортировки данных в односвязных списках (но не ограничиваясь ими).

Оговорки на все три ограничения:

1. Гарантированные O(nlogn) означают, что, например, среднее время быстрой сортировки не подходит — должно получаться O(nlogn) для любых, даже самых худших входных данных.
2. Рекурсию использовать нельзя, поскольку она подразумевает O(logn) памяти на хранение стека рекурсивных вызовов.
3. Произвольного доступа к элементам сортируемого массива нет, мы можем двигаться итератором от любого элемента только к соседнему (за O(1)), причем только в одном направлении (вперед по списку). Модифицировать сам список (перевешивать указатели на следующие элементы) нельзя.

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

Под катом можно узнать, что в итоге получилось у нас.

Challenge. Прежде чем заглядывать под кат, предлагаю сначала самостоятельно подумать над алгоритмом. Если придумается что-то круче нашего варианта — напишите в комментариях.

Не помню, что меня так заело. Наверно, кто-нибудь обыграл меня в Балду с разгромным счетом (ее онлайн-вариант есть на Одноклассниках, Mail.ru и в куче других мест). Короче, я принял вызов. В прошлый раз так было с программкой для разгадки СУДОКУ. Но там все оказалось заметно проще.


Балда, она же Волшебный Квадрат. Игроки добавляют на каждом шагу по одной букве, чтобы получилось осмысленное слово как можно большей длины.

Порой встречаются такие артефакты природы, что начинаешь невольно задумывать о разных конспирологических теориях и альтернативной истории. Сегодня я хотел бы поговорить о разных малоизвестных и не очень аспектах операционной системы MS-DOS. Историй про дос на хабре было огромное множество: краткие очерки, подробная хронология, мемуары ностальгирующих, но никто ни разу не отмечал про MS-DOS 4.0 от 1985 года. Я считаю это очень важным звеном развития операционных систем для IBM PC, но удивительно мало информации о таком важном переходном этапе. Это буквально утерянная ветка доса и найти про нее информацию большая проблема. Что бы вы подумали если бы услышали о поддержке в DOS вытесняющей многозадачности, виртуальной памяти, свопа, семафоров и IPC. Фантастика?

MS-DOS в составе Windows 95 использовалась для двух целей:

• Она служила загрузчиком.
• Она выступала в качестве слоя совместимости с 16-битными драйверами.

Когда Windows 95 стартовала, сначала загружалась специальная версия MS-DOS, именно она обрабатывала ваш файл CONFIG.SYS, запускала COMMAND.COM, который выполнял ваш AUTOEXEC.BAT и в конце концов выполнял WIN.COM, который в свою очередь начинал процесс загрузки 32-битного менеджера виртуальных машин VMM.

Эта специальная версия MS-DOS была полностью функциональна в той мере, в которой слова «полностью функциональна» вообще применимы к MS-DOS. По-другому и быть не могло, при выходе в режим эмуляции MS-DOS только эта версия и оставалась работать.

Программа WIN.COM начинала загрузку того, что большинство людей называют собственно «Windows». Посредством копии MS-DOS она загружала менеджер виртуальных машин, считывала файл SYSTEM.INI, загружала драйверы виртуальных устройств, затем выключала EMM386 (если таковой был) и переключалась в защищённый режим. «Настоящая Windows» с точки зрения большинства людей — именно защищённый режим.

В защищённом режиме драйверы виртуальных устройств творили свою магию. В числе их действий было вытаскивание всего состояния MS-DOS, перевод его в состояние 32-битной файловой подсистемы и отключение MS-DOS. Все дальнейшие файловые операции направлялись в 32-битную файловую подсистему. Когда программа обращалась к int 21h, ответственной за обработку оказывалась 32-битная файловая подсистема.

Здесь вступает в игру вторая роль MS-DOS. Видите ли, программы и драйверы MS-DOS любили встраиваться в глубины операционной системы. Они могли заменять обработчик прерывания 21h, они могли патчить код системы, они могли заменять низкоуровневые дисковые обработчики int 25h и int 26h. Они могли также творить умопомрачительные вещи с прерываниями BIOS типа int 13h, ответственного за работу с дисками.

Пусть мы хотим вычислить десятимиллионное число Фибоначчи программой на Python. Функция, использующая тривиальный алгоритм, на моём компьютере будет производить вычисления более 25 минут. Но если применить к функции специальный оптимизирующий декоратор, функция вычислит ответ всего за 18 секунд (в 85 раз быстрее):


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

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

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

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

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

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

В какой-то из весенних дней этого года я ехал в троллейбусе и листал комикс о Коше. В одном из выпусков была такая фраза «НО! Её можно понять, она же фракталами в горизонт перетекает, я бы тоже замешкался...». После этого я посмотрел в окно и понял, что если мы возьмём два подходящих дробно-линейных преобразования комплексной плоскости a(z) и b(z), и рассмотрим систему итерированных функций для a(z), b(z), a⁻¹(z), b⁻¹(z), взяв в качестве начального множества картинку с Кошем, то Кош будет перетекать фракталами в горизонт!

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

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

Введение

Привет всем! Несколько месяцев назад на Хабре была опубликована статья «Вещание онлайн-видео с помощью nginx» , в которой Aecktann рассказал о своем опыте внедрения разрабатываемого мной модуля к nginx для вещания видео — nginx-rtmp-module. С тех пор продукт активно развивался и в этой статье я более подробно расскажу о нем.

Вещатель нужен для передачи видео-потока клиенту. Речь идет либо о живом потоке, либо о вещании записанного видео (VOD, Video-on-demand). Существует большое количество технологий вещания видео. Среди них можно выделить традиционные протоколы, такие как RTMP или MPEG-TS, а также появившиеся в последнее время технологии адаптивного вещания поверх HTTP. К последним относятся HLS (Apple), HDS (Adobe), Smooth Streaming (Microsoft), MPEG-DASH. При выборе технологии основным фактором является ее поддержка на клиентской стороне. Именно поэтому вещание в формате RTMP на текущий момент является одним из самых распространенных. Протокол HLS поддерживается устройствами компании Apple, а также некоторыми версиями Android.

Недавно я наткнулся на топик "Сервер онлайн-вещаний на базе nginx" о замечательном модуле Романа Арутюняна (@rarutyunyan) для nginx: nginx-rtmp-module. Модуль очень прост в настройке и позволяет на основе nginx создать сервер публикации видеозаписей и живого вещания.

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

Дуглас Крокфорд

2007-02-21

Введение

В 1973 году на первом ежегодном симпозиуме «Принципы языков программирования» (Principles of Programming Languages Symposium) Вон Пратт представил статью «Нисходящий парсер с операторным предшествованием» (Top Down Operator Precedence). В этой статье Пратт описал метод синтаксического разбора, который объединяет лучшие стороны рекурсивного спуска и метода операторного предшествования Флойда. Метод Пратта очень похож на рекурсивный спуск, но требует меньше кода и работает гораздо быстрее. Пратт заявил, что его метод прост в освоении, реализации и использовании, необычайно эффективен и очень гибок. Благодаря своей динамичности он может использоваться для расширяемых языков.

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

Есть и другое объяснение: этот метод наиболее эффективен для динамических, функциональных языков программирования и использовать его в статическом, процедурном языке куда сложнее. Свою статью Пратт иллюстрирует на примере Lisp и играючи строит синтаксические деревья по потоку лексем. Но методы синтаксического разбора не особо ценятся в сообществе Lisp-программистов, которые проповедуют спартанский отказ от синтаксиса. С момента создания Lisp предпринималось немало попыток придать этому языку богатый синтаксис в стиле ALGOL: CGOL Пратта, Lisp-2, MLISP, Dylan, Interlisp's Clisp, оригинальные М-выражения Маккарти и так далее. Но все они провалились. Для Lisp-сообщества согласованность программ и данных оказалась важнее выразительного синтаксиса. С другой стороны, подавляющее большинство программистов любит синтаксис, поэтому сам Lisp так и не стал популярен. Методу Пратта нужен динамический язык, но сообщество динамических языков исторически не пользовалось синтаксисом, который так удобно реализуется методом Пратта.

Эти приемы были описаны во внутреннем проекте компании Google «Testing on the Toilet» (Тестируем в туалете — распространение листовок в туалетах, что бы напоминать разработчикам о тестах).
В данной статье они были пересмотрены и дополнены.