Обновить
3
Евгений Аблесов@Codebaker

Пользователь

Отправить сообщение

Построение суффиксного дерева: алгоритм Укконена

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

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


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

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

На самом деле можно.
Реализация и доказательство алгоритма под катом

Разработка настольной игры на примере Starcraft

Время чтения6 мин
Охват и читатели58K
Самая знаковая в IT-среде настольная игра — это, скорее всего, Старкрафт.

Когда компьютерная версия набрала достаточную популярность, ребята из Близзарда поделились правами на марку с известным американским издателем Fantasy Flight Games. В топике — обзор факторов, которые привели к успеху настольной версии.



Кроме всего прочего, информация будет полезна разработчикам игр, которым интересен простой и достаточно красивый дополнительный путь монетизации через «портирование» своей игры в физическую форму.

Читать дальше →

Перевод «How we got rid of time reports» Henrik Kniberg

Время чтения9 мин
Охват и читатели3.3K

Как мы избавились от отчетов о выполненных работах


История об избавлении от бессмысленной траты времени


Введение

Вам когда-нибудь приходилось работать с отчетами о выполненных работах? Заполнять их? Утверждать их? Носиться с ними по всему офису?
Было ли это похоже на время, потраченное с пользой?

Заявление 1: Отчеты о выполненных работах иногда полезны.
Заявление 2: Но очень часто ничего подобного.
Читать дальше →

Асинхронное программирование на JavaScript — Остаться в живых

Время чтения14 мин
Охват и читатели36K
Программисты принимают некоторые особенности как должное — последовательное программирование, к примеру, при записи алгоритма, который делает один шаг только после другого.

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

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

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

Сообщество JavaScript в курсе этого, особенно сообщество Node.JS, так как Node.JS ставит акцент на асинхронном коде.
Читать дальше →

Пример Makefile

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

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

Javascript и canvas в игре «Жизнь» Джона Конвея

Время чтения14 мин
Охват и читатели21K
Напишем эту алгоритмическую игру [1] так, чтобы извлечь из неё максимальную образовательную пользу в области алгоритмов, языка Javascript, хорошего стиля программ, умения оптимизировать код. Центральным местом обсуждения будет не игра, а код, способы реализации, оптимизация.

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

Недавно проведённый на Хабре опрос [3] показал реальную картину — 20% программистов написали когда-либо её работающую реализацию, а порядка 10% о ней не слышали. Что ж, тем интереснее будет оставшимся 80% узнать, что можно извлечь из реализации игры.
Читать дальше →

Этот безумный, безумный, безумный appStore

Время чтения4 мин
Охват и читатели5.5K
В прошлом году Дед Мороз подарил мне подержанный алюминиевый iPhone и новенький MiniMac. Не сразу, ох не сразу я распробовал эти девайсы и окунулся в яблочный мир. Сначала iPhone вытеснил Нокии, Моторолы и Самсунги. Ах ты, Господи, совсем забыл. Все мобильные девайсы у меня валяются на рабочем месте и не были куплены за кровно заработанные деньги.

Через месяц-другой iPhone стал опасно родным, его акселерометр и идеальный тачскрин заставили перенести в него любимые авторские игрушки.

Читать дальше →

Лень (Механизм, ч. 2): Цели

Время чтения5 мин
Охват и читатели5.9K
Обычно, если говоришь технарю почему его устройство не работает так как ему нужно, и в каких местах и какую надо посмотреть неисправность, то грамотный технарь действительно займется этим вопросом и всё исправит. Именно такие предположения я делал публикуя статью «Лень — Механизм». К моему сожалению, реакция большинства оказалась «Не работает? Да и ладно. Мне пока и так хорошо». В связи с этим, предприму попытку реабилитирования и постараюсь еще подробнее разжевать данный механизм с конкретными примерами и советами, однако никакой Хабр не вместит подобный материал в полном объеме, по-этому разобью материал на части. Если данная статья будет востребована, то напишу продолжение. Примеры посвящены студентам (сессия всё-таки скоро).

Читать дальше →

Selenium: ожидание завершения всех AJAX-запросов

Время чтения5 мин
Охват и читатели38K
В последнее время развелось очень много различных AJAX-приложений. По сути автоматизация тестирования такого приложения не отличается от автоматизации тестирования обычного WEB-приложения, но есть несколько тонкостей. Одна из тонкостей — это как раз ожидание завершения всех AJAX-запросов. Например, если отметка некого checkbox'а на странице вызывает обновление какого-нибудь select'a по AJAX-запросу, то тест, который сразу после отметки выбирает конкретный option, свалится, т.к. этого option'a там не будет. А всё потому, что сам тест выполняется намного быстрее чем AJAX-запрос на обновление списка.

В данном случае у автоматизатора есть несколько выходов.
Читать дальше →

Пишем свой промежуточный драйвер. Часть 1

Время чтения5 мин
Охват и читатели26K
Здравствуйте, уважаемые хабраюзеры!
Интересовались ли Вы когда-нибудь как работает снифер и что он из себя представляет? Или как Ваш любимый фаервол защищает Вас от троянов и прочей гадости на сетевом уровне? Да и вообще, как он работает? Я уверен, что Вы задавали себе такого рода вопросы, но все же, если нет, то я от части Вам про это расскажу. Начиная с этой статьи мы будем постепенно осваивать написание своего сниферо-подобного драйвера. Сегодня мы рассмотрим некоторые общие положения, которые нам будут необходимы для понимая всего того, что будет происходить в последующих статьях. Перед прочтением этой статьи, дабы у Вас началась складываться более или менее ясная картина, я рекомендую Вам прочтение прошлого топика Краткий обзор драйверов спецификации NDIS

Всем кому это интересно прошу под кат.
Читать дальше →

Многопоточный Observer на С++ (практика)

Время чтения12 мин
Охват и читатели9.2K
Есть много вариаций на тему данного паттерна, но большинство примеров не подходит для многопоточных приложений.
В этой статье я хочу поделится опытом применения паттерна в многопоточных приложениях и опишу основные проблемы, с которыми мне приходилось сталкиваться.
Цель данной стати — обратить внимание разработчиков на проблемы, с которыми можно столкнуться при создании многопоточных приложений. Выявить подводные камни в реализации коммуникации между компонентами в многопоточном приложении.
Если Вам необходимо готовое решение, обратите внимание на библиотеку Signals2, котрая включена в boost с мая 2009-го года.
Я не пытаюсь предоставить решение, которое можно было бы использовать в готовом виде. Но тем не менее, ознакомившись с материалом, можно обойтись без использования сторонних библиотек, в тех проектах, в которых они по каким-либо причинам не доступны или нежелательны (драйвера, низкоуровневые приложения и т.п.).
Читать дальше →

libscgi — эффективное решение для простых и быстрых скриптов

Время чтения4 мин
Охват и читатели5.3K
Очень часто необходимо реализовать простое легкое решение, которое должно отработать довольно быстро. А с использованием технологии AJAX это стало еще актуальнее. Это может быть как скрипт автокомплита, скрипт специфического поиска, вывод информации из справочника. Ранее использовались cgi скрипты. При больших нагрузках они оказались не очень эффективными и были разработаны протоколы fcgi и scgi. Следует заметить что производительность scgi сервера довольно-таки высокоя (более 1500 запр/сек) и памяти занимает всего 600K.

Протокол Simple Common Gateway Interface (SCGI) — это протокол по взаимодействию приложений с веб (http) серверами. Большинство современных WEB-серверов (Apache/nginx/lighttpd) имеют встроенную поддержку scgi. Ниже дано краткое описание использование простой библиотечки, которая представляет собой scgi сервер.

Исходники тут.
Читать дальше →

Python-way. Работа над ошибками

Время чтения3 мин
Охват и читатели20K

Всем доброго времени суток! Новогодние праздники позади, все хорошо отдохнули. Тем не мнеее, даже в праздники иногда появляется работа. Мне, к примеру, довелось покопаться в чужом коде на Python. Код хороший, замечательно документирован, но во время чтения не покидало ощущение, что автор читал доки по Python и портировал код с Си-подобного языка. Это меня вдохновило на написание статьи с указанием ошибок, которые неизбежно возникают при переходе на Python с Си-подобных языков.

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

Читать дальше →

Пишем HTTP proxy сервер с плагинами

Время чтения7 мин
Охват и читатели22K
imageОдно время всплыла тема, что в одной из онлайн-игр появилась такая довольно досадная штука, как каптча. Само по себе, отвлекаться от игры для ввода каптчи может обернуться не слишком хорошими последствиями, особенно, если вводишь её не с первого раза, могут и враги насолить. Но не в этом соль. Особенно плоха вещь для тех, кто использует локальных ботов. Те то, маленькие, спотыкаются об каптчу, и за это игра мнгновенно их штрафует потерей юнитов и ресурсов. Неприятная штука, что говорить.

Итак, задача:
Хочется, чтобы каптчу вводить не приходилось. Хоть если играешь сам, хоть если играет за тебя бот, если ты спишь.
Дополнительное условие: 40 часов времени (ибо паника на корабле).
Желательное условие: установочный файл под Windows.
Ещё одно желательное условие: результат должен занимать не более мегабайта.
Решение задачи с нуля под катом

Алгоритм «diamond-square» для построения фрактальных ландшафтов

Время чтения12 мин
Охват и читатели123K
Карта игры Minecraft, созданная с помощью приложения CartographДумаю, многие знакомы с весьма необычной игрой Minecraft (справа — пример сгенерированной в ней карты), в которой игрок находится на (практически) бесконечной поверхности Земли и может исследовать окружающий мир с минимальными ограничениями.

Как же автору игры, Notch'у, удалось добиться подобного сходства его случайных «миров» с земными просторами? В этом топике я как раз и рассмотрю один из способов построить искусственный ландшафт такого рода (и вскользь упомяну пару других способов), а также расскажу о моем небольшом усовершенствовании этого алгоритма, позволяющем значительно увеличивать размеры ландшафта без заметных потерь в производительности.

Внутри вас ждет несколько схем и красивых картинок, довольно много букв и ссылка на пример реализации алгоритма.

Читать дальше →

Лень — механизм

Время чтения5 мин
Охват и читатели75K

Начинается рабочая неделя для большинства жителей России и близится зимняя сессия. В связи с этим решил описать детальный механизм лени человека.
Однако хочу вас обнадежить, лень является лишь проявлением работы нашего подсознания, а значит ее можно контролировать и «настраивать» как вам того желается. Вы сами сможете в этом убедиться, когда поймете механизм ее возникновения.
Читать дальше →

Как не дать программисту написать плохой код

Время чтения3 мин
Охват и читатели6.7K
image
Как-то раз в одной неглупой статье один неглупый хабраюзер рассказал одну неглупую идею. Суть её была в том, что в его компании настроена система, контролирующая написанный программистами код в момент попытки добавления его в репозиторий и отклоняющая код, не проходящий по некоторым критериям. Мне идея понравилась. Я (и еще 3 человека) попросили автора развить мысль и написать статью об этом, но она так и не появилась. И я решил разобраться сам.
Читать дальше →

Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе

Время чтения3 мин
Охват и читатели455K
Из многих алгоритмов поиска кратчайших маршрутов на графе, на Хабре я нашел только описание алгоритма Флойда-Уоршалла. Этот алгоритм находит кратчайшие пути между всеми вершинами графа и их длину. В этой статье я опишу принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса.

Для примера возьмем такой ориентированный граф G:

image

Читать дальше →

Мультиплексированный ввод/вывод

Время чтения7 мин
Охват и читатели31K

Preface


В данной статье я бы хотел затронуть важные аспекты программирования приложений для web, которые должны обслуживать множество пользователей одновременно, а значит мы будем разбирать уже всем надоевший асинхронный ввод/вывод, мультиплексирование и т.п.
Преследуются следующие цели:
  1. Систематизировать материал по данному направлению, обсудить некоторые несостыковки в терминологии
  2. Полностью разобрать фундамент, на котором строятся приложения для обслуживания множество клиентов
  3. Выработать стратегию для будущего приложения на python которое должно обслуживать множество клиентов
  4. Создать четкую картину в голове (недаром говорят понимаешь — когда можешь объяснить)


Читать дальше →

Ассемблер для Windows используя Visual Studio

Время чтения4 мин
Охват и читатели150K
Многие из нас изучали ассемблер в университете, но почти всегда это ограничивалось простыми алгоритмами под DOS. При разработке программ для Windows может возникнуть необходимость написать часть кода на ассемблер, в этой статье я хочу рассказать вам, как использовать ассемблер в ваших программах под Visual Studio 2005.

image

Создание проекта


В статье мы рассмотрим как вызывать ассемблер из С++ кода и обратно, передавать данные, а также использовать отладчик встроенный в Visual Studio 2005 для отладки кода на ассемблер.
Читать дальше →

Информация

В рейтинге
Не участвует
Откуда
Москва, Москва и Московская обл., Россия
Работает в
Дата рождения
Зарегистрирован
Активность