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

Эволюция архитектуры торгово-клиринговой системы Московской биржи. Часть 2 - 1

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

Чтобы передать сообщение от базовой станции мобильному устройству (и наоборот), электромагнитной волне приходится преодолевать значительное количество препон: отражения, преломления, рассеивания, затенения, доплеровские смещения частот и так далее. Во-первых, все эти воздействия принято называть мультипликативными (от англ. multiplication — умножение) — по математической модели таких воздействий. А, во-вторых, можно собрать под общим термином замирания (fading).

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

И некоторые решения нашли широкое распространение. Скажем больше: почти все из них, так или иначе, связаны с понятием разнесения (diversity).

MIMO spatial diversity: Аламоути, DET и прочее пространственное разнесение - 1Читать полностью »

Дональд Кнут — учёный в области информатики, который настолько заботится о правильности своих книг, что предлагает один шестнадцатеричный доллар ($2,56, 0x$1,00) за любую найденную «ошибку», где ошибкой считается всё, что «технически, исторически, типографически или политически неправильно». Я очень хотел получить чек от Кнута, поэтому решил поискать ошибки в его выдающемся труде «Искусство программирования» (TAOCP). Удалось найти три. Верный слову, Кнут прислал чек на 0x$3,00.

Я получил от Кнута чек на 0x$3,00 - 1

Как видите, это не настоящий чек. Раньше Кнут отправлял реальные чеки, но прекратил в 2008 году из-за безудержного мошенничества. Теперь он рассылает «личные депозитные сертификаты» в банке Сан-Серрифф (BoSS). Он говорит, что готов выслать реальные деньги в случае необходимости, но, похоже, это слишком хлопотно.
Читать полностью »

В этом посте описывается генератор уровней для моей игры-головоломки Linjat. Пост можно читать и без подготовки, но он легче усвоится, если сыграть в несколько уровней. Исходный код я выложил на github; всё обсуждаемое в статье находится в файле src/main.cc.

Примерный план поста:

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

Правила

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

Создание процедурного генератора головоломок - 1

Цель игрока — прочертить вертикальную или горизонтальную линию через каждое из чисел при соблюдении трёх условий:

  • Линия, идущая через число, должна иметь ту же длину, что и число.
  • Линии не могут пересекаться.
  • Все точки необходимо закрыть линиями.

Пример решения:

Создание процедурного генератора головоломок - 2

Ура! Дизайн игры готов, UI реализован, и теперь единственное, что осталось — найти несколько сотен хороших головоломок. А для подобных игр обычно не имеет смысла пытаться создавать такие головоломки вручную. Это работа для компьютера.
Читать полностью »

Поиск похожих изображений, разбор одного алгоритма - 1

Пришлось мне недавно решать задачку по оптимизации поиска дубликатов изображений.

Существующее решение работает на довольно известной библиотеке, написанной на Python, — Image Match, основанной на работе «AN IMAGE SIGNATURE FOR ANY KIND OF IMAGE» за авторством H. Chi Wong, Marshall Bern и David Goldberg.

По ряду причин было принято решение переписать всё на Kotlin, заодно отказавшись от хранения и поиска в ElasticSearch, который требует заметно больше ресурсов, как железных, так и человеческих на поддержку и администрирование, в пользу поиска в локальном in-memory кэше.

Для понимания того, как оно работает, пришлось с головой погружаться в «эталонный» код на Python, так как оригинальная работа порой не совсем очевидна, а в паре мест заставляет вспомнить мем «как нарисовать сову». Собственно, результатами этого изучения я и хочу поделиться, заодно рассказав про некоторые оптимизации, как по объёму данных, так и по скорости поиска. Может, кому пригодится.
Читать полностью »

В комментариях к одному из прошлых постов о решете Эратосфена был упомянут этот короткий алгоритм из Википедии:

Алгоритм 1:

1: для i := 2, 3, 4, ..., до n: 
2:  если lp[i] = 0:
3:       lp[i] := i
4:       pr[] += {i}
5:   для p из pr пока p ≤ lp[i] и p*i ≤ n:
6:       lp[p*i] := p
Результат:
 lp - минимальный простой делитель для кажого числа до n
 pr - список всех простых до n.

Алгоритм простой, но не всем он показался очевидным. Главная же проблема в том, что на Википедии нет доказательства, а ссылка на первоисточник (pdf) содержит довольно сильно отличающийся от приведенного выше алгоритм.

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

Введение

function getAbsolutelyRandomNumer() {
        return 4; // returns absolutely random number!
}

Как и в случае с концепцией абсолютно стойкого шифра из криптографии, реальные протоколы “Publicly Verifiable Random Beacon” (далее PVRB) лишь пытаются максимально приблизиться к идеальной схеме, т.к. в реальных сетях в чистом виде она неприменима: договариваться надо строго об одном бите, раундов должно быть много, а все сообщения должны быть идеально быстрыми и всегда доставляться. Разумеется, в реальных сетях это не так. Поэтому, при проектировании PVRB под конкретные задачи в современных блокчейнах, помимо невозможности контроля получаемого рандома и криптографической стойкости, возникает еще много чисто архитектурных и технических проблем.

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

В мире наступили восьмидесятые. IBM захватывал рынок профессиональных компьютеров своими PC и PC XT — родоначальниками всех современных настольных компьютеров. Джобс одну за другой выпускал новые модели Apple. Commodore 64 и ZX Spectrum гремели по миру. А в это время в советском блоке продолжали выпускаться Ascota 170 — механические компьютеры родом из начала пятидесятых. Почему-то, в рунете (да и в остальном интернете тоже) мало говорят об этих удивительных машинах, едва ли не единственных серийно (больше трёхсот тысяч с 1955 до 1983 годов) выпускавшихся Тьюринг-полных механических компьютерах. Я и сам о них узнал только тогда, когда Аскота случайно попала мне в руки.
Надеюсь, моя статья сможет изменить это.

Аскота 170 — механический компьютер и советский палеоэндемик - 1
Моя Аскота закончила считать квадратный корень из 2.
Читать полностью »

Привет.

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

Как мы боремся с копированием контента, или первая adversarial attack в проде - 1

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

«Мы начинаем разработку новой игры, и нам нужна классная вода. Такую сможешь?»

, — cпросили меня. «Да не вопрос! Конечно, смогу», — ответил я, но голос предательски задрожал. «А, еще и на Unity?», — и мне стало понятно, что впереди очень много работы.
Читать полностью »