Хотелось бы сказать, что Stack Overflow — масштабный проект, но это не так. Я имею ввиду мы добились многого, но я не могу назвать наш проект “большим”, ещё рано. Давайте я приведу в пример некоторые цифры — с какой нагрузкой мы имеем дело сейчас. Срез статистики за 24 часа от 12 ноября 2013 года. Это обычный будний день. Отмечу, что здесь представлена информация только по нашим собственным вычислительным мощностям, без CDN.

Не так давно на Хабре была статья «Коды Грея и задачи перебора». Статья эта скорее, математическая, нежели программистская, и мне, как простому программисту, читать её было невыносимо тяжело. Но сама тема мне знакома, поэтому я решил описать её своим взглядом, а так же рассказать о том, как использовал её в решении задачи о ранце.


КДПВ: задача о ранце на живом примере

Предыстория

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

Задача почему-то запала мне в душу. Вернувшись домой, я быстро накатал решение: наивный перебор всех возможных сумм с выбором наилучшего. Сочетания я получал, перебирая все N-разрядные двоичные числа и беря суммы тех исходных чисел, которым соответствуют единицы. Но я с огорчением обнаружил, что при количестве элементов начиная где-то с 30, программа работает очень долго. Оно и не удивительно, ведь время работы такого алгоритма — n*2ⁿ (количество сочетаний, умноженное на длину суммы).

Добрый день, уважаемые коллеги. Данная статья будет являться продолжением темы, начатой в посте habrahabr.ru/post/178103.
Продолжим с того момента, когда у нас уже есть значения конструктивных постоянных для двигателя Lego, и можно перейти к конструированию и обсчету робота. В качестве опытного образца остановимся на Segway. Это одна из наиболее показательных задач теории автоматического управления. Привожу конструкцию этого механизма.

Больше года назад Google объявил, что отныне в их поиске используется таинственная Сеть Знаний (официальный перевод Knowledge Graph). Возможно, не все знают, что значительная часть данных Сети доступна для использования всеми желающими и доступна по прекрасно описанному API. Этой частью является база знаний Freebase, поддерживаемая Google и энтузиастами. В этой статье мы сначала немного подурачимся, а потом попробуем сделать несколько простеньких запросов на языке MQL.
Эта статья — вторая из цикла Базы знаний. Следите за обновлениями.

• Часть 1 — Введение
• Часть 2 — Freebase: делаем запросы к Google Knowledge Graph
• Часть 3 — Dbpedia — ядро мира Linked Data
• Часть 4 — Wikidata — семантическая википедия

Рассмотрим простую задачу: есть некоторый достаточно большой неизменный набор чисел, к нему осуществляется множество запросов на наличие некоторого числа в этом наборе, необходимо максимально быстро эти запросы обрабатывать. Одно из классических решений заключается в формировании отсортированного массива и обработке запросов через бинарный поиск. Но можно ли добиться более высокой производительности, чем в классической реализации? В этой статье мне хотелось бы рассказать про Cache-Conscious Binary Search. В данном алгоритме предлагается переупорядочить элементы массива таким образом, чтобы использование кэша процессора происходило максимально эффективно.

Вместо предисловия

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

Как я упоминал в своих предыдущих заметках, основными трудностями при реализации lock-free структур данных являются ABA-проблема и удаление памяти. Я разделяю эти две проблемы, хоть они и связаны: дело в том, что существуют алгоритмы, решающие только одну из них.
В этой статье я дам обзор известных мне методов безопасного удаления памяти (safe memory reclamation) для lock-free контейнеров. Демонстрировать применение того или иного метода я буду на классической lock-free очереди Майкла-Скотта [MS98].

Вступление

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



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

На днях на Хабре публиковали заметку с информацией о том, что любознательным любителем астрономии была проведена предположительная реконструкция климатических условий Марса. В той же заметке публиковались скриншоты модели и небольшое видео. Данные для моделирования брались из базы NASA.

Роботы-газонокосилки имеют пока еще малую популярность в России. Но, судя по нашим продажам, спрос растет с каждым годом более чем на 100%. Люди интересуются, подсматривают у счастливых соседей и загораются желанием купить себе на огород такое устройство. Потом они узнают цену, и их энтузиазм часто сходит на нет. Удовольствие довольно дорогое. Стоят ли косилки своих денег или нет, а также как выбрать подходящую для вашего газона? Давайте разбираться.

Некоторое время назад мне пришлось очень плотно поучаствовать в приемо-сдаточных испытаниях самолета. Эти испытания были основной частью процесса передачи свежеизготовленного, самого (по моему мнению) технически продвинутого на настоящий момент времени бизнес-джета от производителя заказчику. Казалось бы, причем здесь тестирование, разработка, да и вообще тематика Хабра? Желающие узнать это могут перевернуть страницу и прочитать довольно много текста, причем вообще без картинок.

В Firefox 27 появился новый инструмент — редактор шейдеров — который значительно упрощает их разработку. Редактор показывает все запущенные в контексте WebGL программы, даёт возможность редактировать их и сразу же видеть изменения без единого обрыва анимаций или потери состояния.

На одной из конференций произошел комичный случай. Подходит слушательница:

— Александр, есть такой вопрос: Как нам повысить уровень доверия в отношениях с заказчиком?

— А что сейчас не так с уровнем доверия?

— Ну, у нас есть команда, есть менеджер. И мы хотим, чтобы заказчик доверял команде и общался только с менеджером. А он лезет напрямую к инженерам…

— А чем это плохо? Человек сразу получает ответы на свои вопросы, быстрые коммуникации и все такое.

— Понимаете… Мы ему джуниор инженеров продаем как синьор инженеров… И нам не хотелось бы, чтобы он обнаружил этот факт.

Напомню изначальную постановку вопроса: “Как нам повысить уровень доверия в отношениях с заказчиком?”

Вот о заказчиках сегодня и поговорим. А точнее, о простом инструменте, который:

• Поможет осознать, где находятся ваши отношения с заказчиком
• Покажет, почему формы отчетов иногда бывают такие идиотские
• Возможно, поможет понять причины “неадекватного” поведения заказчика

В далеком (а может и не очень далеком) 1975 году Альфред Ахо и Маргарет Корасик опубликовали статью, в которой был подробно описан алгоритм эффективного поиска всех вхождений всех строк-образцов в заданную строку. В дальнейшем этот алгоритм и получил название «алгоритм Ахо-Корасик». Неудивительно, что через некоторое время появились технические и «художественные» переводы данной статьи на русский язык. Порой мне даже встречались вольные изложения сути алгоритма в том виде, в котором его понимает автор. Причем последний, судя по тексту, узнал об алгоритме далеко не из первоисточника. Я не знаю существовал ли перевод, который послужил первоисточником проблемы, но мне всё больше и больше попадаются статьи с описанием алгоритма Ахо-Корасик, в котором допущена одна и та же кардинальная ошибка. Последней каплей была статья пользователя rmq на хабре, которую данная ошибка не миновала. Собственно об этой ошибке мне и хотелось бы рассказать общественности в своей статье.
Замечание: статья пользователя rmq, как выяснилось позже, не содержит этой ошибки. Как она решена там расскажу ниже. А ему огромное спасибо, если бы не его топик я бы не написал свой и не получил бы инвайт!
Перед началом, еще пара слов о целевой аудитории: Скорее всего, тем, кто давно знаком с алгоритмом Ахо-Корасик, моя статья будет не интересна, так как о его особенностях они давно уже знают. По крайней мере, все мои знакомые программисты не один раз применявшие данный алгоритм знают о существовании его неверных интерпретаций не понаслышке. А вот новичкам и тем, кому не довелось часто применять его на практике, эта статья может оказаться довольно полезной.
Итак, начнем.

Привет, Хабр)

Этой статьей мы начинаем серию публикаций о технологиях оптического распознавания (OCR, ICR) и понимания документов, разработанных специалистами компании Cognitive Technologies. Многие из этих решений более 10 лет успешно функционируют в разных организациях и помогают оптимизировать процессы обработки бланков Пенсионного фонда, анкет на получение загранпаспорта, платежных поручений Сбербанка РФ, результатов голосования акционеров Газпрома и десятки других документов.
Сегодня наш рассказ об одной из наиболее сложных и интересных с научной точки зрения проблем, которую приходится решать при распознавании деловых документов, это снятие помех или отделение полезной информации от «мусора».

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

В качестве предисловия

Веб-дизайнерский народ в последнее время распробовал single page web applications. Что оправдано во многих случаях.
Но явно ошибочно считать что single page web application не сделать без чего-то типа AngularJS, Ember и прочих Knockouts.
Во всяком случае если вам нужно сделать нечто простое типа To-do списка совершенно не обязательно тащить на клиент килобайты мега-фреймворка. На самом деле килобайты трафика это пол беды. Основная цена, скажем AngularJS, в том что он, как любой универсальный data binding механизм, создает значительную run-time нагрузку.

Эта статья про то как в 60 строках кода + jQuery/Zepto сделать простой app framework котрый можно расширять под свои нужды и без лишних сущностей в нагрузку.

Постановка задачи

Наш framework должен ...:

1. … поддерживать routing, т.е. должна быть возможность сказать в деклартивной модели: «этот вот url hash должен быть показан в этом view».
2. Должна быть возможность динамической загрузки разных view. Какие-то части нашего приложения могут быть либо тяжелы для начальной загрузки, либо не нужны, например, для незалогиненного пользователя.
3. Должна быть возможность динамической загрузки скриптов. По причинам изложенным в п. 2
4. Наше приложение будет поддерживать browsing history — кнопка «назад» в браузере должна показывать предыдущую страницу и т.д.
5. Ну и все это должно быть компактным и расширяемым как того будет требовать логика нашего приложения.

Пример того что мы хотим получить

Приложение Bootstrap'нутый список контактов — содержит сам список, карточку — детали контакта и некую панель управления (dashboard). Что будет на той панели нам не важно — знаем что что-то будет и ладно.

Доброго времени суток, уважаемые хабравчане. За последнее время я увидел несколько интересных и полезных инструментов/библиотек/событий, которыми хочу поделиться с Хабром.

Browserhacks

Название говорит самое за себя. Данный ресурс — хранилище всевозможных хаков к существующим браузерам. Увидев этот сайт, сам Paul Irish мудро произнес: "Holy shit amazing".

5 замечательных изобретений от David DeSandro (Twitter, H5BP)

Masonry — в переводе «каменная кладка» — идеальное решение для создания Grid Layout. Качественная «замена» для неутвержденной Flexbox спецификации. Простой синтаксис дает возможность без труда создавать Pinterest/Surfingbird подобные макеты. Существует на нативном JavaSciprt и как jQuery плагин.

Isotope — «изысканный jQuery плагин для магических лэйаутов. Позволяет с легкостью фильтровать, сортировать и придавать динамичность макету».

imagesLoaded.js — определяет когда изображения были загружены. Включает в себя 4 события: always, done, fail, progress. Простой в использовании.

Draggabilly — аналог jQuery UI Draggable на нативном JavaScript в лучших традициях автора кода. Работает с touch интерфейсом.
Close Pixelate — «пикселизация» изображений в Canvas аля потаённые места в некоторых работах жанра НЮ.

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

Однако суровая реальность вечно портит всю малину: в пределах города – все небо засвечено уличным освещением и турбулентность воздуха высокая. Это означает, что либо придется ограничится самыми крупными и яркими объектами (вроде Луны и Юпитера), либо возить телескоп далеко за город.

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

Пример того, что получилось: галактика Андромеда, M31 на телескопе Т20

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