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

Вступление

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

Четверной обмен

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

    if (val[0] > val[1])
    {
        tmp[0] = val[0];
        val[0] = val[1];
        val[1] = tmp[0];
    }

В четверном обмене происходит сортировка с помощью четырёх подменных переменных (своп). На первом этапе четыре переменные частично сортируются в четыре своп-переменные, на втором этапе они полностью сортируются обратно в четыре исходные переменные.

Алгоритм сортировки quadsort - 1
Этот процесс показан на диаграмме выше.
Читать полностью »

Идём в глубь острова сокровищ с названием "Алгоритм".

Title

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

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

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

Как мы забрали у человека сито и помогли мельнице - 1

В 1949 году советский пилот-геологоразведчик Михаил Сургутанов пролетал над одной из территорий Казахстана (урочище Сарбай) и, взглянув на компас, заметил, что стрелка стала игнорировать Север и зажила своей жизнью. Да, как в кино при обнаружении каких-то магнитных аномалий.
Читать полностью »

Обезл***вание д***ных — это не просто рандомизация - 1

В банке есть проблема: нужно давать доступ к базе данных разработчикам и тестировщикам. Есть куча клиентских данных, которые по PCI DSS требованиям Центробанка и законам о персональных данных вообще нельзя использовать для раскрытия на отделы разработки и тестирования.

Казалось бы, достаточно просто поменять всё на какие-нибудь несимметричные хеши, и всё будет хорошо.

Так вот, не будет.

Дело в том, что база данных банка — это множество связанных между собой таблиц. Где-то они связаны по ФИО и номеру счёта клиента. Где-то по его уникальному идентификатору. Где-то (тут начинается боль) через хранимую процедуру, которая вычисляет сквозной идентификатор на основе этой и соседней таблицы. И так далее.

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

То есть прежде чем всё это обезличить, сначала надо разобраться в базе данных. Читать полностью »

Привет! Представляю вашему внимаю перевод статьи из журнала APC.

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

Однако недавно в Google Play появилось новое бесплатное приложение под названием «DataLearner», с помощью которого можно добывать данные. Оно не требует внешних ресурсов и доступа с полномочиями суперпользователя.

Вычислительные ресурсы смартфонов

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

У компьютерного обучения есть свои уровни сложности. Если представить, что такая недавно появившаяся техника глубокого обучения, как свёрточная нейросеть (CNN) – это автомобиль с высокой удельной мощностью, то другие техники, например, дерево поиска решений и многие прочие «лесные» методы обучения – это горячие «хэтчбеки». Они показывают отличные результаты, быстры и легки даже при ограниченных вычислительных возможностях CPU.
Читать полностью »

В этой статье я не буду рассказывать о новых фичах генератора парсера — я достаточно описал его в предыдущих частях. Вместо этого хочу рассказать что я делал на 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-подобную грамматическую нотацию, которая мне до сих пор очень нравится.

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


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