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 при каждом пуше веток.
Недостатки, как обычно, есть продолжения достоинств. Тесты покрывают только серверную часть,
Мысли о движке сайтов S2
В этом году я сделал несколько доработок своего движка сайтов S2, главная и самая заметная из которых — система рекомендаций. Я бы не стал об этом опять писать, если бы не одно но — до этого крупные доработки в движке я делал больше 8 лет назад. В этой заметке я хочу зафиксировать, как так получилось и что теперь с этим делать.
История
Историю движка можно проследить по тегу «S2». Главная проблема движка в том, что он был полем для моих экспериментов в процессе изучения
С другой стороны, в движке были и удачные находки. Например, шаблон страницы обрабатывается не только после подготовки данных, когда они подставляются в этот самый шаблон, но и до того, чтобы определить, какие именно данные нужны шаблону. Это позволяет гибко управлять функциональностью и не нагружать сервер лишней работой, если она не требуется для отображения текущей страницы. Такую оптимизацию я не встречал в других системах.
В
Со второй частью намерений не сложилось. Были желающие помочь развитию движка, но других активных разработчиков у движка так и не появилось.
Со временем я приобрел достаточный опыт в разработке и стал понимать, насколько тяжело дописывать новый код движка в старой парадигме. Я несколько раз пытался переписывать код с нуля. Сначала без фреймворков с «нормальным» объектным подходом (версия 2.0dev). Потом на микрофеймворке Silex. Потом авторы Silex отказались от его развития, и я подключил Symfony. Все эти попытки сделать версию 3.0 останавливались на том, что надо переделать на новую схему админку и расширения, и для такой объемной работы у меня не было времени и желания.
Одновременно с этим активность на форуме угасла. Авторы некоторых сайтов перенесли их на другие движки. Некоторых сайтов больше нет. Некоторые заброшенные сайты до сих пор работают на S2.
В итоге сейчас у движка больше нет пользователей, на которых надо ориентироваться.
Доработка
Недавно я решил просмотреть все заметки в блоге, удалить устаревшие заметки, актуализировать теги. На удивление некоторые заметки перечитал с удовольствием. Этот процесс вдохновил меня на то, чтобы залезть в код движка и посмотреть, что можно с ним сделать.
У меня получилось за 1 января (обычно бесполезный день) подключить к S2 версии 2.0dev свежую версию поискового движка Rose, и при этом сделать так, чтобы в общем кодовом пространстве движка сосуществовали устаревший код, на который больно смотреть, и новый код, с которым приятно работать. Такой быстрый прогресс открыл дорогу к тому, чтобы сделать уже упоминавшуюся систему рекомендаций.
Также я внес несколько менее масштабных, но не менее желанных изменений. Перенес
Еще подключил codeception — библиотеку для написания автотестов, и стал добавлять эти автотесты. Среди нескольких видов тестов пришлось выбрать приемочные (acceptance). В них выполняются настоящие
Продуктовый подход
Я как единственный оставшийся пользователь движка подошел к нему и своему сайту как к работающему продукту. Вместо того чтобы пытаться переписать движок с нуля на идеальной архитектуре, потратив непонятное количество времени, я сконцентрировался на том, какие фичи могу добавить прямо сейчас. Практика показала, что многое можно сделать в текущей версии, не переписывая ее код с нуля.
Альтернатива — забросить S2 и перейти на другой движок, хотя бы ту же Эгею Ильи Бирмана. Но для этого надо создать свою тему оформления, написать и отладить конвертер заметок, разобраться со старыми адресами URL, пройтись по всем заметкам и убедиться, что ни в одной ничего не сломалось (а ломаться есть чему: у меня есть заметки с нетривиальной версткой вроде рецензии на книгу о фильме «Интерстеллар»). Это значительный объем работы, которую нельзя делать понемногу, мелкими шагами. Мне проще было постепенно доработать свой движок.
Светлое будущее
S2 переехал на гитхаб, откуда его можно скачать. Версию 1.0 я пока что использую, поэтому еще некоторое время буду исправлять баги и проблемы совместимости со свежими версиями PHP. Новых фич в ней не будет. С версии 1.0 можно обновиться до 2.0dev, переработав стили.
Версию 2.0dev буду иногда дорабатывать на досуге. Не планирую свои сайты переводить с неё на
На вопросы возможных пользователей движка я отвечать не планирую. Я не вижу перспектив в том, чтобы у движка появлялись новые пользователи. Сейчас соцсети, облачные платформы и конструкторы сайтов не оставляют движкам типа S2
Чему же равно 6:2(1+2)?
Когда я впервые увидел этот пример в интернете, подумал, что это проблема на ровном месте. Да, мнения людей об ответе расходятся:
$${6\over 2(1+2)}={6\over 6}=1.$$
Борис Трушин смог снять по этой теме целых два видео по 18 минут:
После просмотра я сделал для себя такой вывод. Приоритет арифметических действий учат в начальной школе, а опускать знак умножения — только в средней школе. По характеру необходимых действий пример 6:2(1+2) — из начальной школы, поэтому он записан некорректно, умножение между двойкой и скобками опускать нельзя.
И совсем недавно мне попалось еще одно видео по теме. Оказывается, мнение о правильном ответе расходятся не только у спорящих в интернете, но и у производителей калькуляторов!
В этом видео отметил следующие вещи. Оказывается, около 100 лет назад еще были колебания в определении приоритета (явного) умножения и деления, но колебания приоритета неявного умножения над делением не было: если знак умножения опущен, выражение воспринимается единым целым, будто записано в скобках. К девяностым годам североамериканские учителя повлияли на производителей калькуляторов, чтобы те изменили приоритет неявного умножения и выровняли его с явным умножением и делением. Но так сделали не все производители, а сейчас происходит частичный откат к тому, что неявное произведение становится приоритетнее. Колебания приоритета неявного умножения относятся только обучению в школе, в профессиональном употреблении колебаний нет.
После просмотра этого видео я понял, что мой аргумент про использование двоеточия как знака деления в основном в начальной школе — это всего лишь отрицание проблемы. Действительно, использование горизонтальной черты для обозначения деления удобно в отдельных формулах, а не в сплошном тексте. Сейчас в математических текстах вместо двоеточия используется наклонная черта. Так что никто не мешает спросить, чему равно
Я решил посмотреть, как сам записывал в одну строку формулы с делением и неявным умножением, и какие приоритеты подразумевал. Прошелся по текстам в блоге о теоретической физике старше нескольких лет, чтобы исключить возможное влияние обсуждений этого вирусного примера. В выражении
Ради интереса взял с полки книгу начала прошлого века «The mathematical theory of electricity and magnetism». В ней тоже неявное умножение имеет более высокий приоритет перед делением, в чем легко убедиться, сравнив выражения 1/4πd в однострочной формуле и в двухэтажной дроби:
Раз уж мы обсуждаем приоритеты арифметических действий, поделюсь воспоминанием из начальной школы, кажется, из второго класса. Учительница нам говорила, что если в выражении на одном уровне несколько умножений и делений, то выполняются сначала деления, а потом умножения. Такого правила я больше нигде не встречал. Обычно учат, что умножение и деление выполняется подряд, слева направо. Например,
Задача о педантичном пассажире
В недавней поездке наблюдал, как люди рассаживаются в автобусе. Чтобы скоротать время в дороге, решил прикинуть, насколько тяжело пересаживаться людям, занимающим места не по билетам. Задачу пришлось решать в уме, так как черновика и ручки не было. Правда, был мобильник с интернетом, так что без чтения википедии и других сайтов не обошлось. Однако ничего полезного не нашел и решил задачу самостоятельно.
Условие
В автобусе n пронумерованных мест. Пассажиры занимают места в случайном порядке, не обращая внимание на номера в билетах. Последний пассажир оказывается педантичным — он хочет сидеть на своем месте. Если место педантичного пассажира занято, он заставляет сидящего там пассажира пересесть. Пересаживающийся пассажир тоже становится педантичным и идет на свое место. Процесс пересаживания продолжается до тех пор, пока последний педантичный пассажир не усядется в пустое место. Сколько в среднем пассажиров пересядет?
Математическая природа задачи
Знакомые с теорией представлений групп перестановок сразу скажут, какая идея скрывается за формулировкой задачи. Мне же придется пересказать некоторые математические факты, чтобы пояснить ход рассуждений.
Сидящие в
$$\begin{pmatrix} \text{места}\\ \text{билеты} \end{pmatrix}=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 6 & \bf{1^*} & 2 & 5 & 3 & 8 & 7 \end{pmatrix}.$$
Для удобства рассуждений будем считать, что педантичный пассажир имеет билет номер 1. (Интуитивно понятно, что ответ в задаче не зависит от конкретного номера билета у педантичного пассажира, но вы попробуйте это доказать в качестве упражнения.) Если бы пассажир не был педантичным, он просто занял бы свободное место с номером 3. Но поскольку пассажир педантичный, он заставляет пересесть пассажира 4, тот заставляет пересесть пассажира 2, дальше пересаживается пассажир 6 и, наконец, пассажир 3 идет на свое свободное место:
$$\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 \\ 4\ar[urrr,dotted,looseness=1,in=155] & 6\ar[urrrr,dotted,looseness=1,in=160] & 1\ar[ull,dotted] & 2\ar[ull,dotted] & 5 & 3\ar[ulll,dotted] & 8 & 7 \end{tikzcd}\right) \end{matrix}$$
Получившаяся цепочка (1 4 2 6 3) называется циклом.
Таким образом, в задаче фактически нужно найти среднюю длину цикла, содержащего случайно выбранный элемент случайной перестановки.
Погружение в теорию
Любая перестановка распадается на один или несколько циклов. В нашем примере это циклы $$(1\ 4\ 2\ 6\ 3)(5)(7\ 8)$$. Циклы могут иметь произвольную положительную длину. Единственное ограничение на циклы — сумма их длин равна n. Фактически циклическая структура перестановки описывается разбиением чисел.
Разбиения чисел, как и циклы в перестановках, изображают графически в виде диаграмм Юнга. Каждая строка этой диаграммы соответствует своему циклу, строки расположены в порядке убывания длины. В нашем примере диаграмма Юнга имеет вид:
$$\begin{tikzpicture}[scale=0.5]\small \draw[line width=0.22mm] (0,0) grid (5,-1) (0,-1) grid (2,-2) (0,-2) grid (1,-3); \end{tikzpicture}$$
Каждой диаграмме Юнга, в которой $$m_1$$ циклов длины 1, $$m_2$$ циклов длины 2 и т. д. соответствует следующее количество перестановок:
$$N={n!\over 1^{m_1}m_1!\cdot 2^{m_2}m_2!\cdot\ldots\cdot n^{m_n}m_n!}.$$
Давайте для тренировки проверим, что получится для нашей диаграммы Юнга:
$$N_{8 = 5 + 2 + 1}={8!\over 1^{1}1!\cdot 2^{1}1!\cdot 5^{1}1!}={8!\over 10}=4032.$$
Выходит, среди всех 8! = 40320 перестановок из 8 элементов десятая часть имеет структуру, описываемую разбиением 8 = 5 + 2 + 1.
Теперь надо перебрать все диаграммы Юнга, для каждой вычислить вес по этой формуле и усреднить длину строк с такими коэффициентами. Осталась «небольшая» проблема — я не знаю простого аналитического способа перебора диаграмм Юнга. Такой метод решения задачи заводит в тупик, особенно если решать в уме. Поэтому забудем всё, что здесь было написано, и будем решать задачу с нуля без
Решение «на пальцах»
Как было написано выше, мы будем вычислять среднюю длину цикла, содержащего первый элемент в случайной перестановке длины n. (Вместо первого элемента можно брать любой: из формул дальше видно, что ответ от этого не зависит.) Под средней длиной понимается математическое ожидание — усреднение длины цикла с весами, равными вероятностям:
$$L=P_1\cdot 1+P_2\cdot 2 +\ldots+P_n\cdot n,$$
где $$P_1$$ — вероятность того, что цикл имеет длину 1, $$P_2$$ — что имеет длину 2 и т. д. Ясно, что циклов с длиной больше чем полное количество элементов n не бывает, и слагаемые в формуле останавливаются на n.
В этой формуле легко подсчитать $$P_1$$. Так как перестановки случайные, элемент 1 с равной вероятностью может переводиться перестановкой в любой другой элемент от 1 до n. Если 1 переходит в 1, мы получаем цикл длины 1:
$$\begin{pmatrix} 1 & 2 & \ldots & n\\ 1 & * & \ldots & * \end{pmatrix}.$$
В противном случае длина цикла будет больше. Таким образом, $$P_1=1/n$$ — с такой вероятностью можно выбрать число 1 из первых n чисел.
Попробуем теперь вычислить $$P_2$$. Чтобы получился цикл длины 2, элемент 1 должен переходить в элемент $$k\neq 1$$, а элемент k — в 1:
$$\begin{pmatrix} 1 & \ldots & k & \ldots & n\\ k & \ldots & 1 & \ldots & *\\ \end{pmatrix}.$$
Есть $$n-1$$ способ выбрать первый элемент $$k\neq1$$, что дает вероятность $$(n-1)/n$$ (действительно, в противном случае мы бы получили цикл длины 1 с вероятностью $$P_1=1/n$$). Вторым элементом должен быть 1, его можно выбрать из оставшихся $$n-1$$ элементов с вероятностью $$1/(n-1)$$. Таким образом,
$$P_2={n-1\over n}\cdot{1\over n-1}={1\over n}.$$
Удивительно, но мы получили, что $$P_1=P_2=1/n$$. Давайте проверим, совпадение ли это, или закономерность. Цикл будет иметь длину 3, если его длина не 1 и не 2, и если третьим элементом мы выберем 1. Вероятность этого
$$P_3=\left(1-P_1-P_2\right)\cdot{1\over n-2}={n-2\over n}\cdot{1\over n-2}={1\over n}.$$
Аналогично все остальные вероятности тоже совпадают: $$P_i=1/n$$. Таким образом, средняя длина цикла $$L=(n+1)/2$$.
Вывод
В автобусе с количеством мест n педантичный пассажир спровоцирует $$(n+1)/2$$ пересадок. Или, если исключить его самого из этого числа, пересядет $$(n-1)/2$$ других пассажиров. Мы не только вычислили среднее количество пересаживающихся пассажиров, а еще и нашли распределение этого количества: оно оказалось равномерным. Иными словами, с равной вероятностью педантичный пассажир сядет в свое пустое место, или заставит пересесть одного пассажира, или двух и т. д. Все эти исходы оказываются равновероятными.
Послесловие
Простота ответа — пересесть должна половина автобуса — наводит на мысль о том, что задачу можно решить только с помощью некоторой наглядной картинки, вообще без вычислений. К сожалению, я пока не придумал, как это сделать. Например, можно мысленно переставить сиденья с пассажирами в один ряд так, чтобы в процессе пересаживания педантичный пассажир садился на случайное место, заставляя пересесть всех пассажиров справа от него на одно место. Ясно, что для такой вставки элемента среднее количество операций совпадает с вычисленным ответом. Но откуда возьмется связь между случайным циклом случайной перестановки и элементами справа от случайно выбранного элемента? Как между ними установить соответствие, сохраняющее вероятности?
И, наконец, если вы сомневаетесь в правильности ответа, можете запустить скрипт, вычисляющий ответ методом полного перебора. Алгоритм перебора перестановок взял из книжки. Сконвертировал код из Perl в PHP с помощью ChatGPT. Усреднение длины цикла делается тривиально.
<?php
function nextShuffle(array $shuffle): ?array {
for ($i = 1, $count = count($shuffle); $i < $count; $i++) {
if ($shuffle[$i] < $i) {
$shuffle[$i]++;
return $shuffle;
}
$shuffle[$i] = 0;
}
return null;
}
// Длина цикла, содержащего элемент 1.
function cycleLength(array $p): int {
$num = 1;
$result = 0;
while ($p[$num - 1] !== 1) {
$num = $p[$num - 1];
$result++;
}
return $result;
}
$n = (int)$argv[1];
if ($n <= 0) {
die("$argv[0]: Нужно неотрицательное число!\n");
}
$shuffle = array_fill(0, $n, 0);
$totalLength = 0;
$totalPermutations = 0;
while ($shuffle !== null) {
// Начальная перестановка
$p = range(1, $n);
// Применение транспозиций
for ($i = 0; $i < $n; $i++) {
$temp = $p[$i];
$p[$i] = $p[$shuffle[$i]];
$p[$shuffle[$i]] = $temp;
}
$length = cycleLength($p);
$totalLength += $length;
$totalPermutations++;
// echo implode(" ", $p), " | ", $length, "\n";
// Генерирование следующего набора транспозиций
$shuffle = nextShuffle($shuffle);
}
echo "Всего перестановок (факториал) = ", $totalPermutations, "\n",
"Среднее количество пересадок = ", $totalLength / $totalPermutations, "\n";
Пример результата запуска:
> php script.php 8
Всего перестановок (факториал) = 40320
Среднее количество пересадок = 3.5
Http-прокси на PHP
Обычно в постах о программировании я пишу об успешных подходах и находках. В этот раз расскажу об идее, которая на практике не заработала.
В прошлый раз я рассказывал, что если у вас есть свой виртуальный сервер, вы можете не возиться с VPN, а отправить трафик из браузера через
Я задумался, можно ли провернуть такой же трюк без своего виртуального сервера. Стал смотреть в сторону виртуальных (shared) хостингов, в частности бесплатных или предоставляющих бесплатный тестовый период. На hostings.info нашел бесплатный хостинг с доступом по SSH. Трюк с
Я стал думать дальше и решил попробовать другой вариант. На сервере хостера запущен PHP. Я могу подключиться к нему через обычный
<?php
require 'vendor/autoload.php';
use GuzzleHttp\Client;
use GuzzleHttp\Psr7\Request;
use GuzzleHttp\Psr7\ServerRequest;
// Создание экземпляра клиента Guzzle
$client = new Client();
// Обработка входящего запроса
$request = ServerRequest::fromGlobals();
// Получение URL-адреса запрашиваемого сайта
$url = $request->getUri();
$url
// Я собирался ходить на https-сайты, поэтому подменил протокол и порт
->withScheme('https')
->withPort(443)
// Подменяем хост (видимо, тут и происходит обработка протокола http-прокси)
->withHost($request->getHeaderLine('host'))
->withQuery($request->getUri()->getQuery())
;
// Создание прокси-запроса
$proxyRequest = new Request(
$request->getMethod(),
$url,
$request->getHeaders(),
$request->getBody(),
$request->getProtocolVersion()
);
// Отправка прокси-запроса и получение ответа
$response = $client->send($proxyRequest, [
'stream' => true,
'verify' => false,
'allow_redirects' => false, // Коды редиректов отправляем назад в браузер
]);
// Передача заголовков ответа клиенту
foreach ($response->getHeaders() as $name => $values) {
foreach ($values as $value) {
header(sprintf('%s: %s', $name, $value), false);
}
}
// Передача тела ответа клиенту
echo $response->getBody();
Чтобы этот скрипт завести, нужно сохранить его в файл со произвольным редким названием, например, q7e6r53t.php, и установить через composer библиотеку guzzle. Кроме того, в nginx в настройку хоста надо добавить следующее:
server {
listen 8082;
server_name localhost;
root /mnt/c/git/proxy;
location / {
try_files $uri $uri/ /q7e6r53t.php$is_args$args;
}
location ~ \q7e6r53t.php$ {
fastcgi_split_path_info ^(.+\.php)(/.+)$;
fastcgi_pass unix:/var/run/php/php7.4-fpm.sock;
fastcgi_index index.php;
include fastcgi.conf;
}
}
В таком варианте прокси заработал локально, даже с авторизацией и куками. Самый большой недостаток этого подхода в том, что нельзя проксировать
127.0.0.1 - - [18/Jun/2023:12:56:47 +0300] "CONNECT www.google.com:443 HTTP/1.1" 400 166 "-" "-"И даже если вдруг представить, что такое возможно, это был бы man in the middle. Поэтому в браузере приходится набирать адрес сайта с http, а скрипт подменяет протокол на https. Если в PHP нет нужных сертификатов, подключиться к сайту будет невозможно. Для отключения проверки сертификатов я добавил флаг 'verify' => false. Конечно, это несекьюрно, но тут и так трафик передается хостеру в открытом виде, так что держать ворота запертыми в открытом поле смысла нет :)
На практике у хостера этот скрипт не заработал. В браузере отображалась страница ошибки Apache о неправильно сконфигурированном хосте. Очевидно, Apache настроен так, чтобы не позволять так просто делать
В ходе лабораторной работы мы написали простейший скрипт
Эксперименты и использование ChatGPT
Успехи
Самое большое впечатление он произвел, когда решил задачу по SQL с моих собеседований: моментально выдал абсолютно точный запрос, хотя не все кандидаты могут его написать даже после подсказок. Правда, потом я спросил, какие индексы нужны для этого запроса, и он немного поплыл (предложил индекс и на колонку в where, и на колонку в group by, и на обе этих колонки), но тем не менее.
Не хочу копировать сюда задачу с собеседования, поэтому для иллюстрации посмотрим другую задачу. Вот какой получился диалог (курсивом выделил свои реплики):
В таблице в БД хранятся древовидные записи. Есть колонки id, parent_id и text. Напиши запрос, который выводит записи в виде дерева: чем глубже запись в дереве, тем больше должно быть отступов
Для вывода записей в виде дерева с отступами можно использовать рекурсивный запрос с помощью общей таблицы выражений (CTE) в SQL. Ниже приведен пример запроса для базы данных MySQL:
WITH RECURSIVE tree AS ( SELECT id, parent_id, text, 0 AS level FROM my_table WHERE parent_id IS NULL UNION ALL SELECT t.id, t.parent_id, t.text, tree.level + 1 FROM my_table t JOIN tree ON t.parent_id = tree.id ) SELECT CONCAT(REPEAT(' ', level * 2), text) AS tree_view FROM tree ORDER BY id;В этом запросе используется общая таблица выражений tree, которая содержит две части:
Базовый запрос выбирает корневые узлы дерева (те, у которых parent_id равен NULL), задает начальный уровень level = 0 и добавляет их в таблицу tree.
Рекурсивный запрос выбирает дочерние узлы дерева, соединяя таблицу my_table с таблицей tree, используя ключ parent_id = id. Он также увеличивает уровень level на 1 и добавляет эти узлы в таблицу tree.
Затем запрос выводит каждую запись с отступом, который рассчитывается как уровень узла умноженный на два пробела, и сортирует записи по их идентификатору.
Примечание: запрос может потребоваться адаптировать для конкретной базы данных в зависимости от синтаксиса.
Сгенерируй запрос, создающий такую таблицу, и заполняющий ее записями
Ниже приведен пример запроса на языке SQL, который создает таблицу с тремя колонками (id, parent_id и text) и заполняет ее несколькими записями:
CREATE TABLE my_table ( id INT PRIMARY KEY, parent_id INT, text VARCHAR(255) ); INSERT INTO my_table (id, parent_id, text) VALUES (1, NULL, 'Node 1'), (2, 1, 'Node 1.1'), (3, 1, 'Node 1.2'), (4, 2, 'Node 1.1.1'), (5, 2, 'Node 1.1.2'), (6, 3, 'Node 1.2.1'), (7, NULL, 'Node 2'), (8, 7, 'Node 2.1'), (9, 7, 'Node 2.2');Этот запрос сначала создает таблицу my_table с тремя колонками: id, parent_id и text. Колонка id определена как первичный ключ.
Затем запрос заполняет таблицу несколькими записями с разными значениями для id, parent_id и text. В этом примере мы создали простое дерево с двумя уровнями и несколькими дочерними узлами, чтобы продемонстрировать, как можно использовать рекурсивный запрос для выборки записей в виде дерева с отступами.
Дальше я скопировал запросы в консоль, и они выполнились без единой ошибки!
MariaDB [s2_test]> CREATE TABLE my_table (
-> id INT PRIMARY KEY,
-> parent_id INT,
-> text VARCHAR(255)
-> );
Query OK, 0 rows affected (0.033 sec)
MariaDB [s2_test]> INSERT INTO my_table (id, parent_id, text)
-> VALUES
-> (1, NULL, 'Node 1'),
-> (2, 1, 'Node 1.1'),
-> (3, 1, 'Node 1.2'),
-> (4, 2, 'Node 1.1.1'),
-> (5, 2, 'Node 1.1.2'),
-> (6, 3, 'Node 1.2.1'),
-> (7, NULL, 'Node 2'),
-> (8, 7, 'Node 2.1'),
-> (9, 7, 'Node 2.2');
Query OK, 9 rows affected (0.004 sec)
Records: 9 Duplicates: 0 Warnings: 0
MariaDB [s2_test]> WITH RECURSIVE tree AS (
-> SELECT id, parent_id, text, 0 AS level
-> FROM my_table
-> WHERE parent_id IS NULL
->
-> UNION ALL
->
-> SELECT t.id, t.parent_id, t.text, tree.level + 1
-> FROM my_table t
-> JOIN tree ON t.parent_id = tree.id
-> )
-> SELECT CONCAT(REPEAT(' ', level * 2), text) AS tree_view
-> FROM tree
-> ORDER BY id;
+----------------+
| tree_view |
+----------------+
| Node 1 |
| Node 1.1 |
| Node 1.2 |
| Node 1.1.1 |
| Node 1.1.2 |
| Node 1.2.1 |
| Node 2 |
| Node 2.1 |
| Node 2.2 |
+----------------+
9 rows in set (0.001 sec)Данные выведены ровно так, как я попросил. Обратите внимание, что я не думал долго и сформулировал условие небрежно (что такое «древовидные записи»?) и скорее на уровне идеи, а не требований к результату. Я будто написал коллеге, с которым давно работаем, и получил ожидаемый результат.
Провалы
Я пробовал ChatGPT в более серьезных задачах. Результат был менее впечатляющим. Например, мне нужен был алгоритм разбиения абзаца на предложения. ChatGPT выдавал варианты, но они не учитывали все условия, и докрутить у меня не получилось. Пришлось использовать идеи со
Если спрашивать у ChatGPT решение отвлеченных задач, получается ерунда. С загадкой для младших классов ChatGPT не справился даже после 5 уточняющих вопросов. Угадал ответ, но обоснование всё равно осталось в корне неверным:
раздели полста на половину
Если мы разделим 50 на половину, то мы должны разделить его на 2. Это даст нам ответ 25.
Таким образом, ответ на задачу «раздели полста на половину» равен 25.
половина — это не 2
Вы правы, прошу прощения за ошибку в моем предыдущем ответе.
Если мы хотим разделить 50 на половину, то это означает, что мы делим его на 2 равные части. Половина от 50 равна 25, поэтому ответ на задачу «раздели полста на половину» также будет 25.
нет, половина — это 1/2
Вы абсолютно правы, прошу прощения за мою путаницу в ответах.
Разделив 50 на половину, мы делим 50 на две равные части. Половина от 50 — это 50 умножить на 1/2, то есть 25. Таким образом, ответ на задачу «раздели полста на половину» равен 25.
Спасибо за исправление моей ошибки!
Почему умножить? Мы же делим!
Действительно, я снова ошибся, искренне извиняюсь.
Разделив 50 на половину, мы делим 50 на 2 равные части. Поскольку половина означает деление на две равные части, то можно напрямую получить ответ, просто разделив 50 на 2, без использования умножения.
Таким образом, правильный ответ на задачу «раздели полста на половину» равен 25. Еще раз извиняюсь за путаницу в предыдущих ответах.
Это загадка, и у нее ответ не на поверхности. Перепроверь всё еще раз
Прошу прощения, я недостаточно внимательно прочитал ваш предыдущий комментарий. Если это загадка, и ответ на нее не на поверхности, то я могу попросить вас задать вопрос еще раз или дать больше информации о том, что вы имели в виду, чтобы я мог правильно понять и помочь вам.
Раздели полста на половину
Я понимаю, теперь я понимаю, что вы задали мне загадку. Ответ на эту загадку — это число 100.
Давайте рассмотрим это более подробно. Половина от 50 равна 25, как мы уже обсуждали. Но если мы рассмотрим число 50 как «полста», то разделив его на половину, мы можем получить 100, потому что «полста» означает 50, а половина от 50 равна 25, так что 50 плюс 25 даст нам 75.
Таким образом, ответ на загадку «раздели полста на половину» — это число 100.
Надо понимать, что ChatGPT легко генерирует подобную ерунду. Вот пример:
Мало того, что такой задачи не существует. Так и в самом тексте содержится фактическая ошибка: последнее утверждение «магнитное поле Земли имеет дипольную структуру и не может взаимодействовать напрямую с магнитным монополем» просто неверно.
Я уже было подумал, что он генерит подобную чушь в ответ на любой некорректный запрос. Но после
Знаешь закон Лермонтова — Смита?
Я не знаком с законом
Лермонтова-Смита, потому что это не является широкоизвестным законом или принципом в науке или в других областях. Если у вас есть дополнительная информация о нем, я могу попробовать помочь вам разобраться в нем лучше.
Но стоит немного изменить вопрос, как мы опять получаем ерунду:
Я пробовал сгенерировать пост для блога в ChatGPT, в частности, о состояниях долгоживущих процессов. Получались тексты с кучей воды и без деталей, я в таком стиле не пишу. В итоге полностью переписал весь текст. Но некоторые «мысли» пришлись кстати и остались даже в переписанном тексте.
Как можно применять ChatGPT?
Оставим в стороне очевидные вещи вроде переводов, сочинений, курсовых и дипломных работ. Для себя увидел возможность применения в следующих сценариях.
В скучных и рутинных задачах. Например, в разработке можно попросить следующее: сгенерировать простую функцию, шаблон класса,
При нехватке навыков и компетенций. Мне недавно пришло письмо от пользователя Upmath с просьбой добавить поддержку корейского языка. Я попросил ChatGPT написать ответ. Получилось неплохо, с учетом всяких формул вежливости и прочих правил деловой переписки. Также я просил исправить стилистические ошибки в некотором тексте на английском. Если мне варианты кажутся равнозначными, есть смысл положиться на нейросеть, повидавшую весь интернет.
Как стартовую точку в изучении новой темы. Раньше такой входной точкой был гугл с постоянным уточнением поисковых запросов (интересно, кстати, сильно ли влияет гугл на работу человеческого мышления, потому что мы раньше не общались поисковыми запросами без регистрации без смс). Сейчас можно спросить у ChatGPT. Хоть ответ и надо перепроверять, не нужно отбиваться от «оптимизированных» сайтов, сюда сеошники еще не пролезли.
Чтобы побороть страх чистого листа. Не то, чтобы у меня есть такой страх. Но мне действительно проще редактировать уже готовый черновик, чем написать с нуля такой же текст. Мозг переключается в режим критика, который лучше всех знает, как правильно. А когда критиковать нечего и ограничений мало, бывает сложно сделать первый шаг в решении задачи.
Понятно, что ChatGPT — это еще не тот искусственный интеллект, о котором мечтали фантасты. Но всё равно создание системы, которая может «понять» запрос на живом языке и выдать адекватный ответ — это уже большой прорыв в этой области. Пока мы обсуждали прикладные вопросы, пост и так уже получился длинным. Так что пофилософствуем и пофантазируем мы уже в следующий раз.
Фишинг
Пришло качественно сделанное фишинговое письмо, я даже мог бы попасться. Смотрите:
- Релевантная тема и момент. Сегодня действительно мог истечь срок оплаты домена, если бы я его заранее не продлил.
- Письмо не попало в спам, и гугл даже распознал его как важное.
- В клиенте на мобильном телефоне не отображается электронная почта отправителя, просто написано «Beget». То, что я выделил желтым на скриншоте ниже, в мобильном приложении не отображается.
Я сразу полез проверять, что там с балансом. Подумал, что домен не продлился. Оказалось, что с балансом всё нормально. Я пришел к выводу, что внутри сервисов Бегета произошла
Ссылка в письме, разумеется, поддельная. Ради интереса открыл в режиме «инкогнито». При переходе сначала просит ввести капчу, а затем направляет на экран оплаты. В дополнение к пунктам выше смогли еще и пару сайтов взломать.
Сумма на форме примерно в 5 раз больше стоимости настоящего продления (289 рублей). Не удивлюсь, если за этой формой окажется окошко для ввода пароля из смс, а с карты спишут, скажем, 16 460 рублей.
Вывод всегда один: не переходите по ссылкам из писем, открывайте важные сайты самостоятельно.