?

Log in

No account? Create an account
 

swizard

About Свежие записи

У нас есть Rust, поэтому C++ больше не нужен. 19 окт, 2017 @ 17:47

Просто чудесный пост у thesz, наглядно демонстрирующий мой лозунг из сабжа.

Давайте пройдёмся по пунктам:

> Большое неудобство, однако, составляет отсутствие подсказок компилятора в сообщении об ошибке

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

> но сама необходимость думать о том, как правильно создавать объект, отнимает достаточно сил

А в Rust отсутствует возможность "неправильно" создать объект.

> должен ли я бросать исключение

В Rust нет исключений, а есть только один "идеоматический" (как это по-русски — общепринятый?) способ сигнализировать об ошибке: вернуть Result.

> могу ли я оставить объект не полностью или не корректно созданным

В Rust невозможно (без использования unsafe) не полностью инициализировать объект.

Ну и так далее.

На самом деле, в Rust очень многое сделано сразу правильно, по сравнению с C++. Ведь его же создавали люди, которые много программировали на C++ :) В Rust мы не встретим таких понятий, как "правило пяти", "swap", "pimpl", etc, потому что язык уже сделан как нужно.

Кроме того, в Rust используется только один общепринятый стиль написания кода (вспоминаем все эти венгерские нотации, все эти противоречащие друг другу c++ guidelines от гугл, тоёты, микрософта и тд), существует один всемогущий cargo c сайтом crates.io (вспоминаем цмейк, автомейк, сконс и тд), а также rustdoc, rustup, rustfmt, и тд и тп.

Повторюсь (уже в третий раз в этом блоге): нет никаких причин в настоящее время программировать что-то новое на C++, потому что есть Rust. Могут быть причины, чтобы выбрать вместо Rust, там, какой-нибудь Haskell, Scala, Erlang, да даже Common Lisp. Но не может быть никаких причин, чтобы вместо Rust выбрать C++.


а вот, например, ещё вакансии 4 сент, 2017 @ 15:40

Собственно, образовалась ещё вакансия. Нам нужно несколько человек, задач много, они все (как это водится) инновационные и интересные, минимум легаси, максимум r&d, ну и так далее.

Формальное описание таково:


От кандидата требуется:
  • Опыт работы с большими объёмами данных.
  • Знание основных паттернов проектирования систем обмена сообщениями.
  • Опыт сетевого программирования.
  • Навыки работы с linux.
Плюсами будут:
  • Знание теории, связанной с bigdata (статистика, машинное обучение, анализ данных, вероятностные алгоритмы, кластеризация, и т.п.)
  • Знание, или устойчивое желание и возможность освоить:
    • Язык программирования Rust
    • Язык программирования Erlang и платформу OTP
  • Владение функциональной парадигмой программирования.
  • Опыт работы с:
    • RabbitMQ
    • Postgres
    • Apache Cassandra
    • Redis

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

Если интересна вакансия, пишите мне на почту (с резюме в аттаче), если знаете кого-то, кому может быть она интересна — рассказывайте! Общие вопросы пишите лучше сюда в комменты, чтобы мне не копипастить по письмам ответы.


Послеконкурсное 31 авг, 2017 @ 18:16
Отчёт о конкурсе: часть первая и вторая.

Тем временем подъехали результаты для lightning- и основного раундов, пока ещё не окончательные, но с нашими достижениями там уже всё понятно =)

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

Все записи игр, результаты которых пошли в зачёт, можно посмотреть в симуляторе. Я посмотрел :) Увиденное принесло чёткое понимание, что свой визуализатор надо было делать с самого начала. Очень многое сразу бросается в глаза, когда видишь картину происходящего в динамике. Собственно, отсутствие визуализатора — это первая наша серьёзная ошибка.

Далее, просмотр записей игр и чтение отчётов выявили вторую серьёзную ошибку (на этот раз она чисто моя): я слишком много сил уделил фьючерсам. Да, у меня, в итоге, родился очень неплохой алгоритм, благодаря которому фьючерсы достаточно часто удаётся выполнить. Проблема в том, что на маленьких и средних картах выгода от закрытого фьючерса оказывается совсем небольшой, и намного лучшей идеей было бы вложиться в стройку обычного маршрута подлиннее (опять же, это безрисково). На некоторых реплеях видно, что, успешно выполнив два фьючерса, наш бот занимает второе место, уступив решению, которое просто тупо строит дорогу.

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

Единственным дополнением, которые однозначно воспользовались все — это опционы (хотя походу Unagi даже их не использовали, тем не менее, вторая позиция в рейтинге), а вот splurges были проигнорированы. Я вообще не смог найти ни одного реплея, где кто-либо использовал бы бахвальство — не очень понятно, какого эффекта от него ждали организаторы.

Ну да ладно, главное — выводы сделаны (лол, прямо дежавю), в следующем году надерём японцам задницу!


ICFPC 2017: Ticket to Ride на Rust (вторая часть) 29 авг, 2017 @ 02:04
Продолжение. Первая часть здесь.

День второй.

Я возвращаюсь в чат в полдень, к этому времени там уже произошло:

  1. ничего.
Sectoid садится программировать автоматическую сборку сабмишна по триггеру от репозитория, когда на код ставится определённый тег. Сам я не занимаюсь ничем в течении полутора часов, но в чате усиленно делаю сложные щи. В 13:33 мне это надоедает, и я решаю спрограммировать солвер, который соединяет на карте друг с другом рудники: solvers::link_mines.

В 13:44 я обнаруживаю в списках игроков на серверах вот такое имя: "A Storm of Minds: Mine Connect Claimer" -- понимаю, что я на верном пути =) Дальше мы пытаемся придумать какую-нибудь простую, но более эффективную стратегию, а параллельно я усиленно программирую link_mines.

В 14:17 организаторы объявляют продление лайтнинга на час (в качестве компенсации за то, что начало конкурса задержалось из-за обвала сайта с заданием). Это круто, потому что я как раз начал усиленно переживать, что не успеваю к трём. В солвере я, помимо соединения шахт, планирую один из этих маршрутов объявлять фьючерсом. Но вот засада -- не могу найти карту с фьючерсами, прошу команду помочь.

В 14:33 солвер у меня научился соединять шахты дейкстрой, осталось срочно придумать, что делать, когда все шахты на карте соединены. Решаю пока просто захватывать оставшиеся реки в случайном порядке.

В 15:01 у меня всё готово, прошу в чате всех помочь с тестированием.

RUST_LOG=lambda_punter=debug,lambda_punter_online=debug cargo run --release -- --server-port 9024 link_mines
В процессе оказывается, что играет оно плохо: пока я тяну дорогу, враги быстро перекрывают подступы к шахтам. В срочном порядке бранчуюсь и начинаю кодить вариант, который строит маршрут не от одной точки другой, а от обеих сразу к центру маршрута.

В 15:10 готово, все продолжаем тестировать. Через 10 минут Sectoid находит баг в декодере пакетов: оказывается, что количество очков может быть отрицательным (например, за проваленный фьючерс). На серверах тем временем играют боты каких-то товарищей под таким именем: "WISE_PIDOR_SOLUTION" :) В целом, всё остальное вроде ок, и в 15:33 Sectoid пошёл собирать сабмишн.

В 15:39 обнаруживаю карту "Oxford sparse" на которой только одна шахта: на ней солвер link_mines отказывается работать :) Срочно бросаюсь делать фикс. В 15:42 фикс готов, идёт вывариваться новый сабмишн. В 15:45 решаю срочно улучшить поведение, когда все основные цели солвер выполнил. В 15:53 у меня готов очередной фикс. Но там баг! К 15:56 готов багфикс. Пока решали, сабмитить или нет, к 15:59 я обнаружил ещё один баг! Короче пофиг, решаем больше не дёргаться.

16:00: lightning division типа закончен. Но что-то везде тишина.

Тем временем, в 16:19 я делаю окончательный багфикс солвера. Результаты с eager punter-ами улучшились в два с половиной раза :) Решаем на авось засабмитить, вдруг это решение каким-то чудом на лайтнинг пройдёт. Ну а если нет, то и не надо. К 16:30 сабмишн уезжает, я отправляюсь обедать, а ребята там ещё в остаются в чате придумывать разнообразные стратегии победы на будущее. Sectoid решает сделать автоматическую тестировалку наших ботов об сервера организаторов.

Дальше часок мы там просто абстрактно размышляли на разные темы, а дальше на меня (как на жирафа) начала накатывать череда озарений:

  • к 17:29 я внезапно соображаю, что при построении своих маршрутов я же ведь имею право пользоваться своими уже захваченными ранее реками! Казалось бы, очевидная вещь, но по какой-то причине она мне раньше не пришла в голову. Бегу программировать.
  • к 18:46 я так же внезапно обнаруживаю, что фьючерсы (по заданию) должны начинаться в шахте, а заканчиваться не в шахте! Я же объявлял их от шахты до шахты. Бегу программировать.
  • параллельно обнаруживаю ещё пару багов, один из которых про то, что реки (A, B) и (B, A) у меня кое-где считаются разными.
К 19:30 я делаю толстый коммит в ветку post_lightning_followup, в котором ничего нового нет, просто отремонтированное старое. Sectoid в это время настраивает интерактивный хипстерский TODO через телеграм.

В 19:50 организаторы фиксят свой lamduct (по многочисленным жалобам), сделав там блокирующий режим в пайпе -- это ведь как раз то, с чем я сражался половину предыдущей ночи. Мне всегда в такие моменты немного обидно: ты типа мучался, тратил время, и потом с таким трудом одолел проблему -- а кто-то вместо этого немного поныл в чатик организаторам, и ему всё принесли готовое. Лучше б я поспал вчера :)

В 20:15 я решаю как-нибудь несложно доработать утилиту lambda_punter_online, чтобы она умела одновременно проводить сразу несколько игр на разных рандомных серверах. Эта работа немного пересекается с автоматической обстреливалкой, которую делает Sectoid, но мне вот прямо щас уже нужны какие-то массовые результаты, чтобы было представление о качестве солвера. Turtle к этому времени начинает писать кастомный сервер, но вскоре ему приходится уехать. Jtootf с Sectoid в это время садятся брейнштормить алгоритмы. Я им для затравки подробно описал как сейчас работает мой текущий солвер.

Далее мы примерно этим расслабленно занимаемся вплоть до 22:00. Из любопытных идей было порождено следующее:

  • @jtootf: стараться отстраивать те куски маршрута, которые имеют больший коэффициент связности.
  • @sectoid: выкрасть прямо из браузера graph-viewer и puntfx от организаторов (так как они грамнотно написаны и не обфусцированы), и собрать на их базе визуализатор.
В десять вечера я заканчиваю поддержку нескольких одновременных игр в lambda_punter_online на случайно выбранных серверах, и выясняется, что почти везде там мой достаточно примитивный солвер выигрывает с огромным отрывом. Конечно, понятно, что соперниками, в массе своей, оказываются eager punter-ы и экспериментальные солверы других команд, но всё равно приятно :)

Тем не менее, периодически попадаются товарищи, которые меня наказывают. Например, на random-* картах солверу достаточно быстро обрубают пути, которыми он пытается соединять рудники, и он начинает метаться по карте вместо полезной деятельности.

Постепенно lambda_punter_online отыгрывает 256 игр на разных случайных картах: получаю винрейт 82%. Через пять минут соображаю, что сервера слишком рандомно выбираются, и из-за их ограниченного количества и долгого времени ожидания на некоторых картах, возникает ситуация, когда у меня бот играет сам с собой. Иногда бывает даже до 12 моих ботов на одной карте :) Сажусь переделывать, чтобы сервера предлагались гарантированно разные.

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

К 23:05 замечаю, что сломалась игра через lambda_punter_offline -- какая-то проблема с сериализацией стейта. Оказалось, что serde_json не хочет сериализовать через #[derive(Serialize)] хэш-таблицу, где ключами являются не строки. Сажусь ремонтировать :(

К 23:51 доигрались 256 игр с условием, чтобы мои боты сами с собой не играли: винрейт почти 90%!

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

Чуть подумав, вместо того, чтобы пойти спать, я в книжке Mining Of Massive Data Sets откапываю алгоритм, который давно хотел сюда как-то применить: Girvan-Newman, про кластеризацию графа. Сама по себе кластеризация мне тут вроде ни к чему, но меня больше интересуют коэффициенты рёбер, которые показывают, сколько идёт кратчайших путей из любого узла графа в любой другой.

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

А вот так, например, отрисовывается эта же карта randomMedium.jspn с реками, интенсивность подсветки которых зависит от коэффициента betweenness.

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

В половину второго внезапно прибегает Sectoid с вопросом, можно ли разложить граф на плоскости, и если можно, то как это использовать :)

Ближе к четырём ночи я коммичу реализацию Girvan-Newman в репо вместе с тестами, и отваливаюсь спать.

День третий.

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

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

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

Два часа дня. Тыкаюсь какое-то время в игровые сервера: сильные игроки всё ещё не играют, винрейт стабильно за 90%. Делаю поддержку бахвальства в протоколе. Сажусь писать поддержку Girvan-Newman в солвере, чтобы он захватывал сначала важные реки: заодно, решаю переименовать солвер в solvers::gn (от Girvan-Newman), чтобы можно было всегда откатиться к solvers::link_mines, если что.

Народу приходит интересная идея, как в теории можно применить бахвальство: если нам не хватает времени досчитать ход, мы пасуем и сохраняем в стейт недосчитаное решение. Затем на следующем ходу досчитываем и делаем сразу ход из двух сегментов. Идея любопытная, на самом деле, но пока у нас проблема с таймаутами не стоит, ну и вообще это сложно как-то реализовывать.

16:00: Turtle бросает сервер и садится делать реплеи.

Я пока всячески апгрейжу по-мелочи solvers::gn -- по сравнению с link_mines он теперь:

  • На картах с одной шахтой выбирает себе целью построить самый длинный возможный путь, а не случайный какой-нибудь.
  • Для карты на этапе инициализации считаются betweenness-коэффициенты с помощью Girvan-Newman.
  • В случае, когда все текущие цели выполнены, выбирается честно рандомная речка для захвата, а не первая свободная.
  • В случае, когда ни один из ходов не принесёт дополнительных очков, всё равно захватывается какая-то случайная речка (до этого просто производился пас).
  • + Делаю дампалку статусов выполнения фьючерсов после окончания игры

К пяти вечера я ещё разок пробую уговорить Turtle попрограммировать на расте, конкретно портировать визуализатор из сокобана. Но он боится, не хочет :)

Ещё через полчаса раздумий, куда бы правильней применить результаты Girvan-Newman, я решаю реализовать пока свою первоначальную идею: когда приходит ход, захватывать ту речку из маршрута, которая имеет самый высокий коэффициент betweenness. По-идее, должно полегчать на картах с явно выраженными мостами: они должны теперь у меня захватываться в первую очередь.

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

К шести вечера выясняется, что на треугольнике и некоторых рандомах солвер стабильно проигрывает боту от kontur.ru. Ну вот, а ведь так хорошо всё начиналось =) Думаю, как можно улучшить наши результаты на этих картах. Есть подозрение, что у нас что-то неправильное происходит с фьючерсами.

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

  1. которые были бы максимально удалённые от исходной шахты
  2. до которых было бы проще всего добраться (минимальный шанс врагам обломать маршрут)
Самое сложное во всём этом -- это придумать, как эти два взаимоисключающих параметра совместить :)

Обнаруживаю, что lambda_punter_online при массовой игре засчитывает ничью как поражение. Исправляю. Обстрел показывает, что старый солвер link_mines показывает (вроде бы) более лучшие результаты, чем новый gn.

Turtle тем временем нарисовал на бумажке картинок и рассказывает нам своё видение стратегии победы. К сожалению, в итоге в его алгоритме что-то не срастается. В конце концов сходимся на том, что я выдаю ребятам рассчитанные betweenness коэффициенты для карты randomMedium, а сам удаляюсь по делам на пару часов. По возвращении я строго наказываю придумать мне ясный и эффективный алгоритм для объявления фьючерсов.

Возвращаюсь в половину десятого, алгоритм не придуман :) Sectoid пытается разобраться с тем, как именно работает Girvan-Newman. К половине одинадцатого предлагаю забить на придумывание алгоритма, и закончить насущные дела по реплеям, серверу и бенчмаркам.

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

  • На входе нам выдаётся карта, в которой известно количество рек, количество игроков и порядок их хода.
  • Игроки типа совершают ходы в порядке своей очереди.
  • В наш ход мы пытаемся забрать сегмент своего некоторого маршрута, который мы хотим объявить как фьючерс.
  • Противник в свой ход может с какой-то вероятностью захватить одну из оставшихся рек. Допустим, эта вероятность будет прямо пропорциональна коэффициенту betweenness реки. Логика под этим такая, что более востребованные сегменты маршрутов (рёбра, через которые проходит большинство кратчайших путей) будут нужны большему количеству игроков, чтобы построить свой маршрут.
  • Соответственно, в некоторый момент с какой-то вероятностью наш маршрут будет обломан. Очевидно, что чем дальше мы пытаемся строить этот маршрут, тем с большей вероятностью он будет обломан.
  • Умея эту вероятность находить, в конце концов, нам надо пройти по всем узлам графа и для каждого из них получить оценку, насколько реально до сюда достроить фьючерс. И уже имея эту оценку, можно принимать решение, до куда конкретно нам его имеет смысл объявлять.

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

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

Ну что ж, раз в математику мы не можем, решаю идти путём слабаков: будем брутфорсить вероятности через монте-карло. Теория такая, что раз у нас на этот раз быстрый Rust, должна быть возможность запустить достаточное количество симуляций игр, чтобы получились нужные числа. Короче, сажусь постепенно что-то делать.

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

В половину первого ночи ворвался Sectoid с сообщением, что у него заработал бенчмарк, и мы теперь можем типа объективно оценивать солвер. Запускаем играть gn. Пример выхлопа выглядит примерно так:

^CGot INTERRUPT. Finalizing...
+---------------------+-------+--------+-----------------+-----------+----------------+---------+
|         MAP         | GAMES | ERRORS |      SCORE      | METASCORE | TOTALMETASCORE | WINRATE |
+---------------------+-------+--------+-----------------+-----------+----------------+---------+
| sample              | 10    | 0      | 25.8            | 2         | 20             | 1       |
| lambda              | 10    | 0      | 678             | 3.9       | 39             | 0.9     |
| Sierpinski-triangle | 10    | 0      | 1078            | 3         | 30             | 1       |
| circle              | 15    | 5      | 276.5           | 4         | 40             | 1       |
| randomMedium        | 10    | 0      | 5107.2          | 3.9       | 39             | 0.9     |
| randomSparse        | 11    | 1      | 5490.5          | 3.9       | 39             | 0.9     |
| boston-sparse       | 6     | 0      | 108926.66666667 | 8         | 48             | 1       |
| tube                | 0     | 0      | 0               | 0         | 0              | 0       |
| edinburgh-sparse    | 0     | 0      | 0               | 0         | 0              | 0       |
| nara-sparse         | 0     | 0      | 0               | 0         | 0              | 0       |
| oxford              | 0     | 0      | 0               | 0         | 0              | 0       |
| gothenburg-sparse   | 0     | 0      | 0               | 0         | 0              | 0       |
+---------------------+-------+--------+-----------------+-----------+----------------+---------+
  
В процессе разглядывания результатов рождаются сопутствующие идеи:
  • Сохранять чат протокола тех игр, где мы проигрываем.
  • Стараться выбирать игры, где играют не только одни eager punter'ы.
  • Синхронизировать вывод формата с тем, что на входе ожидает Turtle, чтобы можно было сразу смотреть реплеи проигранных игр.

Тем временем уже почти два ночи. У turtle уже появляются реплеи с отрисовкой в gnuplot. Выглядит это как серия изображений вот такого типа:

Три ночи. Sectoid развёл какую-то невероятную активность в бенчмарке, коммиты прилетают один за другим. Turtle куда-то пропал, а я всё ещё изо всех сил программирую фьючерсы через монте-карло.

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

Почти пять ночи. Turtle обнаруживает самый эпичный фейл за весь конкурс: фьючерсы запрограммированы, они расчитываются при инициализации, летают в стейте в lambda_punter_offline, но они не объявляются! Тупо заявки на них не передаются на сервер. Это провал, и я отправляюсь это поведение ремонтировать. Получается, солвер там на игровых серверах и без всяких футур умудрялся кого-то побеждать. Чудеса.

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

Почти шесть. Turtle тоже куда-то отошёл, а я коммичу уже практически готовый предсказатель фьючерсов.

Собственно, морда map_vis, которую я уже упоминал в контексте визуализации результатов Girvan-Newman, умеет отрисовывать и результаты предсказания фьючерсов тоже. Если интересно, можно понапередавать ей разных карт и разные значения для общего количества игроков и очередности их хода. Например, вот такие фьючерсы предлагаются на randomMedium.json при двух игроках, когда мы ходим первые:

cargo run --release -- -f ../maps/randomMedium.json -c 2 -i 0

А вот такая картина будет для четырёх игроков, когда наш ход последний:

cargo run --release -- -f ../maps/randomMedium.json -c 4 -i 3

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

06:30 -- у меня поехали какие-то игры с новыми фьючерсами. Попутно ремонтирую всплывающие баги. Наконец-то идут победы на рандомных картах. Тем не менее, работягам из kontur.ru всё ещё стабильно сливаем, но уже хотя бы совсем немного, а не как раньше:

SUCCESS for game port 9327:
  Punter: 0, score: 19
  Punter: 1, score: 35
  Punter: 2, score: 8098
  Punter: 3 (it's me), score: 7104
  

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

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

09:30 -- массовые результаты всё ещё неплохие, но контур нас стабильно наказывает на треугольниках и рандомах. Всплывает новая проблема: таймауты! На гигантских картах тормозят расчёты Girvan-Newman и, особенно, симуляции монте-карло. Выношу симуляции в отдельный тред, чтобы можно было отследить таймаут из основного. Вроде как результаты ещё улучшились: массовый прогон показывает winrate > 90%. Не знаю уж, сколько там попалось контуров, но, тем не менее.

Десять утра. Я решаю окончательно всё проверить, в том числе, что не развалился lambda_punter_offline. Для этого нужна помощь Turtle, и его виртуалка.

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

10:15 -- выясняется, что проклятые таймауты всё ещё не побеждены. Закапываюсь в ремонт. Тем временем, находится ещё баг в бенчмарке Sectoid-а.

11:20 -- я наделал разнообразных лимитов на количество симуляций и всего такого: вроде как, большую часть таймаутов победил. Но, как обнаруживается, не окончательно. Остальной расклад такой: на треугольнике без ничего мы стабильно чуть-чуть проигрываем, с фьючерсами и/или опционами выигрываем. Есть ещё какие-то проигрыши, но, в массе, результаты обнадёживающие: общий винрейт по результатам 128 игр 89%.

12:30 -- сабмит оргам ушёл, Sectoid уехал в офис, а Turtle отправился обедать. Сам я, по-моему, пошёл немного вздремнуть.

13:40 -- все вернулись, работаем дальше. Прошу найти мне какую-нибудь игру, где враги делают splurges, чтобы, хотя бы посмотреть как их надо готовить :) Сам отправляюсь по-мелочи улучшать солвер на граничных случаях.

14:00 -- бахвальства не нашли. То ли эту опцию реально никто не использует, то ли просто люди уже не играют на серверах.

14:30 -- по доброй традиции затеял серьёзное улучшение в солвере =) Разумеется, за 15 минут до окончания конкурса посыпались разнообразные баги, которые я в резком темпе пытался фиксить, короче, в итоге решили забить и оставить сабмит заведомо рабочей версии.

Есть наблюдение, что участники в своей массе тусуются на маленьких и небольших картах. На больших стабильно пусто -- а вот мы как раз на них вполне себе выступаем. Получается, что если всё удачно сложится, у нас есть неплохой шанс в третьем раунде общего зачёта (если мы туда вообще доберёмся, конечно :)). Вот так выглядит среднестатическая игра в толпе на большой карте:

SUCCESS for game port 9703:
  Punter: 0, score: 0
  Punter: 1, score: 0
  Punter: 2, score: 0
  Punter: 3, score: 0
  Punter: 4, score: 0
  Punter: 5, score: 55
  Punter: 6, score: 91
  Punter: 7, score: 6699
  Punter: 8 (it's me), score: 750349
  Punter: 9, score: 0
  Punter: 10, score: 0
  Punter: 11, score: 0
  Punter: 12, score: 281651
  Punter: 13, score: 146012
  Punter: 14, score: 299313
  Punter: 15, score: 214630
  

15:30 -- конкурс закончен. Ну что ж, будем ждать результатов.

Постфактум.

В целом, мне задание в этом году очень понравилось. Конечно, неудачно вышло, что команда участвовала в неполном составе, с Rust-ом тоже получилось неаккуратно, а сам я вообще программировал со сломаной рукой, но, тем не менее. По-моему, мы сыграли неплохо, были реализованы интересные идеи, и, вообще, с драйвом и фаном было всё отлично. Собственно, для этого мы и участвуем в icfpc, так ведь? :)

Единственно, я пока никак не могу придумать стратегию, как же нам, в конце-концов, выиграть этот проклятый конкурс :) Как бы ты ни выкладывался в процессе, всё равно перед командами типа тех же kontur.ru или Unagi ощущаешь полное бессилие. У контуров, например, там шестнадцать башковитых человек в команде, они вместе сидят все выходные в офисе, у них разные алгоритмические и инфраструктурные группы, они проводят совещания в переговорках и успевают даже в процессе заниматься видео-блогом =) Японцы вообще параллельно делают по нескольку десятков солверов на разных языках от джавы до пхп, и потом комбинируют их в одного терминатора. Я не очень представляю себе, как их можно побеждать нашими ограниченными силами, мы просто физически не успеваем.

С другой стороны, был же ведь не так давно конкурс, где первое место взял на хаскеле соло чувак из Латвии. Получается, есть способ :)

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


ICFPC 2017: Ticket to Ride на Rust (первая часть) 29 авг, 2017 @ 02:02

ICFPC 2017: Ticket to Ride на Rust.

Сетап.

В прошлом году я как-то так и не собрался написать отчёт про ежегодный конкурс, который проходит под эгидой ICFP. Хотя там тоже было интересно: наша команда впервые выступила не на традиционном Common Lisp, а вовсе даже на Haskell. Опыт был достаточно любопытным. Мне скорее понравилось, ребятам скорее нет -- но положенную долю драйва все получили (хотя выступили в тот раз так себе, конечно).

В этот раз решили продолжить с экспериментами, и попробовать в деле Rust. Так как этот язык кроме меня тоже никто не знал, было принято решение основательно подготовится в течении года: совместно порешать предыдущие задания ICFPC, поревьювить разнообразного коду на расте, и тд. Надо же ответственно подходить к делу, сколько можно проигрывать-то всяким бомжам, верно? Итак, внимание вопрос: сколько же раз мы с командой успели таким образом попрактиковаться? Правильно, ноль.

Соответственно, исходный расклад перед конкурсом выглядит следующим образом:

  • Пять человек в команде.
  • Из них "на полной ставке" четверо.
  • Программировать на Rust-е умеет один, остальные листали книжку.
Казалось бы, это же верная заявка на победу? Вот и я так думал, поэтому мирозданию пришлось ещё немного подкорректировать расклад:
  • Фёдор по семейным обстоятельствам отказывается от участия.
  • Я ломаю себе правую руку.
Вот теперь ситуация выглядит справедливо, следовательно, можно начинать играть :)

Подготовка.

Надо сказать, что немного потренироваться всё же как-то получилось: за сутки до конкурса мы с Turtle быстренько спрограммировали абстрактный sokoban: всего по-минимуму: какие-то там карты, какой-то там солвер и какой-то там визуализатор. Чисто чтобы освоить инструменты, которые могут пригодиться на конкурсе. Мне, в основном, было интересно изобразить что-то похожее на визуализатор, так как все предыдущие разы у нас до него не доходили руки. А ведь это зачастую полезная вещь для понимания того, как именно у тебя работает программа.

Вот что мне показались полезным по итогам экспериментов:

  • nom -- крутая библиотека zero-cost парсер-комбинаторов.
  • piston -- вообще, это игровой движок, но он сильно модульный, поэтому оттуда легко взять только самоы необходимый минимум для того же визуализатора, без необходимости разбираться в огромном навороченном апи.

Надо сказать, что пистон меня прямо впечатлил: я что-то даже не ожидал, как там легко всё делается: графика (и 2d, и opengl), рисовалки всякие, картинки, шрифты, мышь/клавиатура. Прям даже захотелось какую-нибудь игру напрограммировать =) По-факту визуализатор базового уровня (а что-то большее редко требуется на icfpc) пишется неспешно за 30 минут, а если приложить чуть больше усилий, можно вполне сделать игровой симулятор. Пример такого простенького графического интерфейса для сокобана можно видеть на картинке выше.

Начало конкурса.

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

В этот раз ребята, организовавшие конкурс (University of Edinburgh) осмелели настолько, что по какой-то причине решили захостить сайт с заданием на своей площадке (а не на гитхабе или гугл-доках, как обычно это делалось в последнее время). Разумеется, ровно в 15:00 сайт обвалили, и работягам пришлось ждать минут тридцать, пока орги всё-таки перевезут своё барахло на гитхаб. Но, так или иначе, задание всё же было получено в виде PDF-ки.

Участникам предлагалось сыграть в онлайн-версию "Паровозов": весьма популярной настолки Ticket To Ride. На старте выдаётся карта с набором объектов, малая часть из которых является шахтами, где добывают лямбды, а большая часть является потребителями этих лямбд. Объекты как-то соединены между собой реками, по которым лодочники могут доставлять добытые лямбды из шахт к потребителям.

На картинке объекты 1 и 5 являются рудниками, а все остальные узлы графа -- потребителями. Игроки (лодочники) делают ход по-очереди, либо "захватывая" себе одну какую-то ничейную реку, либо пасуя. Чем дальше по построенному маршруту удалось увезти от шахты ламбды, тем больше очков зарабатывает игрок. Цель игры, соответственно, набрать больше всех очков.

Уметь играть предлагалось в двух режимах:

  • онлайн: по сетевому соединению с сервером -- в этом режиме можно было играть с другими участниками во время конкурса
  • и оффлайн: когда твой предварительно скомпилированный бинарь на каждый ход отдельно запускает рантайм организаторов, а стейт игры между ходами сериализуется -- в этом режиме должен быть посчёт очков

Вообще, конечно, я уже не первый раз наблюдаю в ICFPC эти милые мелочи, типа сериализуемого стейта: видно, что организаторы всячески пытаются подогнать задание под функциональные языки, чтобы на них делать было удобно, а на императивных, напротив, муторно. И, что любопытно, даже несмотря на это побеждают преимущественно всякие c++ и java :)

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

Также, в этот раз были обещаны апдейты задания прямо в процессе конкурса (до четырёх раз), и lightning division: отдельное объявление победителей по итогам 24-х часового марафона.

День первый.

Первые пару часов мы традиционно тупим в правила, и пытаемся играть друг с другом в предоставленном организаторами симуляторе, который работает через веб-интерфейс. К 16:23 я коммичу скелет проекта и какие-то базовые структуры данных, а Sectoid начинает настраивать какой-то наколенный CI.

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

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

Далее работы распределяются следующим образом: Игорь начинает программировать сериализацию структур данных в json, я отправиляюсь писать игровой цикл с сопутствующей обвязкой, Sectoid продолжает мучать CI, а Turtle куда-то уходит.

В 17:23 я внезапно делаю игровой цикл с игровым стейтом. Осмотревшись вокруг, я обнаруживаю, что никто ещё не освободился. Поэтому я берусь делать дальше протокол чата с сервером. Ещё через двадцать минут возвращается Turtle и берётся писать подсчёт очков -- как это обычно у нас принято, испортив мастер. Я традиционно прогоняю его в бранч :) Sectoid в это время дорабатывает CI.

Ещё через два часа я делаю реализацию игрового чата с сервером. Причём, в этом виде функции практически без изменений доживают до самого конца конкурса, хотя это изначально планировался как черновой набросок. Так как у меня на текущий момент есть только игровой стейт, а самих клиентов (сетевого и оффлайн) и сериализации пока нет, я делаю вот такую функцию:

pub fn run_online<S, FS, SR, FR, RR, GB>(
    name: &str,
    mut fn_state: S,
    mut send_fn: FS,
    mut recv_fn: FR,
    gs_builder: GB)
    -> Result<(Vec<Score>, GB::GameState), Error<SR, RR, <GB::GameState as GameState>::Error>>
    where FS: FnMut(&mut S, Req, Option<GB::GameState>) -> Result<(), SR>,
          FR: FnMut(&mut S) -> Result<(Rep, Option<GB::GameState>), RR>,
          GB: GameStateBuilder
и аналогичную для run_offline. Конечно, возникает вопрос, почему я не сделал FS и FR трейтами вместо замыканий со стейтом. Ну, так просто получилось меньше церемониального кода с вводом новых типов и описыванием имплементаций, ну и плюс стейта S там в изначальной реализации вообще не было. Соответственно, в реализации клиента нужно было просто вызвать нужный run, передав функции для отсылки и получания сообщений, и всё должно было заработать само.

Дальше я отправляюсь писать всякие тесты для игрового цикла и чата с сервером, в том числе, на основе демонстрационного чата Alice и Bob, который был приведён в конце спеки.

В этом месте мне следует сделать логическое отступление и поразмышлять о тестах в Rust. Дело в том, что на данный момент единственная объективная вещь, из-за которой раст может проигрывать в динамике разработки тому же Common Lisp, Haskell или Erlang -- это отсутствие REPL. Всем, кто уже успел привыкнуть к реплу, должно быть известно, насколько он ускоряет цикл создания нового кода. Особенно роскошен в этом плане CL + Slime, ни один другой репл даже близко к его возможностям даже близко не стоит. И настолько же мучительно потом возвращаться к абстрактному С++ или Java, где ты сначала несколько минут компилируешь программу, чтобы потом две секунды потратить на отлаживание printf-aми -- за это время ты бы успел провести десяток экспериментов в репле, чтобы проверить десяток идей.

Формально, Rust можно было бы причислить как раз к этой категории, если бы не его встроенная поддержка тестов. Эта поддержка на деле получилось насколько удобной, что, по-факту, цикл вида: "написал тест" + "вызвал cargo test" (C-C-t в емаксе) оказывается вполне такой себе заменой репла. Конечно, по интенсивности этот манёвр, всё же, реплу сильно уступает, но надо понимать, что тест-то остаётся "навсегда", в отличие от команды в консоли. Он будет прогоняться каждый раз во время cargo test (и в цикле CI), и, рано или поздно, он потенциально сможет вскрыть какой-нибудь новый недавно спрограммированный баг.

Тем временем Turtle начинает жаловаться в чатик на свой неравный бой с какой-то "арифметикой указателями", и я сразу подозреваю неладное :) Но, так как он упражняется в отдельной ветке, я не придаю его словам значения. Как потом выяснилось, зря.

В девять вечера, когда я возвращаюсь с ужина, обнаруживаю, что Sectoid делает автоматическую сборку сабмишнов, а Игорь доделал сериализацию и десериализацию наших структур данных в json. После небольшого совещания решили, что я попробую быстро спрограммировать сетевой клиент, а Игорь наваяет какой-нибудь базовый солвер, который что-то бы умел захватывать. Без какой-либо специальной стратегии пока, но любой солвер такого плана всяко лучше стратегии постоянного пасования каждый ход :) Игорь решает попробовать захватывать сначала все реки вокруг шахт, и потом все остальные рандомно. Я удаляюсь программировать клиента.

В 21:45 у меня готов клиент, и я обнаруживаю, что на текущий момент у нас уже есть сериализация, протокол, чат, игровой цикл, клиент, и почти готов какой-то солвер. В воздухе отчётливо запахло успешным сабмитом к lightning division :) Я бросаюсь программировать бинари lambda_punter_online и lambda_punter_offline, которые будут точками входа для онлайн и, соответственно, оффлайн реализаций протоколов. Через полчаса Sectoid куда-то убрёл, обещая вернуться в течении двух часов.

В 22:40 у Игоря готов солвер nearest, который столбит ближайшие к руднику реки. В 22:45 я заканчиваю lambda_punter_online который даже, внезапно, заработал с первой попытки! Вот она -- целебная сила написания тестов параллельно с разработкой :) Через веб-интерфейс оргов я даже умудряюсь сыграть со своим ботом. Это, конечно, всего лишь always_pass солвер, который каждый ход пасует, поэтому я разгромил его в пух и прах. В честь этой победы я ухожу дорабатывать lambda_punter_online (и, соответственно, -offline), чтобы можно было выбирать используемый солвер с помощью параметров командной строки.

В 23:17 мне это удаётся, и на карте sample.json я играю с нашим ботом уже вничью! Предлагаю в чате всем присоединиться к тестированию бота:

RUST_LOG=lambda_punter=debug,lambda_punter_online=debug cargo run --release -- --server-port 9002 nearest
В этот момент на связь снова выходит Turtle со своей "адресной арифметикой" в Rust. После краткого допроса выясняется, что он так и не смог освоить теорию про заимствования и владения в языке, и пытается программировать путём буквального следования подсказкам компилятора, который, в свою очередь, тщетно пытается угадать, что его хозяин имеет в виду :) Основная проблема заключается в том, что эти понятия в расте основополагающие, поэтому, судя по всему, особо много полезного кода Turtle'у породить не удастся.

В 23:33 из эфира пропадает Игорь, а я отправляюсь доделывать lambda_punter_offline, чтобы у нас был хотя бы один рабочий сабмит для лайнтнинга. Попутно, правда, пришлось оторваться на чат с Turtle'ом про то, как делать разное на Rust, а потом мне вообще нужно временно удалиться.

Вплоть до 01:30 мы с Turtle'ом усиленно учим Rust в ускоренном темпе, а в 1:40 я заканчиваю первую версию бинаря для оффлайна. Буквально через 10 минут организаторы апдейтят задание: появляются фьючерсы на маршруты. Тем, кто играл в паровозы должна быть понятна аналогия с карточками маршрутов, которые раздаются в начале игры (из которых можно выбрать какие хочешь). В ICFPC смысл точно такой же: на этапе инициализации игрок имеет право объявить несколько (от нуля до количества шахт) маршрутов, которые он обязуется выполнить. Получилось -- зарабатывает большой бонус, не получилось -- получает такой же большой штраф. В принципе, всё понятно :)

Тем временем Sectoid'а всё нет в эфире, и мы с Turtle'ом пытаемся понять, как собрать сабмишн. Формально-то lambda_punter_offline у меня готов, а сабмишна-то у нас нет.

В 02:46 всё-таки появляется Sectoid и обязуется сварить сабмишн. Все уже к этому довольно медленные и тупят (особенно я). Ещё через десять минут организаторы выкладывают программку-адаптер между оффлайн и онлайн режимом, с помощью которой оффлайновый клиент можно проверить прямо на игровых серверах. Программка на окамле, которую (кто бы сомневался) мне на макбуке собрать никак не удаётся.

В этом месте я ещё раз хочу сделать отступление, и отдать должное Rust-у. Я имел дело с очень большим количеством языков и их рантаймов, так вот, ответственно заявляю: почти у всего, что бывает в мире, гарантирован геморрой в плане кроссплатформенности. На чём бы вы не программировали большой проект, например, под линуксом -- будьте уверены, что отнести его мак и запустить его с без специальных плясок с первого раза не удастся (не говоря уж об венде, не к ночи будет упомянута). Неважно, хаскель это, лисп или си (особенно c++). Больше всего шансов в этом плане у джавы (хотя там есть свои приколы) и у эрланга (если не использовать порты). Так вот, проект на Rust соберётся в "чужеродной" среде с практически 100%-тной вероятностью. Особо отметим при этом, что раст -- низкоуровневый язык без рантайма.

Вплоть до трёх ночи я мучаюсь с окамловой сборкой, после чего позорно сдаюсь. Через некоторое время Turtle собирает этот адаптер у себя в виртуалке, а мне любезно даёт туда ssh.

Хоть все уже и тупят просто отчаянно, тем не менее, нам удаётся заметить, что lambda_punter_offline через орговский адаптер lamduct не работает: ошибка в клиенте "Resource temporarily unavailable". Хотя я же проверял руками через stdin/stdout, у меня всё пашет как ожидается. Что может быть увлекательней, чем ремонтировать такого рода баги в половину пятого ночи? :) Я уже было совсем собрался плюнуть и пойти спать.

04:30: пока пойти спать как-то не удалось, поэтому спрограммировал в протоколе поддержку фьючерсов. Вот теперь уже вроде все точно собрались идти спать.

04:40: я неожиданно нагугливаю информацию про "Resource temporarily unavailable" и решаю срочно ремонтировать lambda_punter_offline :) Разумеется, не получается. Хотя суматохи я навёл: Turtle'у надо пересобрать бинарь у себя в виртуалке, а Sectoid'у переварить заново сабмишн.

05:18: внезапно ремонтирую таки. Оказывается, это проблема возникает, когда на том конце пайп установлен в неблокирующий режим. Правда, вместо отремонтированного всплывает другой баг.

05:28: ремонтирую второй баг. Всплывает третий. Меня уже не остановить =)

05:36: ремонтирую третий баг. Всё, наконец заработало! Но, проблема: Sectoid'а нет, сабмишн собрать некому :) К счастью, через пять минут он появляется и сабмишн уходит. Тадам, у нас есть рабочий сабмишн к lightning division. Всё, я ухожу спать.

Продолжение здесь.
Other entries
» Трамплины и продолжения
Любопытно, конечно, что наибольшую популярность завоёвывают именно плохие с инженерной точки зрения технологии. Я не могу объяснить этот феномен: казалось бы, согласно эволюционной теории "более лучшие" вещи должны постепенно заменять эквивалентные по функционалу "более худшие", но этого не происходит. И даже не всегда проблема в том, что что-то сложнее, а что-то легче: обычно, в плохо продуманных технологиях сложность как раз выше, просто она "отложенная".

Давайте, например, посмотрим на такие платформы: Common Lisp/Scheme, Haskell или OCaml. А потом на такие: Java или Javascript. В чём разница? Правильно, в одних есть хвостовая рекурсия, в других нет :)

Ладно, на самом деле, большинству программистов наджави эта рекурсия нафиг не сдалась. Полагаю, что многие и не подозревают даже что это такое, и подобное неведение никак не мешает им вполне комфортно существовать на свете. Но оная проблема встаёт достаточно остро для пользователей более вменяемых языков, которые используют джаву или js в качестве бэкенд-платформы. Например, Clojure для jvm или Elm для javascript. Эти языки предполагают функциональную парадигму программирования, и отсутствие TCO при этом причиняет серьёзные неудобства.

Честно говоря, натолкнувшись на переполнение стека в Elm, я был несколько ошарашен. Ничто не предвещает беды, вокруг тепло и уютно: с одной стороны, у тебя почти хаскель, с другой тебе было обещано отсутствие рантайм-исключений (если ты не выходишь за рамки чистого elm). И тут херак, привет из js:

RangeError: Maximum call stack size exceeded

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

Итак, давайте рассмотрим следующий синтетический пример:


isEven : Int -> Bool
isEven x =
    case abs x of
        0 -> True
        v -> isOdd <| v - 1


isOdd : Int -> Bool
isOdd x =
    case abs x of
        0 -> False
        v -> isEven <| v - 1


isSumEven : Int -> Int -> Bool
isSumEven a b =
    isEven a == isEven b


Я тут попытался смоделировать проблему: у нас есть две взаимно-рекурсивные функции (определяющие, чётное или нечётное число на входе) и одна утилитарная, которая их как-то использует (предсказывает, будет ли сумма двух чисел чётная).

Можно сразу посмотреть в репле, как они (не) работают:


> isEven 2
True : Bool
> isOdd 13
True : Bool
> isSumEven 100 1
False : Bool
> isEven 100000
RangeError: Maximum call stack size exceeded


Как их заставить работать, если платформа не поддерживает TCO? Никак, надо переписывать.

Общепринятая практика использовать в таких случаях технику, которая называется trampolining. Она широко используется, например, в Clojure. Идея там достаточно простая. Мы рефакторим функции, использующие рекурсию таким образом, чтобы:

  1. во всех местах, где производится рекурсивный вызов, вместо этого возвращалось наружу продолжение (достаточно просто обычного замыкания: thunk)
  2. на самом "верхнем" уровне выполняется обычный тупой цикл (trampoline), который последовательно вызывает отрефакторенную функцию до тех пор, пока она возвращает продолжения

Тем самым все функции перестают быть рекурсивными, и использование стека становится чётко детерминировано: из всех условных веток возвращаются либо результаты, либо замыкания (которые потом будут вызваны из трамплина).

В Elm, оказывается, есть даже микро-пакетик с трамплинами: elm-lang/trampoline. С его помощью можно переписать вышеприведённые взаимно-рекурсивные функции следующим образом:


import Trampoline exposing (Trampoline, done, jump, evaluate)


isEvenTr : Int -> Trampoline Bool
isEvenTr x =
    case abs x of
        0 -> done True
        v -> jump <| \() -> isOddTr <| v - 1


isOddTr : Int -> Trampoline Bool
isOddTr x =
    case abs x of
        0 -> done False
        v -> jump <| \() -> isEvenTr <| v - 1



В данном случае, всё получается достаточно прямолинейно: когда готов результат, возвращаем его через done, а когда нужно выполнить рекурсивный вызов, оборачиваем его в thunk и возвращаем через jump. Соответственно, в пакете trampoline лежит ещё функция evaluate, которая как раз крутит цикл, вызывая по-очереди все возвращаемые продолжения. Проверяем:


> evaluate <| isEvenTr 2
True : Bool
> evaluate <| isOddTr 13
True : Bool
> evaluate <| isOddTr 100000
False : Bool


Да, в этом варианте всё работает!

Кстати, небольшое отступление. Очевидно, что многим (включая меня) может не понравиться, как выглядит вот этот кусок кода:


jump <| \() -> isOddTr <| v - 1


Лично я его автоматически написал сначала так:


jump <| always <| isOddTr <| v - 1


За что был наказан потерянным часом на отладку. Кто может предположить, в чём кроется засада? :) Для справки: always.

Ладно, возвращаемся к примерам. Как написать трамплин-версию isSumEven? В принципе, можно как-то так:


isSumEvenTr : Int -> Int -> Trampoline Bool
isSumEvenTr a b =
    done <| (evaluate <| isEvenTr a) == (evaluate <| isEvenTr b)


Конкретно для этого синтетического примера, наверно, такой вариант особо ничем не плох. Но всё же: можно ли обойтись только одним evaluate? Очевидно, что можно, если получится каким-то образом "попасть внутрь" типа Trampoline a, чтобы достать значение a или, хотя бы, как-то его преобразовать. Но вот незадача: этот тип не является функтором или монадой, никаких соответствующих комбинаторов для него нет, да и вообще это всё страшные слова, и такой мерзости у нас в эльме не водится! Следовательно, единственный вариант — это честно интерпретировать Trampoline a через evaluate. Или нет?

На самом деле, есть способ "состыковать" несколько Trampoline-ов, чтобы выполнить их в одном цикле-эвалюаторе: опять же, CPS. Но для этого нам опять нужно отрефакторить функции, на этот раз в continuation passing style:


isEvenTrK : Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isEvenTrK x k =
    case abs x of
        0 -> k True
        v -> jump <| \() -> isOddTrK (v - 1) k


isOddTrK : Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isOddTrK x k =
    case abs x of
        0 -> k False
        v -> jump <| \() -> isEvenTrK (v - 1) k


isSumEvenTrK : Int -> Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isSumEvenTrK a b k =
    isEvenTrK a <|
        \resultA ->
            jump <| \() -> isEvenTrK b <|
                \resultB ->
                    k <| resultA == resultB



Главное изменение: функции теперь не возвращают результаты напрямую (логически, они уже ничего не должны возвращать), вместо этого они принимают дополнительные параметр: "продолжение", которому этот результат передаётся. Теперь в isEvenTrK появилась возможность состыковать две "затрамплиненные" функции внутри продолжения, при этом сохранив тип возвращаемого значения Trampoline Bool, который уже скармливается единственному evaluate:


> evaluate <| isSumEvenTrK 100000 1 done
False : Bool
> evaluate <| isSumEvenTrK 100000 100000 done
True : Bool


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

Ну, в целом, как-то так. Далее полагается, чтобы я написал какие-то выводы или подытоги, но какие тут могут быть выводы? Сложно, запутанно. Но это и есть та самая "отложенная сложность", про которую я говорил в начале поста. Был бы в вашем джаваскрипте изначально родной TCO, я бы не писал этот текст, а вместо этого сделал бы что-нибудь полезное.
» Вернуть итератор
А между тем, зацените, в nightly rust научились делать вот так:

#![feature(conservative_impl_trait)]

fn numbers() -> impl Iterator<Item = i32> {
    1 ..
}

Дословно, мы из функции возвращаем некоторый анонимный тип, всё что известно про которого — это то, что он реализует типаж Iterator, ассоциативный тип Item коего установлен в i32.

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

fn numbers() -> Box<Iterator<Item = i32>> {
    Box::new(1 ..)
}

… что плохо, потому что здесь одна совершенно ненужная аллокация, и итерация через vtable. Либо писать вот так:

fn numbers() -> std::ops::RangeFrom {
    1 ..
}

… что тоже омерзительно, по ряду причин:
  • Надо знать возвращаемый тип, а он может быть сильно составным (и будет, в случае с лесенкой преобразований итератора).
  • Зачастую приходится оборачивать его в newtype, чтобы не экспортировать из модуля кишки (и имплементировать соответствующий Deref).
  • В некоторых случаях тип вообще невозможно прописать руками, например, когда generic биндится замыканием (а тип замыкания нельзя написать руками).

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

Помимо итераторов, данная возможность даст возможность возвращать замыкания перемещением (by move), как-то так:

#![feature(conservative_impl_trait)]

fn adder(a: i32) -> impl Fn(i32) -> i32 {
    move |x| x + a
}

Это ваще космос. По факту можно будет с относительным комфортом писать в функциональном стиле на языке, в котором нет garbage collector (!!), и при этом без сегфолтов и утечек.

Да, и ещё формат ошибок в Rust теперь слизали с Elm, и они теперь выглядят максимально подробно:


Короче, я повторю свою мысль ещё раз: в 2016-м не может быть ни единой причины писать что-то на C++, когда есть Rust. Ну, может, если вы только дорабатываете какой-то уже существующий большой проект. Начинать же сейчас что-то новое на плюсах вообще безумие, никогда так не делайте :)
» Вероятностные алгоритмы.

Введение.

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

Задание было придумано очень крутое. "Очень крутое" -- это, в моём понимании, такое задание, которое:

  1. Имеет практическую ценность.
  2. Не подразумевает одного единственного верного решения, до которого просто нужно додуматься в процессе конкурса.

Полностью условие можно почитать на офсайте, а вкратце оно звучит так:

  • Дан словарь из ~660k записей. Ориентировочно, это английские слова.
  • Надо написать функцию "test(word)", которая возвращает true, если заданное слово входит в словарь, и false, если нет.
  • Суммарный объём программы и файла с данными, которым она может пользоваться, не должен превышать 65536 байт.
  • Побеждает решение, которое даст максимальный процент правильных ответов на большом количестве тестов.

Чтобы было повеселее, в тестах используется специальный генератор слов, которые визуально (и грамматически) очень похожи на нормальные английские, но при этом в словаре их нет, например: "goldrunk". И, напротив, в заданном словаре есть весьма странные записи, в которых распознать английский язык очень сложно, например, "qwertys" или "rRNA".

Согласно комментариям участников в соответствующем треде на хабрахабре, основные идеи (успешных) решений были следующие:

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

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

Немного теории.

В статье на русскоязычной википедии говорится, что: "Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью". Это не совсем так -- принципиально, к ГСЧ в вероятностных алгоритмах обращаться необязательно. В англоязычной версии этой статьи есть более корректное определение: "uniformly random bits". Опять же, экономия может достигаться не только во времени работы, а по памяти, например.

Неплохой демонстрацией может служить широко известный фильтр Блума, который является "вероятностной структурой данных". Источником "случайных" значений с дискретно-равномерным распределением здесь служит хеш-функция, а выигрыш получается в более экономном использовании памяти. Взамен мы получаем, правда, неуверенность в ответе: вместо да и нет мы имеем вероятно, да и точно нет. Эта неуверенность обусловлена вероятностью возникновения коллизии, но эту вероятность можно достаточно точно подобрать, чтобы применение блумфильтра было обосновано для конкретной задачи.

Соответственно, возможность такого рода компромисса в постановке задачи (значительный выигрыш по ресурсам взамен некоторой допустимой недостоверности ответа) может быть хорошим признаком того, что в решении имеет смысл использовать вероятностный алгоритм. Например, это конкурс про упаковку огромного словаря в 64Kb :)

Самое главное, что здесь нужно запомнить, это фразу: дискретно-равномерное распределение. "Равномерное распределение" на практике должно означать следующее: если случайная величина (ГСЧ, хэш-функция, значение сигнала) генерирует нам какое-то значение из интервала R, нужно, чтобы вероятность получения каждого значения из R была 1/R (или, хотя бы, очень близко к этому). При этом количество таких значений должно быть конечно (дискретно). Визуально, это выглядит следующим образом: допустим, мы взяли поле 10x10 и ткнули в рандомную точку. Получилось, например, как-то так:

А если мы воткнули их несколько тыщ, то должно получиться относительно равномерное покрытие, что-то типа такого:

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

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

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

Немного практики.

Из популярных практических алгоритмов для подобного рода задач я бы хотел отметить, например, такие:

  • Locality-sensitive hashing: подбирает для множества элементов хэш-функцию таким образом, что "схожие" элементы попадают в одну корзину (хеши дают коллизию ожидаемым образом). Таким образом достигается существенное уменьшение размерности данных, и используется, например, в задачах кластеризации.
  • MinHash: ускорение расчёта коэффициента Жаккара для вычисления степени схожести двух множеств. Широко используется, например, для задач выявления нечётких дубликатов среди большого количества документов.
  • Семплирование потока данных. В отличие от простой выборки каждого N-ого элемента из потока, хешируют некоторый составной ключ (например, "пользователь"/"запрос"/"таймстамп"), после чего берут N корзин, и отбрасывают все результаты, не попавшие в одну из них. Это позволяет семплировать поток по сложным условиям, избегая дорогостоящей группировки.
  • Flajolet–Martin algorithm, и его развитие в виде HyperLogLog. Алгоритмы используют достаточно изящный хак для быстрой аппроксимации количества уникальных элементов в заданном множестве. Я реально советую ознакомится с описанием, это, действительно, хитрый трюк :)

Конкурсная задача.

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

Самый простой вероятностный алгоритм, который можно придумать, это подбрасывание монетки:

function test(word) {
    return Math.random() < 0.5;
}

Несложно догадаться, что он совершенно бесплатно даёт нам 50% правильных ответов, при этом даже не пользуясь своим аргументом :) Соответственно, это значение будет базисом, с которым можно сравнивать результативность других алгоритмов.

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

Но, если понимать как работают вероятностные алгоритмы в принципе, можно попробовать придумать что-нибудь чуть более оригинальное. Я позаимствовал некоторые идеи из MinHash, и получилось вот что.

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

Применив K таких случайных хеш-функций к одному и тому же аргументу (например, слову из словаря) мы получим K результатов, которые будут, опять же, случайно распределены по всему диапазону значений fnv. Я взял 32-х битную версию, соответственно, результаты хеширования будут в диапазоне 0 - 0xffffffff. Дальше надо как-то убедиться, что эти результаты имеют равномерное распределение. Этот факт явно каким-то образом должен доказываться, но я, к сожалению, не математик, поэтому тупо нарисовал график и посмотрел на него глазами. Выглядит как равномерное :) Это свойство в данном случае мне важно для того, чтобы можно было оценить вероятность того, что случайная хэш-функция даст конкретное значение. При равномерном распределении эта вероятность будет 1/R, где R = 232.

Дальше сделаем вот что: возьмём одну такую случайную хеш-функцию H, и прогоним через неё все N слов из словаря. Получим N чисел (хешей слов), которые как-то случайным образом будут раскиданы в интервале от 0 до 232 - 1. Теперь нам надо найти какое-то такое утверждение P, которое бы:

  1. Выполнялось бы для всех полученных чисел.
  2. Не выполнялось для как можно большего количества остальных чисел из [0, 232).

Идея понятна: алгоритм получает слово, считает от него хеш с помощью хеш функции H, проверяет результат на условие P, и, если оно ложно, то это слово точно не из словаря. Если условие истинно, то слово, с какой-то вероятностью, может быть в словаре. С какой? Это зависит от природы утверждения P. Далее нам достаточно провести несколько проб (повторить алгоритм несколько раз для различных хеш-функций), с каждым разом увеличивая вероятность срабатывания P, чтобы достичь удовлетворяющей нас достоверности ответов.

Допустим, к примеру, сложилось такая ситуация, что все хеши слов из словаря оказались чётными. Тогда все нечётные значения из интервала от 0 до 232 означали бы true negative. Вероятность этой ситуации (хеш проверяемого слова оказался нечётным) была бы почти 0.5 -- это очень крутой результат для одной только пробы. Ведь тогда нам для достоверности ответа "слова точно нет в словаре" в 99% достаточно log0.50.01 = ~7 проб, то есть, всего семь рандомных хеш-функций.

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

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

Если значения хеш-функций имеют равномерное распределение (а они имеют в нашем случае), вероятность попадания хеша в одну из корзин будет равняться 1/M. Каким же должен быть M, чтобы, раскидав по этому такому количеству корзин 660 тысяч хешей, у нас бы осталась одна пустая корзина? Это как-то явно подсчитывается при помощи математики, но (если вы, подобно мне, ничерта не помите из тервера) можно немного схалтурить, и получить нужные цифры при помощи несложного программирования.

Проведём эксперимент: сгенерируем нужное количество 32-х битных случайных чисел, по одному на слово из словаря -- как будто, это результаты хеширования. Программный ГСЧ должен давать равномерное распределение, и хеш-функция тоже даёт равномерное распределение, так что это относительно равноценная замена. Далее тупо брутфорсом попробуем подобрать минимальное количество корзин так, чтобы в одну из них ни одно рандомное число не попало. Вот как это примерно может выглядеть на Common Lisp:

(defun get-minimum-buckets-count (words-count)
  (iter
    ;; generate pseudo hashes
    (with pseudo-hashes =
              (iter (repeat words-count)
                    (collect (random (ash 1 32)) result-type simple-vector)))
    (for buckets-count from 2)
    ;; make buckets with hit counters
    (for buckets-hits =
         (make-array buckets-count
                     :element-type 'fixnum
                     :initial-element 0))
    ;; collect hits
    (iter (for i from 0)
          (for hash in-sequence pseudo-hashes)
          (for bucket = (mod hash buckets-count))
          (incf (elt buckets-hits bucket)))
    ;; check whether an empty bucket exists
    (for empty-bucket = (position 0 buckets-hits))
    (when empty-bucket
      (return-from get-minimum-buckets-count
        (values buckets-count empty-bucket)))))        

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

Запустив эту функцию для 660000 слов, мы (через некоторое время) получим результат для M порядка ~33000. Разумеется, при каждом запуске он будет разный (так как псевдо-хеши генерируются каждый раз случайным образом), но это будут всегда приблизительно одинаковые значения с небольшим разбросом. На практике это означает, что мы можем получить с одной пробы вероятность 0.00003, что слово не входит в заданный словарь: для этого достаточно проверить, что хеш слова попал в пустую корзину. На первый взгляд совсем мизерный шанс, но давайте прикинем, что с этого можно получить.

Итак, мы можем взять одну рандомную хеш функцию H0, словарь, и найти для них два числа: M0 (минимальное количество корзин, раскидывая хеши по которым образуется одна пустая), и B0 (номер пустой корзины). Эти два числа описывают пробу P0, которая даёт шанс в 0.003%, что проверяемое слово точно не принадлежит словарю. Если же мы посчитаем таким же образом P1 для другой функции H1, мы сможем провести две независимые пробы, увеличив вероятность true negative до 0.00006 (вероятность не попасть в пустую корзину для одной пробы равняется 1.0 - 0.00003 = 0.99997, а для двух независимых проб вероятности умножаются). Аналогично, десять подобных проб дадут уже вероятность в 0.03%, сто в 0.3%, а десять тысяч, например, целых 26.1%. Продолжая этот ряд, можно подобрать число 153000 -- именно столько проб нужно выполнить, чтобы с вероятностью 99% определить true negative.

Одна проба однозначно задаётся двумя числами M и B, соответственно, для 150-ти тысяч проб нужно сохранить 300 тысяч чисел. Это явно больше того, что можно запихать в заданные задачей лимиты. Нетрудно прикинуть, что, если мы аллоцируем, ориентировочно 14 бит для M и 15 бит для B, в 64 Kb можно вместить всего порядка 18000 проб. А ведь там ещё должно остаться какое-то место для сценария на js! Соответственно, чуть более реалистичная цифра в 17000 проб даст вероятность определения true negative в ~40%.

Что это означает на практике? Это означает следующие вещи:

  • Если на вход функции test было подано слово из словаря, все пробы будут успешными (хеши не попадут в пустые корзины), и будет возвращена истина. Это true positive.
  • Если на вход функции test было подано слово не из словаря, то:
    1. с вероятностью 40% одна из проб даст неуспех (один из хешей попадёт в пустую корзину), и будет возвращена ложь. Это true negative.
    2. с вероятностью 60% все пробы, всё же, дадут успех, и будет возвращена истина. Это false positive.
  • Ситуация false negative в данной конфигурации невозможна, потому что мы, формируя множество проб, специально так подбирали числа M, чтобы для слов из словаря обязательно оставалась пустая корзина.

Итоговый процент верных ответов зависит от характера тестовых данных: в худшем случае он будет стремиться к 40% (если на вход подаются только слова не из словаря), в лучшем -- к 100% (если на входе только слова из словаря), а в случае половина тех, и половина других, это должно быть значение порядка 70%.

Эту цифру можно чуть-чуть улучшить, параллельно значительно упростив формат сериализованной пробы (что тоже немаловажно, ведь размер js-скрипта тоже имеет значение). Можно подбирать M специальным образом, чтобы пустая корзина оказывалась всегда, например, в нулевой позиции (B == 0, или H % M == 0). В этом случае для записи пробы нам достаточно только одного числа M. Эксперименты показывают, что это получаются значения из диапазона примерно 38000 - 91000: это означает, что соответствующие вероятности для проб будут меньше, но зато для их упаковки теперь достаточно 16 бит, следовательно количество проб можно увеличить до ~32000, и, главное, сильно упростить код для их упаковки/распаковки.

Конечно, полученная цифра в 70% верных ответов выглядит не очень впечатляюще. Но следует отметить две вещи про это решение:

  1. Удивительная простота алгоритма в целом, и элементарная масштабируемость: для достижения нужной точности нужно просто последовательно увеличивать количество проб.
  2. Это абсолютно "чистый" и "честный" результат: на нетронутых оригинальных входных данных, когда словарь взят полностью как есть. Всегда можно приложить некоторые усилия к препроцессингу: порезать слова, оканчивающиеся на "'s", разделить на префиксы/суффиксы, и т.п. Ребята в комментариях к задаче на хабрахабре писали, что они относительно безболезненно уменьшали словарь до 280000 записей. А 280 тысяч хешей в нашем алгоритме уже означают M ~ 13000, что, в свою очередь, даёт вероятность одной пробы 0.0076% и порядка 18000 проб в 64 Kb, выдающих, суммарно, почти 75% true negative! А это уже больше 87% верных ответов для случая 50/50 словарных и не словарных слов.

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

Полностью моё решение, вместе с расчитанными данными, можно взять в этом репо: сами хеши я породил из js (директория generator), а компилятор проб из них сделал на Rust (директория compiler).


» Геймификация скучных процессов
13 апреля я опубликовал пост с текстом интересной, как мне тогда казалось, вакансии, и он провисел неделю. Много ли за эту неделю заинтересовалось ей людей? Нуль!
19 апреля я предложил развлекательную тестовую задачку для потенциальных кандидатов и им сочувствующих, и внезапно за одну такую же неделю мне наприсылали какие-то полчища резюме, что я даже немного впал в ступор :) Честно говоря, начал даже понимать профессиональных эйчаров, это не такая уж и простая работа, оказывается.

Так что, коллеги, кому нужны сотрудники (например), можете перенимать лайфхак, дарю бесплатно и без регистрации.
» Задачка для интересу
Чёто вакансия вызвала интерес у удивительно малого количества народу, я даже затрудняюсь объяснить этот феномен :) Все так недолюбливают Эрланг? Но у меня же ещё Elm и Rust, и вообще, потенциально определённая свобода в этом плане. Пишите, когда ещё вам предложат попрограммировать с пользой на чём-то неунылом за деньги :)

Для подогрева интереса к вакансии выкладываю тестовую задачку для потенциальных кандидатов. А то чё я её зря что ли придумывал.
UPD 2016-04-20: добавил "sample_9".
UPD 2016-04-21: пофиксил рефенсные тайминги.

Итак, задачка из трёх частей, в порядке увеличения сложности. Делать надо на эрланге, если умеете эрланг, или на чём угодно, если не умеете. Ориентировочные критерии оценки такие:
  • Если человек сделал первую часть, то хорошо: с ним уже есть о чём говорить.
  • Если получилась вторая — очень хорошо.
  • Если третья — совсем круто!

Общее условие

Дана программа в виде упрощённого S-expression (что это?), например:

sample_1() -> <<"(+ (* 4 4) (* 2 (- 7 5)) 1)">>.

где первый элемент каждого списка — это операция (всего их три вида):
  1. сложение: атом "+"
  2. вычитание: атом "-"
  3. умножение: атом "*"
Все остальные возможные атомы — это целые числа.
Ещё примеры:

sample_2() -> <<"10">>.
sample_3() -> <<"(* 10 (- 0 1))">>.
sample_4() -> <<"(- (+ 10 10) -5 0)">>.
sample_5() -> <<"(+ (- (* (+ (- (* 1))))))">>.
sample_6() -> <<"(* 2 (+ (- 10 9) (- 3 (* 2 1))) (+ (- 10 9) (- 3 (* 2 1))))">>.
sample_7() -> <<"(+ (* 2 1) (+ 8 8) (- (+ 4 3 2 1) (* 3 3) (* 2 2)) (* 5 7))">>.
sample_8() -> <<"(- (+ (+ 3 3) (- 3 3) (+ 3 3) (- 3 3)) (* 2 2))">>.
sample_9() -> <<"(+ (- 6 1) (+ 0 1 1) (- 7 2) (* 3 4 5) (- 3 1) (+ 2) (- 0 10))">>.

Задача 1

Реализуйте функцию-интерпретатор "interpret/1" и вычислите результаты вышеприведённых программ.

Например:
interpret(sample_1()). --> 21
interpret(sample_2()). --> 10
interpret(sample_3()). --> -10
interpret(sample_4()). --> 25
interpret(sample_5()). --> 1
interpret(sample_6()). --> 8
interpret(sample_7()). --> 50
interpret(sample_8()). --> 8
interpret(sample_9()). --> 66

Задача 2

Представим, что все операции в программе имеют константную задержку, которая не зависит от процессора. Например, это некоторого рода длительная сетевая активность.
Итого, реализация каждой из операции теперь должна содержать вызов "timer:sleep(X)":
  • X = 2000 ms для сложения "+"
  • X = 3000 ms для вычитания "-"
  • X = 10000 для умножения "*"

Реализуйте функцию-интерпретатор "interpret_network/1", которая вычисляет результат заданной программы с минимально возможной задержкой.

Например:
interpret_network(sample_1()). --> 21 (delay 15 s)
interpret_network(sample_2()). --> 10 (delay 0 s)
interpret_network(sample_3()). --> -10 (delay 13 s)
interpret_network(sample_4()). --> 25 (delay 5 s)
interpret_network(sample_5()). --> 1 (delay 30 s)
interpret_network(sample_6()). --> 8 (delay 25 s)
interpret_network(sample_7()). --> 50 (delay 15 s)
interpret_network(sample_8()). --> 8 (delay 13 s)
interpret_network(sample_9()). --> 66 (delay 12 s)

Задача 3

Представим, что все операции в программе имеют константную задержку, которая зависит от процессора. Например, это некоторого рода тяжелые вычисления, выедающие 100% ядра процессора.
Наша машина оборудована N физическими ядрами.
Итого, реализация каждой из операции теперь должна содержать вызов "timer:sleep(X)", при этом максимальное количество "одновременно выполняющихся" операций должно быть меньше или равно N:
  • X = 2000 ms для сложения "+"
  • X = 3000 ms для вычитания "-"
  • X = 10000 для умножения "*"

Реализуйте функцию-интерпретатор "interpret_cpu/2", которая, используя процессор максимально оптимальным образом, вычисляет результат заданной программы с минимально возможной задержкой.

Например:
interpret_cpu(sample_1(), 2). --> 21 (delay 15 s)
interpret_cpu(sample_2(), 2). --> 10 (delay 0 s)
interpret_cpu(sample_3(), 2). --> -10 (delay 13 s)
interpret_cpu(sample_4(), 2). --> 25 (delay 5 s)
interpret_cpu(sample_5(), 2). --> 1 (delay 30 s)
interpret_cpu(sample_6(), 2). --> 8 (delay 28 s)
interpret_cpu(sample_6(), 3). --> 8 (delay 25 s)
interpret_cpu(sample_7(), 2). --> 50 (delay 26 s)
interpret_cpu(sample_7(), 3). --> 50 (delay 22 s)
interpret_cpu(sample_7(), 4). --> 50 (delay 15 s)
interpret_cpu(sample_8(), 2). --> 8 (delay 15 s)
interpret_cpu(sample_8(), 3). --> 8 (delay 13 s)
interpret_cpu(sample_9(), 2). --> 66 (delay 15 s)


Приглашаю всех желающих порешать, код выкладывайте на какой-нибудь gist и давайте ссылку в комменты. Свой вариант я выложу ближе к концу недели.
Top of Page Разработано LiveJournal.com