Пакеты numpy и scipy предоставляют прекрасные возможности для быстрого решения различных вычислительных задач. Концепция универсальных функций (ufunc), работающих как со скалярными значениями, так и с массивами различных размерностей, позволяет получить высокую производительность при сохранении присущей языку Python простоты и элегантности. Универсальная функция обычно используются для выполнения одной операции над большим массивом данных, что идеально подходит для оптимизации с помощью SIMD-инструкций, однако мне не удалось найти готового решения, основанного на свободном программном обеспечении и позволяющего использовать SIMD для вычисления в numpy таких математических функций, как синус, косинус и экспонента. Реализовывать алгоритмы вычисления этих функций с нуля совсем не хотелось, но к счастью в интернете нашлось несколько свободных библиотек на языке «С». Преодолев лень сомнения, я решил написать собственный numpy-модуль, предлагающий универсальные функции для синуса, косинуса и экспоненты. За подробностями и результатами тестов добро пожаловать под кат.

Вступление

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

Начальное описание

Алгоритм Ахо-Корасик реализует эффективный поиск всех вхождений всех строк-образцов в заданную строку. Был разработан в 1975 году Альфредом Ахо и Маргарет Корасик.
Опишем формально условие задачи. На вход поступают несколько строк pattern[i] и строка s. Наша задача — найти все возможные вхождения строк pattern[i] в s.

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

От переводчика: вдохновившись циклом статей, я решил попробовать свои силы в SDL. Да вот незадача, каких-либо толковых уроков по SDL версии 2.0 на русском языке найти мне не удалось. Это и подтолкнуло меня к переводу замечательной серии туториалов Twinklebear, в оригинале доступных тут.

Добро пожаловать!

Цель данных уроков — познакомить вас с основами SDL 2.0 и гейм-дева на С++. Подразумевается, что у читателя есть некоторый опыт программирования на С++ и минимальные знания массивов, векторов, управляющих структур, функций и указателей.

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

Если вы хотите увидеть полный исходник или же скачать ресурсы для уроков, то все это можно получить на GitHub’е. Но не копируйте!

Также документация по SDL 2.0 доступна для чтения в этой вики.

Доброго времени суток, уважаемое сообщество.

Предыстория

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



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

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

1. иметь малые накладные расходы по памяти. Большая часть доступной памяти должна использоваться для хранения текста, а не служебной информации;
2. допускать эффективную вставку и удаление в произвольном месте текста.

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

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

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

Несмотря на то, что эта структура данных была открыта давно и использовалась в текстовых редакторах на старых ЭВМ в 8-битную эпоху, это тайное знание предков было в значительной мере утеряно и в современных редакторах встречается редко. Попробуйте открыть файл, состоящий из одной строки мегабайт на 10, в Notepad или Far. Вставка и удаление символов будет длиться секундами.

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

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

Что же всё-таки можно нарисовать с помощью всего двух треугольников? Квадрат? Фрактал? Полёт сквозь мегатонной мощности взрыв в центре города? Есть ли предел безумию, где заканчивается реальность и начинается явь? Как правильно ухаживать за лучами, чем их кормить и обо что отражать вы узнаете во внезапном продолжении цикла статей про демомейкинг!

Всем привет!

Хочу начать вольный перевод отличной книги «WebGL Beginner's Guide», которая, на мой взгляд, будет интересна не только новичкам, но и более продвинутым разработчикам.

Содержание:

• Глава 1: Начиная работать с WebGL
• Глава 2: Рендеринг геометрии
• Глава 3: Освещение
• Глава 4: Камера
• Глава 5: Движение
• Глава 6: Цвет, глубина и альфа-смешение
• Глава 7: Текстуры
• Глава 8: Выбор
• Глава 9: Собираем все вместе
• Глава 10: Дополнительные методы

WebGL первоначально была основана на OpenGL ES 2.0 (ES означает Embedded Systems), версии спецификации OpenGL для таких устройств как iPhone от Apple и iPad. Но спецификация развивалась, стала независимой, ее основная цель это обеспечение переносимости между различными операционными системами и устройствами. Идея веб-интерфейса, рендеринг в реальном времени открыли новую вселенную возможностей для веб-3D сред, таких как видеоигры, научная и медицинская визуализация. Кроме того, из-за широкого распространения веб-браузеров, эти и другие виды 3D-приложений могут быть запущены на мобильных устройствах, таких как смартфоны и планшеты. Если вы хотите создать свою первую веб-видеоигру, 3D арт-проект для виртуальной галереи, визуализацию данных ваших экспериментов или любое другое 3D-приложение, вы должны иметь ввиду, что первым шагом должно быть то, что вы должны убедиться, что у вас есть подходящая среда.
В этой главе вы сможете:

• Понять структуру WebGL-приложения
• Создавать свои области рисования (canvas)
• Проверить WebGL-возможности вашего браузера
• Понять, как устроена машина состояний WebGL
• Изменять переменные WebGL, которые влияют на вашу сцену
• Загружать и исследовать полнофункциональные сцены

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

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

Что из этого вышло читайте дальше.

Пишем игры на C++, Часть 2/3 — State-based программирование
Пишем игры на C++, Часть 3/3 — Классика жанра

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

На хабре не очень много уроков по созданию игр, почему бы не поддержать отечественных девелоперов?
Представляю вам свои уроки, которые учат создавать игры на C++ с использованием SDL!

Что нужно знать

• Хотя бы начальные знания C++ (использовать будем Visual Studio)
• Терпение

О чем эта часть?

• Мы создадим каркас для всех игр, в качестве отрисовщика будем использовать SDL. Это библиотека для графики.

В следующих постах будет больше экшена, это лишь подготовка :)

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

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

В этой главе мы поднимемся на следующую ступень и рассмотрим модули и функции.

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

На самом деле, у хрущёвок существует несколько десятков модификаций, но некая основа, сущность хрущёвки всё равно прослеживается.

В общем, недолго думая, я сел и написал генератор хрущёвок на C# под Unity3d. Под катом описание работы алгоритма и размышления на тему uv-карт, сабмешей и шейдеров.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1
Часть 2

Логарифмы

Если вы знаете, что такое логарифмы, то можете спокойно пропустить этот раздел. Глава предназначается тем, кто незнаком с данным понятием или пользуется им настолько редко, что уже забыл что там к чему. Логарифмы важны, поскольку они очень часто встречаются при анализе сложности. Логарифм — это операция, которая при применении её к числу делает его гораздо меньше (подобно взятию квадратного корня). Итак, первая вещь, которую вы должны запомнить: логарифм возвращает число, меньшее, чем оригинал. На рисунке справа зелёный график — линейная функция f(n) = n, красный — f(n) = sqrt(n), а наименее быстро возрастающий — f(n) = log(n). Далее: подобно тому, как взятие квадратного корня является операцией, обратной возведению в квадрат, логарифм — обратная операция возведению чего-либо в степень.

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

(с) xkcd

Без использования сложных формул и матлаба я постараюсь ответить на следующие вопросы:

• FT, DTF, DTFT — в чем отличия и как совершенно разные казалось бы формулы дают столь концептуально похожие результаты?
• Как правильно интерпретировать результаты быстрого преобразования Фурье (FFT)
• Что делать если дан сигнал из 179 сэмплов а БПФ требует на вход последовательность по длине равную степени двойки
• Почему при попытке получить с помощью Фурье спектр синусоиды вместо ожидаемой одиночной “палки” на графике вылезает странная загогулина и что с этим можно сделать
• Зачем перед АЦП и после ЦАП ставят аналоговые фильтры
• Можно ли оцифровать АЦП сигнал с частотой выше половины частоты дискретизации (школьный ответ неверен, правильный ответ — можно)
• Как по цифровой последовательности восстанавливают исходный сигнал

Я буду исходить из предположения что читатель понимает что такое интеграл, комплексное число (а так же его модуль и аргумент), свертка функций, плюс хотя бы “на пальцах” представляет себе что такое дельта-функция Дирака. Не знаете — не беда, прочитайте вышеприведенные ссылки. Под “произведением функций” в данном тексте я везде буду понимать “поточечное умножение”

Всем привет!
Продолжаю перевод книги John Torjo «Boost.Asio C++ Network Programming». В этой части второй главы мы поговорим про асинхронное программирование.

Содержание:

• Глава 1: Приступая к работе с Boost.Asio
• Глава 2: Основы Boost.Asio
  
  • Часть 1: Основы Boost.Asio
  • Часть 2: Асинхронное программирование
• Глава 3: Echo Сервер/Клиент
• Глава 4: Клиент и Сервер
• Глава 5: Синхронное против асинхронного
• Глава 6: Boost.Asio – другие особенности
• Глава 7: Boost.Asio – дополнительные темы

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

В задачах поиска информации одной из важнейших задач является поиск точно заданной подстроки в строке. Примитивный алгоритм поиска подстроки в строке основан на переборе всех подстрок, длина которых равна длине шаблона поиска, и посимвольном сравнении таких подстрок с шаблоном поиска. По традиции шаблон поиска или образец принято обозначать как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»). На языке Python примитивный алгоритм выглядит так:

index = -1
for i in xrange(len(haystack)-len(needle)+1):
    success = True
    for j in xrange(len(needle)):
        if needle[j]<>haystack[i+j]:
            success = False
            break
    if success:
        index = i
        break
print index

Обозначим n=|haystack|, m=|needle|. Простейший алгоритм поиска даже в лучшем случае проводит n–m+1 сравнений; если же есть много частичных совпадений, скорость снижается до O(n*m).

Рассматриваемый далее алгоритм хотя и имеет невысокую скорость на «хороших» данных, но это компенсируется отсутствием регрессии на «плохих». Алгоритм Кнута-Морриса-Пратта является одним из первых алгоритмов с линейной оценкой в худшем случае.

Всем добрый день!

В статье уже был кратко рассмотрен оператор LBP. Хотелось бы остановиться на данном вопросе несколько подробнее, а также рассмотреть применение LBP к решению задачи распознавания лиц.

1. Введение

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

Продолжение.
Предыдущие части: 1-3, 4-6

7. Связь один-ко-многим.

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

Другой пример связи один-ко-многим – это связь, которая существует между матерью и ее детьми. Мать может иметь множество детей, но каждый ребенок может иметь только одну мать.

(Технически лучше говорить о женщине и ее детях вместо матери и ее детях потому, что, в контексте связи один-ко-многим, мать может иметь 0, 1 или множество потомков, но мать с 0 детей не может считаться матерью. Но давайте закроем на это глаза, хорошо?)

Когда одна запись в таблице А может быть связана с 0, 1 или множеством записей в таблице B, вы имеете дело со связью один-ко-многим. В реляционной модели данных связь один-ко-многим использует две таблицы.


Схематическое представление связи один-ко-многим. Запись в таблице А имеет 0, 1 или множество ассоциированных ей записей в таблице B.

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

4. ТАБЛИЦЫ И ПЕРВИЧНЫЕ КЛЮЧИ

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



В таблице имеются 6 уроков. Все 6 – разные, но для каждого урока значения одинаковых полей хранятся в таблице, а именно: tutorial_id (идентификатор урока), title (заголовок)и category (категория). Tutorial_id – первичный ключ таблицы уроков. Первичный ключ – это значение, которое уникально для каждой записи в таблице.
В таблице клиентов ниже customer_id – первичный ключ. В данном случае первичный ключ – также уникальное значение (число) для каждой записи.

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

Другие части: 4-6, 7-9, 10-13, 14-15.

Руководство по проектированию баз данных.

1. Вступление.

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