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-токенов
Недавно Фёдор Борщёв написал о том, что разделение на
У нас на работе для единого входа в приложения (SSO) и получения ролей используется Keycloak. В целом он работает нормально, но иногда подтекает по памяти и начинает отвечать ошибками типа 502. В этот момент приложение тоже становится недоступным: когда истекает время жизни
Чтобы уменьшить влияние недоступности сервиса авторизации на работающее приложение и предотвратить потерю денег, мы придумали переиспользовать истекшие токены и назвали этот прием «воскрешением». Время жизни
Для рассматриваемого
Разумеется, события воскрешения токенов регистрируются в мониторинге, на них установлены уведомления в рабочие чаты. График в мониторинге во время инцидента может выглядеть примерно так:
На графике красным отображаются воскрешения токенов, желтым — запросы новых
Кстати, на графике применен еще один полезный прием: ошибочные события, отображаемые красным, выделены на отдельную ось и растут вниз (им формально приписан знак минус). Я сделал так, чтобы у единичных ошибочных событий и у сотен или тысяч успешных событий был разный масштаб, тогда единичные ошибочные события хорошо заметны.
В этой заметке мы рассмотрели некоторые способы обеспечения обеспечения отказоустойчивости и наблюдаемости (observability). Я присвоил ей тег «работа программиста», потому что это действительно работа программиста — подумать об этих нефункциональных требованиях и о том, как их выполнить. К вам никто не придет и не скажет
RSS, формулы и Feedly
Постоянные читатели помнят, что у меня есть сервис по превращению математических формул в картинки и редактор для создания математических текстов. С заменой формул на картинки на обычных
Еще в 2011 году я стал отдавать в RSS растровые картинки, потому что непонятно, в каком окружении будет отображаться контент оттуда. А на обычных
Когда в 2013 году прекратила работать
У Feedly была одна особенность с отображением картинок: они принудительно становились плавающими (включалось
Сейчас я решил проверить, не научился ли Feedly отображать нормально картинки. Оказалось, что научился. Если вы читаете этот текст через RSS в Feedly, можете в этом убедиться в предыдущем абзаце.
Чтобы два раза не вставать, я попросил ChatGPT составить
<?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>
Чтобы это заработало, нужно добавить ссылку на такой
<?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 нормально отображает картинки только в
Еще одно решение задачи о педантичном пассажире
В прошлый раз я решал задачу о педантичном пассажире с помощью комбинаторных соображений и получил простой ответ: если один из пассажиров в автобусе захочет сидеть на своем месте, пересесть в среднем должна примерно половина автобуса. Напомню, что задача свелась к вычислению средней длины цикла в перестановке, содержащего некоторый элемент, например, 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 влияет только одна настройка, но она не 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
Поиск проблемы в интернете быстро подсказал причину: расширение для
Попробую JIT
Добавлено 29.03.2024: Включил JIT несколько недель назад. Видимо,
Как покрыть тестами устаревший код?
Многим разработчикам приходилось поддерживать и дорабатывать устаревшие приложения, в которых никогда не было автотестов. С помощью приемочных тестов библиотеки Codeception можно покрыть
Идея приемочных тестов в том, что приложение тестируется целиком, как есть. Для
Я расскажу на примере 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
После этого файлы тестов можно писать в таком
<?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 при каждом пуше веток.
Недостатки, как обычно, есть продолжения достоинств. Тесты покрывают только серверную часть,