ChatGPT подсказал название задачи по формулировке

Недавно встретил редкую задачу из теории вероятностей. Сначала сам решил, потом стал спрашивать у ChatGPT, чтобы понять, под каким названием эта задача может быть известна.

Пусть имеется множество из N элементов. В ходе одного испытания случайным образом выбирается какой-либо элемент. Сколько в среднем нужно испытаний, чтобы каждый элемент множества был выбран хотя бы один раз?

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

Это классическая задача, известная как проблема дней рождения или задача выбора.

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

Эта задача относится к классу задач под названием «задача об абсолютной перестановке» или «задача о деньгах дней рождения».

Этот вопрос относится к теории вероятностей и известен как проблема «парадокса дней рождений» или «проблема встречи». В вашем случае, это известно как проблема «выборки с возвратом» (sampling with replacement).

Этот вопрос связан с математической областью, называемой «парадоксом дней рождения» или «задачей о шарах и корзинах». Для вашего вопроса это называется «парадоксом выбора с возвращением».

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

This problem is a classic example of the coupon collector's problem.

Оказывается, эта интересная задача встречается в английской литературе под таким названием, что можно перевести как «задача коллекционера», а в русской литературе практически неизвестна. Я думал, что для ChatGPT не проблема дать ответ с учетом перевода. Но, видимо, при генерации ответа связь между словами одного языка сильнее, чем связи между терминами с учетом перевода.

О самой задаче коллекционера написал подробнее в «черновиках физика».

Как не пропускать прием лекарств

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

Я в свое время придумал другой способ. На упаковке с лекарством я прямо подписываю дни недели, в которые надо выпить конкретные таблетки. Сама упаковка становится наглядным индикатором («прогресс-баром») приема.

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

О ссылках на источники вдохновения

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

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

Конечно, есть шанс, что автор неправильно понял «триггер», и его пост окажется «не в тему». И если не ссылаться на триггер, то вроде как и ошибки нет, просто обсуждается другая проблема. Но как раз честность проявляется еще и в том, что автор готов признать ошибку.

Давайте в оставшейся части я на примерах проиллюстрирую свою позицию.

Пример №1. Илья недавно выложил видео на 24 минуты с названием «0,(9) = 1. Как в это поверить?» В вводной части написано «Если вам никак не удается поверить, что 0,(9) = 1, то давайте я попробую убедить». Но масштаб проблемы при этом совсем неясен. Где все эти люди, которым не удается поверить, что 0,(9) = 1? Как они связаны с математикой? Почему важно их в этом убедить? Что будет, если их в этом не убеждать? В школьных и вузовских учебниках о совпадении формально разных десятичных дробей, одна из которых имеет период 9, написан от силы один абзац. Это всё при том, что сама запись рациональных чисел как бесконечных периодических десятичных дробей в науке не особо-то используется. Почему именно этот абзац из тысячи других заслуживает внимания?

Конечно, может быть такое, что к Илье постоянно приходят люди и говорят, что 0,(9) меньше 1. В этом случае идея записать видео и вместо ответа давать на него ссылку имеет право на жизнь. Но тогда бы я начал пост со слов «Мне раз в месяц пишут незнакомые люди о том, что…», и масштаб проблемы стал бы понятен.

Пример №2. У меня есть пост под названием «Какой мир видит фотон?», где я разбираю этот вопрос с точки зрения теории относительности. Для пояснения мотивации я честно добавил критикуемый ролик, в котором авторы попытались смоделировать, что бы засняла камера при движении через солнечную систему со скоростью света. А еще рассказал о семинарах по философии науки, на которых преподаватель утверждал, что из неспособности теории относительности описать движение одного фотона относительно другого следует, что ей на смену должна прийти какая-либо другая теория.

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

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

Опять фишинг с доменами

Опять пришло фишинговое письмо на тему якобы неоплаченного домена:

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

Единица на семисегментных индикаторах

Илья Бирман написал о расстоянии между единицей и другими символами при отображении цифр семисегментным индикатором. Из двух вариантов ниже он предлагает второй:

Также он пишет, что этот прием не применяется в часах и светофорах. Но вот гифка с кишиневским светофором, который отображает число 11 именно так:

Мне, кстати, такое отображение не нравится. Во-первых, кажется «не настоящим». Во-вторых, визуальный центр числа в этот момент прыгает влево.

Воскрешение access-токенов

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

У нас на работе для единого входа в приложения (SSO) и получения ролей используется Keycloak. В целом он работает нормально, но иногда подтекает по памяти и начинает отвечать ошибками типа 502. В этот момент приложение тоже становится недоступным: когда истекает время жизни access-токена, приложение запрашивает новый токен, получает ответ 502 и по умолчанию падает на неперехваченном исключении. Простой приложения влечет остановку основного бизнес-процесса и прямую потерю денег.

Чтобы уменьшить влияние недоступности сервиса авторизации на работающее приложение и предотвратить потерю денег, мы придумали переиспользовать истекшие токены и назвали этот прием «воскрешением». Время жизни access-токена продлевается на TTL, если сервис авторизации возвращает ошибку с кодом 5xx. В воскрешении важно не переусердствовать, коды ошибок 4xx не должны разрешать пользователю продолжать работу.

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

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

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

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

В этой заметке мы рассмотрели некоторые способы обеспечения обеспечения отказоустойчивости и наблюдаемости (observability). Я присвоил ей тег «работа программиста», потому что это действительно работа программиста — подумать об этих нефункциональных требованиях и о том, как их выполнить. К вам никто не придет и не скажет что-то вроде: «а сделай-ка воскрешение токенов, чтобы предотвратить простой приложения». А если вдруг придет и скажет, то цените такого человека :)

RSS, формулы и Feedly

Постоянные читатели помнят, что у меня есть сервис по превращению математических формул в картинки и редактор для создания математических текстов. С заменой формул на картинки на обычных веб-страницах проблем нет, вопрос в том, как поступать с RSS?

Еще в 2011 году я стал отдавать в RSS растровые картинки, потому что непонятно, в каком окружении будет отображаться контент оттуда. А на обычных веб-страницах js-код определял, есть ли в браузере поддержка SVG, и в этом случае подключал красивые векторные картинки.

Когда в 2013 году прекратила работать rss-читалка Google Reader, народ в основном стал использовать Feedly. Напомню, что тогда Feedly работал через API Google Reader. Они подсуетились и написали свой бэкенд, чтобы не только не растерять свою аудиторию, но и подхватить доставшуюся даром аудиторию сервиса гугла.

У Feedly была одна особенность с отображением картинок: они принудительно становились плавающими (включалось css-свойство float). Если в тексте встречается одна иллюстрация, это может быть нормально. Но математические тексты с обилием формул превращались в нечитаемую кашу. Я написал им в поддержку, никакого ответа не получил. И мне пришлось отключить преобразование формул в картинки: я отдавал вместо формул вроде $$E=mc^2$$ их исходный код $$E=mc^2$$.

Сейчас я решил проверить, не научился ли Feedly отображать нормально картинки. Оказалось, что научился. Если вы читаете этот текст через RSS в Feedly, можете в этом убедиться в предыдущем абзаце.

Чтобы два раза не вставать, я попросил ChatGPT составить xslt-преобразование для xml-кода rss-канала, которое бы облагородило внешний вид при открытии RSS в браузере. Я оставил по ссылке нейтральный стиль, но никто не мешает использовать CSS с фирменным дизайном. У меня получился такой xslt-файл:

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:template match="/">
        <html>
            <head>
                <title><xsl:value-of select="rss/channel/title" /></title>
                <style type="text/css">
                    a {
                        color: #56d;
                        text-decoration-thickness: 1px;
                        text-decoration-color: rgba(85, 102, 221, 0.5);
                    }
                    body {
                        max-width: 720px;
                        font: 16px/1.5 sans-serif;
                        margin: 0 auto;
                    }
                    h1, h2, h3 {
                        margin: 1em 0 0.25em;
                    }
                    p {
                        margin: 0 0 0.75em;
                    }
                </style>
            </head>
            <body>
                <h1>
                    <a href="{rss/channel/link}">
                        <xsl:value-of select="rss/channel/title" />
                    </a>
                </h1>
                <xsl:for-each select="rss/channel/item">
                    <div class="item">
                        <h2><a href="{link}"><xsl:value-of select="title" /></a></h2>
                        <div><xsl:value-of select="description" disable-output-escaping="yes" /></div>
                    </div>
                </xsl:for-each>
            </body>
        </html>
    </xsl:template>
</xsl:stylesheet>

Чтобы это заработало, нужно добавить ссылку на такой xslt-файл в RSS:

<?xml version="1.0" encoding="utf-8"?>
<?xml-stylesheet href="/_styles/rss.xslt" type="text/xsl"?>
<rss version="2.0">
    <channel>
	...
    </channel>
</rss>

Кстати, пока со всем этим возился, обнаружил, что в RSS сломалось отображение исходного кода: перестало работать сохранение переносов строк внутри тегов <pre><code>. Долго пытался понять, где ошибка, пока не осознал, что это сломался сам Feedly. Похоже, эта проблема наблюдается в любых источниках в Feedly за последние недели две. Заодно сейчас и проверим, нормально ли будет отформатирован код в этой заметке.

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

Добавлено позднее: оказывается, Feedly нормально отображает картинки только в веб-версии. В приложении на андроиде формулы ни в каком варианте не отображаются, не работает ни SVG и PNG в тегах img, ни SVG, добавленный напрямую в HTML. Буду считать, что это баг на их стороне, и ничего с этим делать не буду.

Еще одно решение задачи о педантичном пассажире

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

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

$$\tikzcdset{arrow style=tikz,diagrams={>=stealth}} \begin{matrix} \left(\begin{tikzcd}[row sep=14pt,column sep=12pt] 1\ar[d] & 2\ar[d] & 3\ar[d] & 4\ar[d] & 5 & 6\ar[d] & 7 & 8 \\ \textcolor{blue}{4}\ar[urrr,dotted,looseness=1,in=155] & \textcolor{blue}{6}\ar[urrrr,dotted,looseness=1,in=160] & \textcolor{blue}{1}\ar[ull,dotted] & \textcolor{blue}{2}\ar[ull,dotted] & \bf{5} & \textcolor{blue}{3}\ar[ulll,dotted] & \bf{8} & \bf{7} \end{tikzcd}\right) &\longleftrightarrow& \begin{tikzcd}[column sep=8pt] \bf{5} & \bf{8} & \bf{7} & \textcolor{blue}{1}\ar[r,dotted] & \textcolor{blue}{4}\ar[r,dotted] & \textcolor{blue}{2}\ar[r,dotted] & \textcolor{blue}{6}\ar[r,dotted] & \textcolor{blue}{3}\ar[llll,dotted,looseness=0.5,in=-60,out=-120] \end{tikzcd} \end{matrix}$$

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

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

Таким образом, мы установили биекцию (взаимно однозначное соответствие) между перестановками, при которой элементы цикла, содержащего элемент 1, переходят в элемент 1 и всех соседей справа. При усреднении по всем перестановкам любой элемент, в том числе 1, оказывается в середине (на каждую перестановку, где этот элемент сдвинут влево от центра, есть зеркальная перестановка, где он сдвинут на такое же расстояние вправо). Поэтому среднее количество соседей слева и справа совпадает и равно $$(n-1)/2$$.

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

Неудачная попытка включить JIT в PHP

Обновил на этом сервере версию PHP с 7.4 на 8.2. Решил включить JIT-компиляцию и посмотреть, будет ли от нее эффект.

Оказалось, на JIT влияет только одна настройка, но она не очень-то и простая. Включил рекомендуемое значение, но никакого эффекта не заметил. Статистика JIT, выдаваемая через var_dump(opcache_get_status()['jit']);, показывала, что на самом деле JIT не включен.

Не сразу понял, в чем проблема, потому что в логах было пусто. Определить проблему удалось, когда попытался включить JIT для запуска PHP из консоли. В консоль выводилась ошибка

PHP Warning:  JIT is incompatible with third party extensions that override zend_execute_ex(). JIT disabled. in Unknown on line 0

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

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

Добавлено 29.03.2024: Включил JIT несколько недель назад. Видимо, нью-релик выпустил новую версию, в которой проблема исправлена. Однако особого влияния на производительность по данным того же нью-релика не заметил. Значит, вычисления не являются бутылочным горлышком в коде движка.

Как покрыть тестами устаревший код?

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

Идея приемочных тестов в том, что приложение тестируется целиком, как есть. Для легаси-кода с процедурным подходом, хранением состояния в глобальных переменных, множеством точек выхода die/exit при ошибках и редиректах, перемешанной логикой и представлением чаще всего альтернатив нет.

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

Проще всего Codeception подключить к проекту через composer:

    "require-dev": {
        "codeception/codeception": "^4.2",
        "codeception/module-asserts": "^2.0.0",
        "codeception/module-phpbrowser": "^2.0"
    }

В проекте нужно создать файл codeception.yml:

suites:
    acceptance:
        actor: AcceptanceTester
        modules:
            enabled:
                - Asserts
                - PhpBrowser:
                      url: http://localhost:8881
                      curl:
                          CURLOPT_TIMEOUT_MS: 120000

После этого файлы тестов можно писать в таком cest-синтаксисе:

<?php

use Codeception\Example;

class InstallCest
{
    public function tryToTest(AcceptanceTester $I, Example $example): void
    {
        $I->install('admin', 'passwd', $example['db_type'], $example['db_user'], $example['db_password']);

        $I->amOnPage('/');
        $I->see('Site powered by S2');
        $I->click(['link' => 'Page 1']);
        $I->see('If you see this text, the install of S2 has been successfully completed.');
        $I->canWriteComment();
    }
}

Здесь методы amOnPage(), see(), click() — встроенные, а install() и canWriteComment() — мои сокращения, определенные в классе-тестере:

<?php

use Codeception\Actor;

class AcceptanceTester extends Actor
{
    public function install(string $userName, string $userPass, string $dbType, string $dbUser, string $dbPassword): void
    {
        $I = $this;
        $I->amOnPage('/');
        $I->seeLink('install S2', '/_admin/install.php');
        $I->amOnPage('/_admin/install.php');
        $I->seeResponseCodeIs(200);
        $I->see('S2 2.0dev', 'h1');

        $I->selectOption('req_db_type', $dbType);
        $I->fillField('req_db_host', '127.0.0.1'); // not localhost for Github Actions
        $I->fillField('req_db_name', 's2_test');
        $I->fillField('db_username', $dbUser);
        $I->fillField('db_password', $dbPassword);
        $I->fillField('req_username', $userName);
        $I->fillField('req_password', $userPass);
        $I->click('start');
        $I->canSeeResponseCodeIs(200);
        $I->see('S2 is completely installed!');
    }

    public function canWriteComment(): void
    {
        $I = $this;

        $name = 'Roman 🌞';
        $I->fillField('name', $name);
        $I->fillField('email', 'roman@example.com');
        $I->fillField('text', 'This is my first comment! 👪🐶');
        $text = $I->grabTextFrom('p#qsp');
        preg_match('#(\d\d)\+(\d)#', $text, $matches);
        $I->fillField('question', (int)$matches[1] + (int)$matches[2]);
        $I->click('submit');

        $I->seeResponseCodeIs(200);
        $I->see($name . ' wrote:');
        $I->see('This is my first comment!');
    }
}

Теперь посмотрим, как это всё запускается. Я написал отдельный скрипт:

# Очистка тестовой базы данных
mysql -uroot --execute="DROP DATABASE IF EXISTS s2_test; CREATE DATABASE s2_test;"

# Запуск веб-сервера
APP_ENV=test \
 PHP_CLI_SERVER_WORKERS=2 \
 nohup php \
  -d "max_execution_time=-1" \
  -d "opcache.revalidate_freq=0" \
  -S localhost:8881 >/dev/null 2>&1 &

serverPID=$!

# Запуск тестов
php _vendor/bin/codecept run acceptance

pkill -P $serverPID # Убиваем воркеры PHP, образовавшиеся из-за PHP_CLI_SERVER_WORKERS
kill $serverPID

Перед запуском тестов поднимается встроенный в php веб-сервер, обрабатывающий запросы по адресу http://localhost:8881/. Веб-сервер запускает несколько воркеров в параллель (PHP_CLI_SERVER_WORKERS=2), так как движок в процессе установки обращается сам к себе, чтобы понять, какая схема перезаписи URL доступна. В процессе установки создается файл config.php. Чтобы PHP сразу видел изменения в этом файле, пришлось переопределить параметр из php.ini: opcache.revalidate_freq=0. Альтернатива — добавить sleep(), но я не хотел играться с ненадежными способами. Переменная окружения APP_ENV=test говорит движку, чтобы он вместо файла config.php создавал и использовал файл config.test.php. Это упрощает запуск и тестов и обычной версии для разработки из одной папки.

Достоинства получившегося способа написания приемочных тестов следующие. Устаревший код приложения практически не нужно дорабатывать, чтобы писать тесты. Так как приложение тестируется через HTTP API, внутренние изменения в приложении, не меняющие API, не требуют доработки тестов. Тесты запускаются где угодно, я даже добавил запуск тестов в github actions при каждом пуше веток.

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

← сюда туда →