Рубрика «алгоритм»

В этой статье я не буду рассказывать о новых фичах генератора парсера — я достаточно описал его в предыдущих частях. Вместо этого хочу рассказать что я делал на Core Developer Sprint на прошлой неделе, прежде чем всё сотрётся из моей памяти. Хотя большая часть материала так или иначе всё равно касается PEG. Так что мне придётся показать некоторый код, который задаёт направление в реализации PEG-парсера для Python 3.9.

Каждый год в течение последних четырёх лет группа разработчиков ядра Python собирается на недельный спринт в экзотическом месте. Эти спринты спонсируются принимающей стороной и PSF. Первые два года мы были у Facebook в Mountain View, в прошлом году была очередь Microsoft в Bellevue, а на этот спринт выбрали офис Bloomberg в Лондоне. (Должен сказать, что он выглядит довольно круто.) Слава core-разработчику Pablo Galindo Salgado за организацию!

Читать полностью »

После того, как я собрал все части генератора PEG-парсеров воедино в предыдущем посте, я готов показать как реализовать и некоторые другие интересные штуки.

Мы рассмотрим следующие фичи PEG:

Читать полностью »

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

Содержание серии статей о PEG-парсере в Python

Рассмотрим это гипотетическое правило грамматики:

expr: expr '+' term | term

Читать полностью »

Вдохновленный лишь частичным пониманием PEG, я решил попробовать его реализовать. Результат может получиться и не самым лучшим среди парсеров PEG общего назначения — их уже много (например, TatSu написан на Python и генерирует код Python) — но это хороший способ разобраться в PEG. В дальнейшем я хочу заменить им текущую реализацию парсера в CPython.

Содержание серии статей о PEG-парсере в Python

  • PEG парсеры
  • Реализация PEG парсера
  • Генерация PEG парсера
  • Визуализация работы PEG парсера
  • Леворекурсивные PEG грамматики
  • Добавление экшенов в грамматику PEG
  • Реализация остальных возможностей PEG
  • PEG на Core Developer Sprint

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

Читать полностью »

Несколько лет назад меня кто-то спросил имеет ли смысл превести Python на PEG-парсер (или на грамматику PEG; я не помню точно кто и когда это было). Тогда я немного посмотрел на него, но так и не пришёл к какому-либо выводу, а потому и отбросил эту тему. Недавно я узнал больше о PEG (Parsing Expression Grammars, грамматике по парсингу выражений), и теперь я думаю, что это интересная альтернатива самописному генератору парсеров, который был разработан 30 лет назад, когда только начинал работать над Python. Я назвал его «pgen», и это был, наверно, первым фрагментом кода, который я написал для Python.

Содержание серии статей о PEG-парсере в Python

  • PEG парсеры
  • Реализация PEG парсера
  • Генерация PEG парсера
  • Визуализация работы PEG парсера
  • Леворекурсивные PEG грамматики
  • Добавление экшенов в грамматику PEG
  • Реализация остальных возможностей PEG
  • PEG на Core Developer Sprint

Причина, по которой я сейчас заинтересован в парсере PEG, заключается в том, что меня несколько раздражают ограничения pgen. Он построен на собственной реализации LL(1), которая имеет ряд допущений. Например, мне не нравились грамматические правила, которые могли бы генерировать пустые строки, поэтому я запретил их. И тем самым упростил алгоритм для создания таблиц синтаксического анализа. Я также изобрёл свою собственную EBNF-подобную грамматическую нотацию, которая мне до сих пор очень нравится.

Читать полностью »

В данной статье будет подробно рассмотрен алгоритм блочного шифрования, определенный в ГОСТ Р 34.12-2015 как «Кузнечик». На чем он основывается, какова математика блочных криптоалгоритмов, а так же как реализуется данный алгоритм в java.

Кто, как, когда и зачем разработал данный алгоритм останется за рамками статьи, так как в данном случае нас это мало интересует, разве что:

КУЗНЕЧИК = КУЗнецов, НЕЧаев И Компания.

Криптографический алгоритм «Кузнечик»: просто о сложном - 1

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

Привет!

В этой публикации я расскажу о статье автора Jinmo Kim: "Maze Terrain Authoring System in Immersive Virtual Reality for New Visual Realism". Она была опубликована 4.04.2019. Полный текст статьи можно посмотреть здесь.

Краткое описание системы

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

Предложенная система генерации ландшафта лабиринта состоит из трех основных функций:

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

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

Читать полностью »

Недавно мне попалась классическая задачка для собеседований: поиск максимального числа точек, стоящих на прямой линии (на плоскости, координаты целочисленные). В голову сразу пришла идея полного перебора, которая имеет очевидную сложность по времени в O(n^2), но мне показалось, что здесь обязано быть что-то ещё, хоть какая-то альтернатива в O(n*log(n)). Через полчаса нашлось даже нечто лучшее!

image
Читать полностью »

Как Amazon выбирает свои, казалось бы, случайные предложения дня. И почему за ними так гонятся продавцы - 1

Amazon захватила 50% интернет-рынка в Америке. В прошлом году за пятинедельный период со Дня благодарения (22 ноября в США) 89% расходов клиентов крупнейших торговых площадок в Штатах пришлось на этот один интернет-магазин. За 2017-й год акции компании совершили ралли на 55%, в 2018-м – еще на 30%. Причина простая: у компании лучшая инфраструктура, плюс она знает, что давать покупателям. Независимые продажники, третьи лица, обеспечивают до 70% покупок на сайте. И компании нужно знать, какие из них выдавать в поисковой выдаче, и на какие устраивать скидки.

Из сотен миллионов товаров, размещенных на площадке, каждый день компания отбирает всего пару тысяч. Какими параметрами при этом руководствуется компания, чтобы обеспечить максимальные продажи? Как выбирает этот 0,1% подходящих вещей? Или берет товары наугад, рискуя разочаровать покупателей?Читать полностью »

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

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

Стало интересно выполнить анализ применимости этих понятий для общепринятых парадигм программирования, например для ООП. Хорошо, если результат этой работы будет полезен и Вам.

image

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js