Суффиксное дерево – мощная структура, позволяющая неожиданно эффективно решать мириады сложных поисковых задач на неструктурированных массивах данных. К сожалению, известные алгоритмы построения суффиксного дерева (главным образом алгоритм, предложенный Эско Укконеном (Esko Ukkonen)) достаточно сложны для понимания и трудоёмки в реализации. Лишь относительно недавно, в 2011 году, стараниями Дэни Бреслауэра (Dany Breslauer) и Джузеппе Италиано (Giuseppe Italiano) был придуман сравнительно несложный метод построения, который фактически является упрощённым вариантом алгоритма Питера Вейнера (Peter Weiner) – человека, придумавшего суффиксные деревья в 1973 году. Если вы не знаете, что такое суффиксное дерево или всегда его боялись, то это ваш шанс изучить его и заодно овладеть относительно простым способом построения.

Здравствуй, Хабр!

В этой статье речь пойдёт о небольшом программистском этюде на тему машинного обучения. Замысел его возник у меня при прохождении известного здесь многим курса «Machine Learning», читаемого Andrew Ng на Курсере. После знакомства с методами, о которых рассказывалось на лекциях, захотелось применить их к какой-нибудь реальной задаче. Долго искать тему не пришлось — в качестве предметной области просто напрашивалась оптимизация собственного шахматного движка.

Вступление: о шахматных программах

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

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

Строго говоря, настоящая оценка может принимать только три значения: выигрыш, проигрыш или ничья — 1, 0 или ½. По теореме Цермело для любой заданной позиции она определяется однозначно. На практике же из-за комбинаторного взрыва ни один компьютер не в состоянии просчитать варианты до листьев полного дерева игры (исчерпывающий анализ в эндшпильных базах данных — это отдельный случай; 32-фигурных таблиц в обозримом будущем не появится… и в необозримом, скорее всего, тоже). Поэтому программы работают в так называемой модели Шеннона — пользуются усечённым деревом игры и приближённой оценкой, основанной на различных эвристиках.

То, что иногда наблюдается в адресной строке пустой страницы «about:blank», для Мозиллы стало философией доступа к ресурсам браузера. Мало кто знает об этой философии, кроме просвещённых монахов, для которых адресная строка менее священна и более инструментальна, чем для остальных. Но трудно запомнить всё разнообразие свойств этой строки. Приоткрыть окно к просветлению помогает мантра «about:about». Сейчас, на момент версии 37, она открывает 34 варианта продолжений ссылок после двоеточия. Есть и недокументированные.

Шутники потирают руки: можно вызывать самые натуральные озадачивающие странички минимальными усилиями. Но есть и ряд полезных страниц. Цель списка ниже — выделить долю полезных страниц для продвинутого пользователя браузера.

27 февраля состоялся очередной Python Meetup. В этот раз мы обсуждали:

• Hy — диалект, который позволяет Lisp-разработчикам использовать библиотеки Python, а Python’истам найти решение для некоторых проблем языка, например, отсутствия скобочек.
• Toga — библиотека построения интерфейсов на Python, которая с первого взгляда выглядит как простой и универсальный инструмент, но на деле имеет ряд недоработок.

Во время Lightning Talk участники делились опытом экспорта .doc-файлов и идеями использования AST для трансляции Python в Ruby, JavaScript, C++ и др.

Всем привет!

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

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

Также данная сборка предлагается и в 32-битной версии для Linux.

По многочисленным просьбам мы добавили возможность открывать закладки или веб-сайты с Экспресс-панели в фоновом режиме кликом средней кнопки мыши (или колёсиком).

Ещё одна хорошая новость для любителей управлять браузером с помощью клавиатуры: мы добавили функцию восстановления недавно закрытой вкладки с помощью клавиатурных команд (CTRL+Z и CTRL+SHIFT+T).

Ну и, наконец, значительно расширился список языков, на которые переведён интерфейс браузера. Теперь список локализаций насчитывает 22 языка, а к имевшимся ранее были добавлены:

Цель данной статьи — показать возможный подход для построения микросервисов с использованием Scala, RESTful JSON, Spray и Akka. В качестве базы данных мы будем использовать MongoDB. В результате нашей работы мы упакуем наш проект в Docker-контейнер, а Vagrant и Ansible позволит нам управлять конфигурацией приложения.

В этой статье вы не найдете подробностей о языке Scala и других технологиях, которые будут использоваться в проекте. В ней вы не найдете руководства, которое ответит на все ваши вопросы. Цель статьи — показать технику, которую можно использовать при разработке микросервисов. На самом деле, большая часть этой статьи не завязана на конкретной технологии. Docker имеет более широкую сферу использования, нежели только микросервисы. Ansible позволяют быстро развернуть любое требуемое окружение, а Vagrant — отличный инструмент для создания виртуальных машин.

Композиция логирования

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

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

Мы в Хекслете недавно запустили новую версию, ключевой особенностью которой стали практические упражнения по программированию в браузере. В связи с этим мы стали получать еще больше писем от начинающих программистов с вопросами вроде «с чего начать». С одной стороны, они хотят выложить бета-версию приложения в app store через неделю. С другой стороны, мы понимаем, что за такой короткий срок, наверное, можно научиться кодить приложения, но нельзя научиться программировать. И сложно решить, что лучше: как можно быстрее научить созданию простых приложений без реального понимания программирования, алгоритмов и их вычислительной сложности, а потом начать знакомство с этими важными темами, или начать «с начала», и органично придти к созданию приложений и продуктов после освоения фундамента.

В 2001 году, Эдсгер Дейкстра написал письмо экономическому совету университета Техаса. В нем знаменитый ученый призывает членов совета задуматься о смене языка программирования для вводного курса. К сожалению, язык был заменен на Java. Примерно в то же время MIT сменили язык курса «Структура и интерпретация компьютерных программ» с функционального Scheme (диалекта LISP) на Python.

Сегодня мы публикуем перевод этого письма.

Членам Экономического Совета

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

Всякий, кто полагается на практику, не зная теории, подобен кормчему, вступающему на судно без руля и компаса, – он не знает, куда плывет.
Леонардо да Винчи

В Священных Языковых Войнах в качестве окончательного аргумента нередко приводят — поскольку языки полны по Тьюрингу, постольку они и равноценны. Под катом попытка уточнить этот тезис для тех, кто уже справился с Python и теперь планирует изучить Erlang или Haskell по спецификации. Материал обзорный, не методичный с картинками.

Доброго времени суток, дорогой %habrauser%!

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

Вступление

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

Я, автор, Юра Перов, занимаюсь вероятностным программированием в течение уже двух лет в рамках своей основной учебно-научной деятельности. Продуктивное знакомство с вероятностным программированием у меня сложилось, когда будучи студентом Института математики и фундаментальной информатики Сибирского федерального университета, я проходил стажировку в Лаборатории компьютерных наук и искусственного интеллекта в Массачусетском технологическом институте под руководством профессора Джошуа Тененбаума и доктора Викаша Мансингхи, а затем продолжилось на Факультете технических наук Оксфордского университета, где на данный момент я являюсь студентом-магистром под руководством профессора Френка Вуда.

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

«Обычное» программирование

Для знакомства с вероятностным программирование давайте сначала поговорим об «обычном» программировании. В «обычном» программировании основой является алгоритм, обычно детерминированный, который позволяет нам из входных данных получить выходные по четко установленным правилам.

Quotient filter — это вероятностная структура данных, позволяющая проверить принадлежность элемента множеству. Она описана в 2011 г. как замена фильтру Блума. Ответ может быть:
— элемент точно не принадлежит множеству;
— элемент возможно принадлежит множеству.

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

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

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

Механические клавиатуры. Путеводитель.

(В недавнем обзоре истории OS/2 давалась очень обобщенная картина разработки ОС. Надеюсь его хорошо дополнит взгляд изнутри самой IBM, воспоминания рядового тестера OS/2.)

Богопротивный альянс IBM и Microsoft выпустил OS/2 25 лет назад, чтобы заменить Windows, Unix и DOS. В то время я был рядовым солдатом этой войны: тестером, работающим в Синем Гиганте по договору. Жестокая судьба и еще более жестокий редактор хотят, чтобы 25 лет спустя я написал статью о том, стоит ли вам сейчас посвящать свою карьеру Microsoft. И меня до сих пор поражает то, насколько не знающие историю люди обречены ее повторять.

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

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

IBM была патологически скрытной. Мое собеседование в основном состояло из вопросов в духе «итак, Доминик, расскажите о себе» без малейших намеков на то, чем мне предстоит заниматься. Так как я принимал участие в проекте Microsoft Unix для Intel x86, я ответил: «В определенном смысле моя работа заключалась в том, что я портил жизнь Microsoft». Сотрудник отдела кадров IBM сказал, что, как правило, их начальству требуется «должное количество времени» для принятия решения, но в этот раз предложение работы пришло на мой автоответчик еще до того, как я вернулся домой.

В свете последних событий, связанных со Skype (блокировка «старых» версий клиента, насильное обновление клиентов на всех платформах, откровенно сырая новая версия клиента для Linux), решил поделиться с сообществом успешным опытом использования Google Hangouts для коллаборации (командной разработки ПО, парного программирования) и написать универсальное руководство (tutorial, how-to) для Debian/Ubuntu Linux, а также Mac OS X и Windows, собрав всю необходимую и полезную информацию воедино.

Эта статья для тех, кто в поиске полноценной альтернативы Skype для большинства современных платформ и в первую очередь для Linux.

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

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

Хоть я и пообещал, что после прочтения этой статьи, можно будет играть в Metro 2033 на калькуляторе (шутка, такого не будет), все же она начнется с рекомендации купить кое-что из железа, если у вас этого еще нет.

Есть проблема в ubuntu 14.04, если назначить в качестве переключалки раскалдки клавиатуры кнопку CapsLock, то со временем (не сразу) при попытке переключить раскладку она бдет скакать как рулетка между языками и остановится непонятно на каком. Баг в общем.
Найдено простое решение.

Сегодня мы продолжаем начатый неделю назад рассказ об интерфейсе игры World of Tanks.

Текущее состояние проекта

Освежим информацию из первой части статьи.

Сейчас для рендеринга GUI в проекте используется технология Autodesk Scaleform, которая позволяет использовать Flash как среду разработки.

Кто знаком с Flash, тот знает, что языком программирования в этой среде является ActionScript. У этого языка есть несколько версий, но самые широко используемые — ActionScript2 (AS2) и ActionScript3 (AS3).

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

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

про AMQP говорили много. Очередная разработка, ориентированная на AJAX.
Возможности:

• читать из очереди одно сообщение
• читать из очереди все сообщения
• узнать длинну очереди
• публиковать сообщение в обмен

Данные возвращаются в JSON.