Как стать автором
Обновить
0
0

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

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

Математик оптимизировал решето Эратосфена, чтобы искать простые числа с меньшим расходом памяти

Время на прочтение4 мин
Количество просмотров31K

38-летний перуанский математик Харальд Хельфготт три года назад доказал тернарную гипотезу Гольдбаха, а сейчас сумел оптимизировать компьютерный алгоритм для расчёта решета Эратосфена. Фото: Matías Loewy

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

Суть понятна из названия. Решето Эратосфена означает поиск простых чисел методом исключения. Берём список чисел, исключаем из него все составные числа — и получаем список простых чисел, словно просеяв список через решето.
Читать дальше →
Всего голосов 57: ↑46 и ↓11+35
Комментарии50

Как устроен поиск

Время на прочтение28 мин
Количество просмотров34K
Андрей Аксёнов

Андрей Аксенов (shodan, Разработчик поискового движка Sphinx)


Поиск устроен вот так:

Краткое устройство поиска

Индексация – по большому счету, ничего сложного. Понятное дело, что по малому счету, там в каждой из трех «деталей» спрятан не то, что демон, а целое где-то стадо, где-то легион, не совсем понятно. Но концепция всегда простая. Все начинается с маленького простенького патчика к Многосерчу, а потом 15 лет этой херней занимаешься.

Берешь документы, разваливаешь их на ключевые слова. И просто взять и развалить документ на ключевые слова «мама, мыла, раму» – это ты не далеко ушел от grep’а, потому что потом все равно эти ключевые слова перебирать. Надо строить некую спец. структуру – полнотекстовый индекс. Вариантов для его построения человечество придумало в свое время довольно много, но, слава Богу, от всех отказалось и в нормальных продакшн системах, по большому счету, победил на данный момент вариант ровно один. Про него и буду рассказывать. Все остальные имеют скорее историческое значение, что ли, и практического интереса не представляют.
Всего голосов 64: ↑53 и ↓11+42
Комментарии22

Elixir: Готовим парсинг правильно — yecc и leex

Время на прочтение9 мин
Количество просмотров12K

Лексический анализ (токенизация) и парсинг — одни из наиболее важных концепцпий в информатике и программировании. Эти концепции базируются на огромном количестве теоретических знаний, но сегодня мы о них не будем говорить, потому что их действительно много. Кроме того, подход к парсингу через "науку" может вызвать жёсткое отвращение и напугать. Между тем, практическое применение очень простое и прямолинейное. Если хотите знать больше о теории — идите в Википедию (лексический анализ и парсинг), или читайте восхитительную книгу дракона (рекомендовано к прочтению вообще всем программистам).


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

Читать дальше →
Всего голосов 20: ↑20 и ↓0+20
Комментарии22

Изучаем OpenGL ES2 для Android Урок №4. Текстуры

Время на прочтение8 мин
Количество просмотров20K
Перед тем как начать

» Если вы новичок в OpenGL ES, рекомендую сначала изучить предыдущие 3 урока: раз / два / три
» Основы кода, используемого в этой статье, взяты отсюда и отсюда.

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


Читать дальше →
Всего голосов 22: ↑19 и ↓3+16
Комментарии2

Стилизация изображений с помощью нейронных сетей: никакой мистики, просто матан

Время на прочтение14 мин
Количество просмотров92K

Приветствую тебя, Хабр! Наверняка вы заметили, что тема стилизации фотографий под различные художественные стили активно обсуждается в этих ваших интернетах. Читая все эти популярные статьи, вы можете подумать, что под капотом этих приложений творится магия, и нейронная сеть действительно фантазирует и перерисовывает изображение с нуля. Так уж получилось, что наша команда столкнулась с подобной задачей: в рамках внутрикорпоративного хакатона мы сделали стилизацию видео, т.к. приложение для фоточек уже было. В этом посте мы с вами разберемся, как это сеть "перерисовывает" изображения, и разберем статьи, благодаря которым это стало возможно. Рекомендую ознакомиться с прошлым постом перед прочтением этого материала и вообще с основами сверточных нейронных сетей. Вас ждет немного формул, немного кода (примеры я буду приводить на Theano и Lasagne), а также много картинок. Этот пост построен в хронологическом порядке появления статей и, соответственно, самих идей. Иногда я буду его разбавлять нашим недавним опытом. Вот вам мальчик из ада для привлечения внимания.


Читать дальше →
Всего голосов 145: ↑141 и ↓4+137
Комментарии38

Модель взаимодействия судов с водой в видеоиграх

Время на прочтение16 мин
Количество просмотров36K


Давайте поговорим о физике транспортных средств


Физика транспортных средств в видеоиграх не очень сильно обсуждается. Статьи в Интернете о физике транспорта в видеоиграх немногочисленны и поверхностны; обычно они посвящены самым основам. Программист транспорта для видеоигр ощущает себя сегодня в относительном вакууме. Возможно, такая ситуация возникла, потому что эту тему довольно сложно объяснить, а может быть, мы просто стыдимся признаваться в использовании хаков, упрощений и хитростей, которые мы вносим по сравнению с «правильной», реалистичной симуляцией физики. Как бы ни обстояло дело, видеоигры имеют уникальные проблемы в симуляции транспорта, а значит, об этом стоит писать. Это захватывающая тема, относящаяся к физике, работе с камерой, звуку, спецэффектам, а также к восприятию и психологии человека.

Я решил сначала поговорить о судах, потому что недавно работал с ними; ещё я обнаружил, что их динамика не совсем понимается даже на уровне исследований (хотя многое и понятно). Модели и теории формулируются таким образом, что их становится сложно применить непосредственно в видеоиграх. Или же они требуют очень ресурсоёмких методов симуляции, которые практически невозможно контролировать и адаптировать под причудливые потребности разработчиков и игроков. Но можно написать упрощённую модель, которая учитывает важные параметры судна. В этом определённо есть доля искусства, «прыжка веры» и небольшая доля «творческой» физики, которая заставит Кельвина и Стокса перевернуться в могилах.
Читать дальше →
Всего голосов 97: ↑97 и ↓0+97
Комментарии30

Теория и практика парсинга исходников с помощью ANTLR и Roslyn

Время на прочтение23 мин
Количество просмотров40K

В нашем проекте PT Application Inspector реализовано несколько подходов к анализу исходного кода на различных языках программирования:


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

Наш цикл статей посвящен структуре и принципам работы модуля сигнатурного поиска (PM, pattern matching). Преимущества такого анализатора — скорость работы, простота описания шаблонов и масштабируемость на другие языки. Среди недостатков можно выделить то, что модуль не в состоянии анализировать сложные уязвимости, требующие построения высокоуровневых моделей выполнения кода.



К разрабатываемому модулю были, в числе прочих, сформулированы следующие требования:


  • поддержка нескольких языков программирования и простое добавление новых;
  • поддержка анализа кода, содержащего синтаксические и семантические ошибки;
  • возможность описания шаблонов на универсальном языке (DSL, domain specific language).

В нашем случае все шаблоны описывают какие-либо уязвимости или недостатки в исходном коде.


Весь процесс анализа кода может быть разбит на следующие этапы:


  1. парсинг в зависимое от языка представление (abstract syntax tree, AST);
  2. преобразование AST в независимый от языка унифицированный формат;
  3. непосредственное сопоставление с шаблонами, описанными на DSL.

Данная статья посвящена первому этапу, а именно: парсингу, сравнению функциональных возможностей и особенностей различных парсеров, применению теории на практике на примере грамматик Java, PHP, PLSQL, TSQL и даже C#. Остальные этапы будут рассмотрены в следующих публикациях.

Читать дальше →
Всего голосов 37: ↑34 и ↓3+31
Комментарии19

Все о коллекциях в Oracle

Время на прочтение12 мин
Количество просмотров270K
Статья имеет довольно таки тезисный стиль. Более подробное содержание можно найти в приложенном внизу статьи видео с записью лекции по коллекциям Oracle.

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

Таким же образом коллекции используются и в Oracle.

Содержание статьи



Шокирующие детали про коллекции в Oracle
Всего голосов 19: ↑17 и ↓2+15
Комментарии9

Как происходит рендеринг кадра видеоигры

Время на прочтение5 мин
Количество просмотров66K
Deus Ex Human Revolution — это компьютерная игра 2011 года, которая является более успешным продолжением оригинальной Deus Ex, чем Invisible War. Но этот пост не о качестве игры, а о демонстрации её технических принципов. Адриан Курреж провёл несколько часов за реверс-инжинирингом, пытаясь понять с помощью инструмента Renderdoc, как происходит обработка каждого из кадров Human Revolution. Затем Адриан изложил результаты в своём блоге.
Осторожно, трафик
Всего голосов 101: ↑98 и ↓3+95
Комментарии8

Основы боевой системы в играх

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



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

В результате, благодаря приобретенному опыту удалось написать свод правил. Соблюдение правил поможет вам воплотить мощную боевую механику в ваших играх.
Узнать все секреты
Всего голосов 57: ↑43 и ↓14+29
Комментарии12

Оптимизация алгоритма проверки условия Делоне через уравнение описанной окружности и его применение

Время на прочтение4 мин
Количество просмотров14K
Расскажу секрет о том, как быстро проверить выполнение условия Делоне для двух треугольников.
Собственно сама оптимизация описана немного ниже(см.«Оптимизация алгоритма проверки условия Делоне через уравнение описанной окружности»), но расскажу обо всем по порядку.

В моем случае триангуляция применяется в трассировке изображения, для разбиения плоскости на примитивные сектора (треугольники). Как известно, она делится также на несколько этапов: корректировка, выявление границ, обход границ, заметание контуров. Это в самом общем виде. Я бы хотел остановиться, думаю, на самом сложном этапе: заметание плоскости.
Итак приступим
Всего голосов 14: ↑11 и ↓3+8
Комментарии61

Как работает мозг?

Время на прочтение8 мин
Количество просмотров119K
Этот пост написан по мотивам лекции Джеймса Смита, профессора Висконсинского университета в Мадисоне, специализирующегося в микроэлектронике и архитектуре вычислительных машин.

История компьютерных наук в целом сводится к тому, что учёные пытаются понять, как работает человеческий мозг, и воссоздать нечто аналогичное по своим возможностям. Как именно учёные его исследуют? Представим, что в XXI веке на Землю прилетают инопланетяне, никогда не видевшие привычных нам компьютеров, и пытаются исследовать устройство такого компьютера. Скорее всего, они начнут с измерения напряжений на проводниках, и обнаружат, что данные передаются в двоичном виде: точное значение напряжения не важно, важно только его наличие либо отсутствие. Затем, возможно, они поймут, что все электронные схемы составлены из одинаковых «логических вентилей», у которых есть вход и выход, и сигнал внутри схемы всегда передаётся в одном направлении. Если инопланетяне достаточно сообразительные, то они смогут разобраться, как работают комбинационные схемы — одних их достаточно, чтобы построить сравнительно сложные вычислительные устройства. Может быть, инопланетяне разгадают роль тактового сигнала и обратной связи; но вряд ли они смогут, изучая современный процессор, распознать в нём фон-неймановскую архитектуру с общей памятью, счётчиком команд, набором регистров и т.п. Дело в том, что по итогам сорока лет погони за производительностью в процессорах появилась целая иерархия «памятей» с хитроумными протоколами синхронизации между ними; несколько параллельных конвейеров, снабжённых предсказателями переходов, так что понятие «счётчика команд» фактически теряет смысл; с каждой командой связано собственное содержимое регистров, и т.д. Для реализации микропроцессора достаточно нескольких тысяч транзисторов; чтобы его производительность достигла привычного нам уровня, требуются сотни миллионов. Смысл этого примера в том, что для ответа на вопрос «как работает компьютер?» не нужно разбираться в работе сотен миллионов транзисторов: они лишь заслоняют собой простую идею, лежащую в основе архитектуры наших ЭВМ.

Моделирование нейронов


Кора человеческого мозга состоит из порядка ста миллиардов нейронов. Исторически сложилось так, что учёные, исследующие работу мозга, пытались охватить своей теорией всю эту колоссальную конструкцию. Строение мозга описано иерархически: кора состоит из долей, доли — из «гиперколонок», те — из «миниколонок»… Миниколонка состоит из примерно сотни отдельных нейронов.



По аналогии с устройством компьютера, абсолютное большинство этих нейронов нужны для скорости и эффективности работы, для устойчивости ко сбоям, и т.п.; но основные принципы устройства мозга так же невозможно обнаружить при помощи микроскопа, как невозможно обнаружить счётчик команд, рассматривая под микроскопом микропроцессор. Поэтому более плодотворный подход — попытаться понять устройство мозга на самом низком уровне, на уровне отдельных нейронов и их колонок; и затем, опираясь на их свойства — попытаться предположить, как мог бы работать мозг целиком. Примерно так пришельцы, поняв работу логических вентилей, могли бы со временем составить из них простейший процессор, — и убедиться, что он эквивалентен по своим способностям настоящим процессорам, даже хотя те намного сложнее и мощнее.
Читать дальше →
Всего голосов 66: ↑64 и ↓2+62
Комментарии38

Сети для самых маленьких. Часть десятая. Базовый MPLS

Время на прочтение45 мин
Количество просмотров383K
Сеть нашей воображаемой компании linkmeup растёт. У неё есть уже магистральные линии в различных городах, клиентская база и отличный штат инженеров, выросших на цикле СДСМ.
Но всё им мало. Услуги ШПД — это хорошо и нужно, но есть ещё огромный потенциальный рынок корпоративных клиентов, которым нужен VPN.
Думали ребята над этим, ломали голову и пришли к выводу, что никак тут не обойтись без MPLS.

Если мультикаст был первой темой, которая требовала некоторого перестроения понимания IP-сетей, то, изучая MPLS, вам точно придётся забыть почти всё, что вы знали раньше — это особенный мир со своими правилами.



Сегодня в выпуске:


А начнём мы с вопроса: «Что не так с IP?»

Читать дальше →
Всего голосов 72: ↑72 и ↓0+72
Комментарии49

Локализация ISO/IEC 14977: 1996(E) (Extended BNF)

Время на прочтение1 мин
Количество просмотров3.1K
Доброго времени суток.

Перевёл себе для работы Стандарт ISO/IEC 14977: 1996(E), описывающий Extended BNF.

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

С уважением, Андрей.
Читать дальше →
Всего голосов 8: ↑7 и ↓1+6
Комментарии0

Как не стоит вычислять матричную экспоненту

Время на прочтение8 мин
Количество просмотров32K
Пост написан под влиянием поста пользователя pchelintsev_an.

В данной статье я постараюсь рассказать, с какими вычислительными трудностями можно столкнуться, если пойти по «наивному» пути вычисления матричной экспоненты. Статья может быть полезна тем, кто хотел бы познакомиться с вычислительной математикой, но уже знаком с такими понятиями как система обыкновенных дифференциальных уравнений и задача Коши. Эксперименты проводились с использованием системы GNU Octave.
Что еще за матричная экспонента
Всего голосов 47: ↑45 и ↓2+43
Комментарии21

Android NDK: работа с OpenSL ES

Время на прочтение11 мин
Количество просмотров15K
День добрый, Хабражители.

Я ранее писал про OpenAL. Позже товарищ zagayevskiy написал хорошую статью по OpenSL ES. В одной из наших игр, дабы не переписывать весь код по работе со звуком, мы не стали переписывать всё на OpenSL ES (при порте на Android). В игре использовалось не так много звуков, поэтому проблем с OpenAL не было. А вот в последней игре у нас использовалось много звуков (специфика игры обязывает), вот тут-то мы и столкнулись с большой проблемой (задержки при воспроизведении — меньшая из них). Было решено переписать всё на OpenSL ES. Для этого я написал парочку враперов, про которые уже рассказывал. Решил поделиться этим и на хабре, может кому-то пригодится.

  1. Краткое описание OpenSL ES.
  2. Аудио контент.
  3. Немного про обёртки.
  4. Принцип работы с объектами.
  5. Инициализация библиотеки (контекста).
  6. Работа со звуками.
  7. Проигрывание PCM.
  8. Проигрывание сжатых форматов.
  9. Заключение.
  10. Доп. информация.

Читать дальше →
Всего голосов 18: ↑17 и ↓1+16
Комментарии2

10 ответов на вопросы по работе с заказчиком

Время на прочтение1 мин
Количество просмотров32K
После прошедшего PM-Weekend удалось поймать selikhovkin и попросить записать несколько видео по самым популярным вопросам про управление проектами. Сегодня — первое видео:

10 ответов на вопросы про работу с заказчиком




В рамках видео Иван тезисно раскрыл следующие вопросы:
  1. Как заинтересовать бизнес в повышении зрелости системы управления?
  2. Методы по формированию ожиданий у заказчика по проекту и их использование
  3. Как понять, что хочет заказчик?
  4. Как удерживать заказчика от раздувания требований?
  5. Как научить заказчика доверять разработчику?
  6. Какие методики/методологии ведения проектов и общения с заказчиком существуют?
  7. Саботаж сотрудников заказчика (как бороться)?
  8. Как сообщить заказчику, что проект идет не по плану, какие фразы использовать, как сгладить впечатление?
  9. Особенности работы с гос.заказчиками
  10. Что делать менеджеру на проекте, который заказчик пускает на самотек?

Читать дальше →
Всего голосов 34: ↑28 и ↓6+22
Комментарии2

OpenFOAM на практике

Время на прочтение3 мин
Количество просмотров27K

Open FOAM


image

OpenFOAM — свободно распространяемый инструментарий вычислительной гидродинамики для операций с полями (скалярными, векторными и тензорными). На сегодня является одним из «законченных» и известных приложений, предназначенных для FVM-вычислений.В частности пакет позволяет решать задачи гидродинамики ньютоновских и неньютоновских вязких жидкостей как в несжимаемом, так и сжимаемом приближении с учётом конвективного теплообмена и действием сил гравитации. Для моделирования турбулентных течений возможно использование RANS-моделей, LES- и DNS-методов. Возможно решение дозвуковых, околозвуковых и сверхзвуковых задач.
Читать дальше →
Всего голосов 28: ↑28 и ↓0+28
Комментарии6

Установка OpenFOAM на Ubuntu 14.04

Время на прочтение3 мин
Количество просмотров14K

OpenFOAM — свободно распространяемый инструментарий вычислительной гидродинамики для операций с полями (скалярными, векторными и тензорными). На сегодня является одним из «законченных» и известных приложений, предназначенных для FVM-вычислений.В частности пакет позволяет решать задачи гидродинамики ньютоновских и неньютоновских вязких жидкостей как в несжимаемом, так и сжимаемом приближении с учётом конвективного теплообмена и действием сил гравитации. Для моделирования турбулентных течений возможно использование RANS-моделей, LES- и DNS-методов. Возможно решение дозвуковых, околозвуковых и сверхзвуковых задач.

На данный момент инсталляционные пакеты доступны для следующих версий ОС
  • 12.04 LTS codename precise
  • 12.10 codename quantal
  • 13.04 codename raring
  • 13.10 codename saucy

Однако, инсталляционный пакет ОС Ubuntu 14.04 отсутствует. Поэтому для версии 14.04, необходимо самостоятельно собрать OpenFOAM 2.3 Это является достаточно не простой задачей для новичков, которые недавно используют данную операционную систему.
Этому и посвящена статья.
Читать дальше →
Всего голосов 26: ↑23 и ↓3+20
Комментарии8

JBrainfuck — Пишем компилятор Brainfuck под Java VM

Время на прочтение13 мин
Количество просмотров22K
Меня давно интересовал вопрос написания своего компилятора под Java VM, но было недостаточно опыта, дабы сделать это. Да и как-то руки не доходили, а недавно все же решил разобраться в этой теме и заодно рассказать о своем опыте создания компилятора под эту VM.

В качестве реализуемого языка возьмем Brainfuck. Он прост в реализации, что отлично подходит для изучения данной темы, но сначала предоставлю вам свою реализацию.

JBrainfuck — оптимизирующий интерпретатор и компилятор Brainfuck под Java VM. Благодаря JIT обладает высокой производительностью.


Ну что, приступим?
Всего голосов 49: ↑49 и ↓0+49
Комментарии18

Информация

В рейтинге
Не участвует
Зарегистрирован
Активность