Hacker News Digest

Архив Эдсгера Дейкстры содержит более тысячи его неопубликованных рукописей, известных как "EWDs", которые он рассылал десяткам получателей на протяжении более 40 лет. Дейкстра, один из основоположников компьютерных наук (1930-2002), внёс фундаментальный вклад в алгоритмы, языки программирования, операционные системы и формальную верификацию, за что получил высшую награду ACM - премию Тьюринга. Большинство его работ остались недоступными для широкой публики, пока не были оцифрованы и представлены на этом сайте в виде PDF-документов.

Исходные материалы, включая дневники и переписку, хранятся в Техасском университете. Архив включает несколько индексов для поиска, а также растущее количество транскрибированных текстов и переводов на разные языки. Дейкстра часто возвращался к уже обсуждавшимся темам, предлагая новые взгляды или более точные формулировки, что отражено в системе перекрёстных ссылок между документами.

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

• LLM-энтузиасты и скептики продолжают спор о том, действительно ли нейросети могут решать задачи, которые они «видели» ранее, и насколько это важно.
• AlphaEvolve показал, что LLM может быть использована как часть эволюционного цикла, но не как единственный инструмент, и что это может быть применимо к математике.
• Обсуждение выявило, что важно различать «решение задачи» и «поиск решения»; LLM может быть полезна для последнего, но не для первого.
• Участники обсуждения отметили, что важно не забывать о том, что LLM не является универсальным инструментом, и что важно продолжать развивать и другие инструменты.

Grayskull — это компактная библиотека компьютерного зрения на C без зависимостей, созданная специально для встраиваемых систем, дронов и робототехники. Её минималистичный дизайн позволяет использовать даже на устройствах с ограниченными ресурсами, сохраняя при этом функциональность для базовых задач компьютерного зрения. Библиотека фокусируется на эффективности и простоте интеграции в существующие проекты.

Разработчики позиционируют grayskull как альтернативу более тяжёлым решениям, подчёркивая её лёгкость и универсальность. Ключевое преимущество — отсутствие внешних зависимостей, что упрощает компиляцию и развертывание на различных платформах. Библиотека идеально подходит для проектов, где важна производительность и минимальный размер исполняемого кода.

• Пользователи обсуждали, что вместо использования готовых библиотек вроде OpenCV, они предпочитают реализовывать алгоритмы с нуля на C, чтобы лучше понять, что происходит под капотом.
• Участник поделился опытом попытки написать собственную реализацию OpenCV на C, но проект был приостановлен из-за потери интереса к компьютерному зрению.
• Другой участник упомянул, что вместо того, чтобы изучать готовые решения, он предпочитает читать исходный код, чтобы понять, как работает алгоритм.
• Была также поднята тема того, что вместо использования готовых решений, лучше уделять время изучению основ и первопричин.
• Участники сошлись на том, что важно понимать, что стоит за конкретной техникой или инструментом, и что важно не просто использовать инструмент, но и понимать, как он работает.

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

Этот культурный сдвиг, затрагивающий все сферы общества, начался задолго до интернета и имеет как положительные, так и отрицательные стороны. С одной стороны, это "чудесное и фантастическое" явление, достойное торжеств; с другой — "мрачное и депрессивное", требующее вмешательства. Автор подчеркивает, что многие ошибочно связывают эти изменения только с интернетом или ограничивают их одной сферой жизни, тогда как на самом деле это комплексное явление с едиными корнями.

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

Онлайн-сообщество недавно определило BB(5) = 47,176,870, первый большой прорыв в проблеме "busy beaver game" за 50 лет. Следующая цель - BB(6), но исследователи не ожидают её достижения в ближайшее время из-за программы Antihydra, которая напоминает нерешенную математическую проблему Collatz conjecture.

Busy beaver numbers измеряют сложность вычислений, которые могут выполнить простые компьютерные программы. В этих исследованиях программы представлены машинами Тьюринга - гипотетическими устройствами, считывающими и записывающими 0 и 1 на бесконечной ленте. Каждая машина имеет уникальный набор правил, определяющих её поведение.

Antihydra представляет особую сложность, так как её поведение тесно связано с проблемой Collatz conjecture, одной из самых известных нерешенных задач в математике. Эта связь делает BB(6) практически недостижимым для точного определения в обозримом будущем.

• Обсуждение охватывает от Busy Beaver до Collatz, от теории вычислимости до философии случайности и даже до SETI@home и Bitcoin, показывая, насколько широко разросся этот меметический вирус.
• Участники обсуждают, как быстро растет функция BB(n), и как она влияет на наше понимание пределов вычислимости и случайности.
• Обсуждается, что даже если бы мы знали BB(5) или BB(6), это бы не дало нам практического способа вычислить BB(6) или выше; вопрос остаётся открытым, что делает эту область столь интригующей.
• Участники также затрагивают вопрос о том, как публикация в блогах может влиять на восприятие этой темы и как можно было бы лучше донести эти идеи до широкой аудитории.
• В конце обсуждение смещается к тому, что даже если бы мы могли бы вычислить эти числа, мы бы всё равно не могли бы их сравнить с чем-то, потому что они бы оказались слишком большими, чтобы иметь какое-либо значение в контексте чего-либо, кроме как самоограничения.

Advent of Code 2025 — это календарь программистических головоломок на каждый день декабря, доступных для решения на любом языке программирования. Созданный Эриком Вастлом, этот проект подходит для любого уровня подготовки — от новичков до опытных разработчиков. Участники используют его для подготовки к собеседованиям, обучения в компаниях, университетских курсов или просто для практики. Не требуется глубоких знаний компьютерных наук — достаточно базовых навыков программирования и решения задач. Все задачи можно решить на десятилетнем оборудовании за не более 15 секунд.

Проект поддерживается через AoC++ и социальные сети. Если вы застряли, автор советует проверять решения на примерах, создавать тестовые случаи и обращаться за помощью в subreddit. В разделе FAQ освещены вопросы аутентификации через OAuth, сложности задач (которые обычно возрастают со временем), разблокировки задач в полночь по EST, а также возможность участия в соревнованиях через приватные рейтинги.

• Сокращение до 12 дней вместо 25 вызвало бурную дискуссию: часть сообщества считает, что это разрушает саму суть "Advent of Code", в то время как другие отмечают, что это снизит нагрузку на автора и позволит ему продолжать проект.
• Пользователи отмечают, что сокращение до 12 дней делает невозможным привычное соревнование за лидербордом, и что это может оттолкнуть некоторых участников.
• Некоторые участники выразили обеспокоенность тем, что сокращение может повлиять на качество головоломок, так как автор будет иметь меньше времени на их разработку.
• Некоторые участники предложили альтернативы, такие как выпуск головоломки каждые два дня вместо ежедневного выпуска, что позволило бы сохранить привычный формат мероприятия.
• Участники также обсудили, что сокращение до 12 дней может повлиять на их собственные планы на декабрь, и что они могут не успеть решить головоломки до Рождества, что для них является важным элементом мотивации.

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

На примере Судоку автор демонстрирует, как преобразовать правила игры в систему булевых ограничений. Для каждой клетки (i,j) и цифры k вводится переменная x_{i,j,k}, где true означает, что клетка содержит цифру k. Правила игры переводятся в ограничения: каждая клетка должна содержать ровно одну цифку (x_{i,j,1} ∨ x_{i,j,2} ∨ ... ∨ x_{i,j,9} и ¬x_{i,j,k} ∨ ¬x_{i,j,l} для k≠l), каждая цифра должна встречаться ровно один раз в строке, столбце и под-сетке. SAT-солвер находит удовлетворяющее всем этим ограничениям присвоение значений переменным, решая головоломку.

• SAT и MILP-солверы недооценены: первые хорошо знакомы инженерам, вторые — нет, хотя MILP позволяет естественно выразить оптимизацию и ограничения.
• Исторически открытые MILP-солверы отставали от коммерческих, что сдерживало их использование.
• SAT-солверы и MILP-солверы дополняют друг друга: SAT хорошо для задач «есть/нет», MILP — для задач оптимизации.
• Практически любую задачу можно выразить как MILP, и SAT-солверы могут быть использованы для решения MILP.

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

• Обсуждение всплеснуло в спор о пропаганде, цензуре и поляризации, а не о самом ролике 1947 года.
• Участники обсуждения обвиняют друг друга в разжигании розни, в то время как ролик призывает к единству.
• Некоторые комментаторы указывают, что ролик сам по себе является пропагандой, и что его использование в современном контексте может быть неуместным.
• Обсуждение также затронуло тему алгоритмических лент и их влияния на общественное мнение.
• Некоторые комментаторы выразили обеспокоенность тем, что ролик может быть использован для оправдания насилия или дискриминации.

В среднем люди проводят в смартфонах по 4 часа 37 минут ежедневно, причём в ЮАР этот показатель достигает 5 часов 11 минут. Для автора это неприемлемо, так как он ценит живое общение и пребывание в настоящем моменте.

Он делится личным опытом: на телефоне уходит всего 30 минут в день, в основном на полезные задачи вроде банкинга и сообщений. Секрет — в осознанном подходе. Например, он удалил соцсети, чтобы убрать соблазны. А ещё отключил историю просмотров в YouTube, чтобы алгоритм не подсаживал на бесконечные рекомендации.

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

• Участники обсуждали, как технологические компании стимулируют зависимость от устройств, и как можно противостоять этому, включая использование телефонов с ограниченной функциональностью, отказ от push-уведомлений и использование приложений в браузере вместо нативных приложений.
• Обсуждались стратегии, как не дать алгоритмам контролировать внимание, включая отключение рекомендаций на YouTube, использование RSS и браузерных расширений вроде Unhook и uBlock Origin для блокировки рекламы и дистракций.
• Участники делились личным опытом, как они ограничивают собственное использование технологий, включая использование телефонов с ограниченной функциональностью, отказ от push-уведомлений и использование ноутбуков вместо телефонов для работы вне дома.
• Обсуждались влияние этих стратегий на продуктивность, фокус и психическое здоровье, включая то, как технологические компании могут быть более ответственными в дизайне своих продуктов.
• Участники также обсуждали, как можно было бы использовать технологии в более осознанном и умеренном режиме, включая использование их для творчества и продуктивности, вместо потребления.

К сожалению, в вашем запросе нет достаточной информации для создания пересказа статьи. Вы предоставили только название "Pointer Pointer" и сообщение о необходимости включить JavaScript для работы приложения.

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

• Старый проект pointerpointer.com (2006) использует JSON-файл с 700+ фото и алгоритм выбирает ближайшее по положению курсора, что делает невозможным «подглядывание» за кадром.
• Пользователи спорят, были ли фото подобраны вручную или с помощью OpenCV, но большинство склоняется к ручному отбору.
• Ностальгия и культурный феномен: обсуждение вызвало волну воспоминаний и вопрос о том, как именно собирались эти изображения.
• Пользователь предложил форк с котами, которые бы «ловили» курсор лапками.

Amazon превратилась из удобного сервиса в источник разочарования для многих пользователей. Основные проблемы включают переполненность платформы поддельными товарами и контрафактной продукцией, что затрудняет поиск качественных items. Алгоритмы рекомендаций часто продвигают низкокачественные продукты, а поисковая система манипулируется продавцами.

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

• Пользователи жалуются на проблемы с доставкой не тех товаров, подделок и сложности с возвратами и возмещениями.
• Многие отмечают ухудшение качества сервиса: медленную доставку, замусоренный поиск и навязчивую рекламу.
• Некоторые пользователи, особенно из Индии и Японии, довольны сервисом, отмечая скорость, цены и удобство возвратов.
• Распространена практика поиска товаров на Amazon для сравнения, но покупки у других продавцов или напрямую.
• Обсуждается общая тенденция «засорения» платформ из-за политики открытых маркетплейсов и третьих продавцов.

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

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

• Участники отмечают сильные стороны Ada, такие как ограниченные числовые типы для предотвращения ошибок, выразительная система типов и удобочитаемость, но сожалеют о его недостаточном распространении вне сообщества safety-critical разработки.
• Rust ценится за безопасность памяти, фокус на надежности и растущую экосистему, но критикуется за отсутствие формальной спецификации (хотя она сейчас разрабатывается) и сложность с компилятором и асинхронностью.
• Поднимаются вопросы о различиях в подходах к строкам (Ada использует массивы символов, Rust — UTF-8), многопоточности (встроенные потоки vs. async) и индексации массивов (произвольные типы в Ada vs. словари в Rust).
• Обсуждаются практические аспекты: скорость компиляции, поддержка Unicode, необходимость спецификаций и влияние экосистемы (инструменты, библиотеки) на выбор языка.
• Упоминаются нишевые применения Ada (например, в 3D-печати) и потенциальные заимствования его функций (ограниченные типы) в другие языки, такие как Rust, C++ и Nim.

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

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

• Обсуждение затрагивает различные типы diff-алгоритмов (одномерные, многомерные, древовидные) и их применение, включая сравнение кода, JSON-структур и даже схем баз данных.
• Участники делятся инструментами для просмотра diff (например, diff2html, meld, Beyond Compare) и отмечают проблемы существующих библиотек, такие как неожиданное экранирование текста.
• Поднимаются вопросы о важности минимальности diff, семантического понимания перемещений блоков и использования метаданных для улучшения алгоритмов.
• Обсуждаются практические применения diff-алгоритмов за пределами контроля версий: в тестировании, юридической сфере, сравнении расписаний и обновлении терминальных экранов.
• Упоминаются конкретные личности (например, Джин Майерс) и работы (статья Nugroho 2019 года), а также выражаются пожелания по улучшению алгоритмов, например, для работы с перемещенными данными.

Концепция «рынка лимонов» объясняет, как асимметрия информации разрушает рынки: покупатели не могут отличить качественные товары от низкосортных, поэтому всё продаётся по средней цене. Это вытесняет добросовестных продавцов, оставляя лишь «лимоны» — продукты, чья реальная ценность ниже ожидаемой.

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

• Обсуждается феномен «рынка лимонов» на платформах вроде Amazon, где сложно отличить качественные товары от низкокачественных из-за обилия безымянных брендов (например, MZOO, YFONG) и асимметрии информации.
• Отмечается, что снижение барьеров для выхода на рынок (дизайн, производство) привело к потоку массовых товаров, вытесняющих уникальные и качественные продукты, что особенно заметно на примере Etsy и Amazon.
• Участники подчёркивают важность курации, проверенных обзоров (Wirecutter) и сарафанного радио для навигации в условиях переизбытка вариантов и снижения доверия к брендам.
• Высказывается мнение, что китайские бренды иногда предлагают инновационные и качественные товары, вопреки стереотипам, но их сложно идентифицировать среди множества похожих предложений.
• Затрагивается влияние политики платформ (например, требование Amazon к брендингу) на появление множества псевдобрендов и усугубление проблемы «лимонов».

В шахматах не существует достижимой позиции, где у стороны было бы более 218 ходов. Это доказано компьютерным анализом, подтверждающим композицию гроссмейстера Ненада Петровича 1964 года. Попытки превзойти этот рекорд предпринимались десятилетиями, но все они провалились из-за математических ограничений и огромного количества возможных позиций — примерно 8,7×10^45.

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

• Обсуждение касается статьи о максимальном количестве возможных ходов (218) в достижимой позиции в шахматах, а не о количестве ходов для её достижения.
• Участники уточняют терминологию и выражают признательность Lichess за бесплатные возможности и варианты игры.
• Поднимаются технические вопросы о доказательстве оптимальности решения через решатель Gurobi и методах кодирования шахматных позиций.
• Обсуждается достижимость приведённой в статье позиции и влияние упрощения правил на модель.
• Автор статьи (Tobs40) участвует в обсуждении, поясняя свой метод и подтверждая доказательность результата.

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

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

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

• Критика отсутствия чёткого определения понятия «вычисление» и спекулятивного характера аналогий между биологией и информатикой.
• Обсуждение возможности моделирования жизни как вычисления, но не отождествления этих процессов, с оговоркой о необходимости строгих определений.
• Упоминание альтернативных концепций, таких как прогностическая обработка, иерархия Хомского и принцип вычислительной эквивалентности Вольфрама.
• Скептицизм по поводу детерминизма жизни и редукционистского подхода, игнорирующего её сложность, стохастичность и emergent-свойства.
• Замечание о том, что подобные аналогии являются продуктом человеческого абстрактного мышления и не существуют в природе в явном виде.

Новички в программировании часто зацикливаются на изучении структур данных и алгоритмов (DSA), потому что это проверяется на собеседованиях. Однако в реальной работе редко приходится реализовывать сложные алгоритмы вручную — вместо этого стоит понять базовые структуры, их trade-offs и основы Big O, чтобы эффективно организовывать и обрабатывать данные.

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

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

Quicksort — эффективный алгоритм сортировки, основанный на стратегии «разделяй и властвуй». Он работает, выбирая опорный элемент и разделяя массив на части: элементы меньше опорного и больше него, затем рекурсивно сортирует каждую часть. Случайный выбор опорного элемента помогает избежать худшего случая производительности, обеспечивая среднее время выполнения O(n log n).

Проект IDEA представляет алгоритмы в виде невербальных инструкций, похожих на руководства IKEA, что делает их понятными для международной аудитории. Эти материалы распространяются под лицензией Creative Commons и используются в образовательных целях, позволяя учителям и студентам визуально осваивать сложные концепции. Инициатива получила широкое освещение в медиа и академических кругах.

• Участники обсуждают эффективность объяснения алгоритма быстрой сортировки (quicksort) с помощью метафоры инструкций IKEA, отмечая, что такой подход может быть полезен как повторение, но не для первоначального изучения.
• Некоторые пользователи указывают на неточности в визуализации, например, пропуск ключевых шагов или ошибки в порядке элементов, что может привести к непониманию или неправильной реализации алгоритма.
• Поднимается вопрос о целесообразности использования quicksort по сравнению с другими алгоритмами, такими как сортировка слиянием (merge sort), из-за худшего времени выполнения в худшем случае.
• Обсуждается культурный аспект названия "KVICK SÅRT" и использование диакритических знаков для создания "IKEA-стиля", что некоторые находят неудачным или раздражающим.
• Упоминаются альтернативные способы визуализации алгоритмов, такие как диаграммы железной дороги (railroad diagrams) или венгерские народные танцы, как более эффективные или эстетичные варианты.

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

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

• Поддержка традиции публичного колокольного звона в Англии как важной части культуры, несмотря на возможные неудобства.
• Обсуждение математических основ и групповой теории в композиции перезвонов, включая исторические параллели с алгоритмами генерации перестановок.
• Упоминание детективного романа "Девять портных" как известного произведения, знакомящего с искусством перезвона.
• Отмечается, что перезвон (change ringing) преимущественно распространен в Англии, в то время как в других странах (включая США) церковные колокола чаще просто играют мелодии.
• Физические ограничения (инерция колокола) и правила как причины, по которым некоторые теоретические методы не находят практического применения.

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

• YouTube связывает падение просмотров с использованием блокировщиков рекламы и трекеров, которые могут блокировать ключевые API-эндпоинты, необходимые для учёта просмотров.
• Некоторые пользователи отмечают, что падение просмотров не влияет на доходы создателей, и выражают недовольство агрессивной рекламной политикой YouTube, которая заставляет использовать блокировщики.
• Высказывается предположение, что YouTube намеренно занижает просмотры, чтобы сделать встроенную рекламу более привлекательной для спонсоров по сравнению с интеграциями внутри видео.
• Обсуждаются технические аспекты: почему YouTube не встраивает рекламу непосредственно в видеопоток на сервере, чтобы её нельзя было заблокировать.
• Многие пользователи отстаивают своё право на использование блокировщиков и расширений для защиты конфиденциальности, несмотря на позицию YouTube.
• Поднимается вопрос о возможных юридических последствиях для пользователей, блокирующих рекламу, по аналогии с преследованиями со стороны RIAA и MPAA.
• Отмечается, что проблема может быть не только в блокировщиках, но и в других факторах: борьбе с ботами, изменениях в алгоритмах или общем падении интереса к платформе.

• Участники обсуждения сходятся в том, что алгоритмические ленты, максимизирующие вовлечение, превращают соцсети в машины поляризации и зависимости.
• Повторяющийся аргумент: «если бы не Facebook/Twitter, люди всё равно нашли бы способ сраться» — отвергается опытом тех, кто ушёл и почувствовал немедленное улучшение психики.
• Главный страх — не просто потеря времени, а то, что наши мысли формируются узким кругом платформ, которым выгодно злить или пугать.
• Предлагаемые «лекарства» звучат жёстко: запретить монетизацию политики, рекламу по данным, разрешать только хронологическую ленту, или вовсе блокировать доступ до 15-16 лет.
• Многие признают: уйти трудно, потому что соцсети одновременно заменили СМИ, клубы, знакомства и даже политические партии; отказаться — значит выйти из публичной жизни.

Соцсети умирают: вместо людей — поток ИИ-шлама.
Лента превратилась в конвейер одинаковых постов, клонов и крипто-рекламы; настоящее вытеснено генеративным спамом, оптимизированным под клики. Facebook, Instagram, TikTok заливает «Shrimp Jesus» и прочий автоматический контент, который платформы не спешат фильтровать. Пользователи всё реже видят друзей и всё чаще — ботов. Это конец романтики «аутентичности» и начало эры цифрового потребления ради потребления.

• Участники сходятся: «соцсети» перестали быть социальными – это медиа-конвейер «производитель → потребитель».
• Алгоритмическая лента превратила пользователей в пассивных зрителей, выжимая внимание и нагнетая полярность.
• Люди устают от «семантического шлама» и ботов, но массового исхода не происходит – платформы всё ещё удерживают триллионы минут.
• Единственное, что работает – полное отсутствие алгоритма (Mastodon, форумы) и маленькие «архитектуры намерения» вроде расширений-задержек.
• Рецепт: убрать лайки/пуши, вернуть хронологию, гарантировать подлинность аккаунтов и заставлять искать друг друга вручную – иначе это уже не «социальное», а телевизор 2.0.

Сложные LeetCode-задачи — простые задачи на ограничения

Интервьюер спросил: «Минимальное количество монет для сдачи 37¢ при номиналах [10, 9, 1]».
Жадный алгоритм даёт 10 монет, оптимум — 4. Ручное ДП сложно, а в MiniZinc — три строки:

int: total; array[int] of int: values = [10,9,1];
array[index_set(values)] of var 0..: coins;
constraint sum(c in index_set(coins)) (coins[c]*values[c]) == total;
solve minimize sum(coins);

Запускаем онлайн, получаем ответы за секунды.

---

Другие «сложные» задачи

1. Максимальная прибыль на акциях
   Дано: цены за день.
   Решение: купить до продать, максимизировать prices[sell]-prices[buy].

   array[int] of int: prices;
   var int: buy; var int: sell;
   constraint sell > buy;
   solve maximize prices[sell]-prices[buy];
   

2. Три числа дают 0 в сумме
   Нужно ли среди списка выбрать 3 числа со знаками ±1, чтобы сумма была 0?

   array[int] of int: nums;
   array[index_set(nums)] of var {-1,0,1}: coef;
   constraint sum(i in index_set(nums)) (nums[i]*coef[i]) = 0;
   constraint sum(i in index_set(nums)) (abs(coef[i])) = 3;
   solve satisfy;
   

3. Самый большой прямоугольник в гистограмме
   Ширина столбцов = 1, высоты заданы.

   array[int] of int: h;
   var 1..length(h): x; var 1..length(h): dx; var 1..max(h): y;
   constraint x+dx <= length(h);
   constraint forall(i in x..x+dx) (y <= h[i]);
   solve maximize (dx+1)*y;
   

---

Плюсы и минусы солверов

• + Код в 3–5 строк, добавление новых ограничений бесплатно.
• – Сложность работы непредсказуема, медленнее «идеального» алгоритма.
• – На собеседовании спросят «а сложность?» — ответа нет.

Вывод: если нужен рабочий код быстро — бери солвер; если нужна гарантированная скорость — пиши алгоритм вручную.

• Кто-то предлагает решать «задачи на подбор монет» и прочие LeetCode-загадки не вручную, а вызывать готовый constraint-/SAT-/SMT-солвер — быстро и универсально.
• Интервьюеры возражают: «мы хотим увидеть, как ты сам пишешь алгоритм, а не вызываешь библиотеку; иначе как проверить сложность и масштабируемость?»
• Сторонники солверов отвечают: в продакшене важен рабочий результат, а не «олимпиадная остроумность»; к тому же солвер легко добавляет новые ограничения.
• Часть комментаторов считает, что LC-интервью вообще плохо предсказывают рабочие навыки и дискриминируют тех, кто не зубрит шаблоны.
• Итог: constraint-solvers — мощный инструмент, но на типовом собеседовании их использование чаще всего «вне правил», поэтому приходится писать ручное решение, даже если в реальной жизни ты бы просто вызвал OR-Tools.

Мелодии, которые размножаются

Я построил «разводильню мелодий»: выбираете до трёх понравившихся фраз, они «спариваются», мутируют и рождают новое поколение. За считанные секунды прокручивается то, что в природе заняло бы столетия. Работает как цифровой организм: нейросети играют роль ДНК, клики пользователей — отбор, кроссинговер и мутации — алгоритмы.

Живая музыка Конвея

Правила «Жизни» Конвея превратились в симфонию: рождение клетки — аккорд, смерть — диссонанс. Планеры становятся мелодиями, пушки — ритм-машинами. Сложность из простых правил, только теперь со звуком.

Культурные вирусы

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

Код как микроскоп

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

• Участники обсуждают «музыкальное» Conway’s Game of Life: каждая клетка рождает/умирает → звучит нота, зависящая от столбца (тон) и строки (октава).
• Похваляют демо, но спорят о «функции пригодности»: без модели «человеческого вкуса» эволюция генерирует случайный шум.
• Вспоминают похожие инструменты: Wolfram Tones, Eurorack-sequencer NLC, Reaktor-дамап, iOS-sequencer ZOA, Otomata, собственные DIY-Launchpad и «Tone of Life».
• Предлагают улучшения: ритм по числу живых клеток, hex-решётка вместо квадратной, MIDI-экспорт, интерактивная веб-версия.
• Проблемы: сафари на iPhone может не играть (выключить беззвучный режим), сайт Wolfram Tones часто лежит, старые Flash-sequencerы умерли.

TikTok победил: теперь всё — 60 секунд

170 млн американцев тратят по часу в день на приложение, которое превратило внимание в товар. Пока Конгресс спорит о данных, TikTok уже промышленно перерабатывает человеческое внимание: вместо сюжетов — бесконечная лента импульсов и нейросетей.

Короткие видео и алгоритмы были и раньше, но TikTok впервые объединил их в систему добычи внимания. Его лента учится не на лайках, а на микродвижениях: сколько миллисекунд вы задержались перед свайпом — и сразу перестраивает ленту.

Последствия уже везде:

• Новости — 30-секундные ролики Washington Post
• Образование — студенты не читают длинных текстов
• Музыка — интро сократилось с 20 до 5 секунд
• Кино — трейлеры стали монтажом «моментов для клипа»

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

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

• TikTok и короткие 60-секундные видео формируют новую медианорму: всё, что короче 10 минут, стремится уложиться в минуту, а лонгформ тянут до 30-90 минут.
• Пользователи жалуются на «засорение» внимания: сложно вернуться к медленным форматам, пропадает терпение на статьи и полуторачасовые видео.
• Платности и алгоритмы подталкивают авторов: YouTube разрешает вставлять рекламу каждую минуту после 8 минут, поэтому ролики раздувают интро и повторы.
• Многие считают shorts «телевидением²» и «ультрапереработанным контентом»; кто-то удаляет приложения, кто-то использует как инструмент, подписавшись на полезные темы.
• Виноваты не только TikTok: Instagram, Twitter, YouTube Shorts, Facebook тоже сводят взаимодействие к бесконечному скроллу и «лайкам», превращая информацию в спектакль.

• Сортировка с хешем быстрее хеш-таблиц: на больших данных 1,5–4×, несмотря на «O(n log n)».
• Память: хеш-таблица тянет 128 Б на 8-Б ключ (64 чтение + 64 запись), радикс-сорт 3 прохода — 48 Б (вся линия кэша используется).
• Плохие распределения (мало заполненных корзин) замедляют радикс-сорт; решаем хешем hash(key) перед сортировкой. Берём обратимую функцию (Murmur3, MulSwapMul), хешируем «на лету» в первом проходе.
• Результат: 2 ГиБ уникальных uint64 за 1,9 с против 2,6 с у оптимизированной хеш-таблицы.
• Подходит, когда порядок не важен, а нужны только уникальные значения; иначе остаёмся на хеш-таблицах.

• Улучшенная нестабильная сортировка Rust почти догнала по скорости специально настроенный radix-sort, несмотря на разницу в O(n log n) vs O(n).
• Хэш-таблица «побеждает» лишь при ограниченном размере ключа и хорошем кэше; при росте данных снова проигрывает из-за промахов и O(n log n) внутри.
• Radix можно ускорить, выделяя buckets через MMU, а не вручную управляя памятью.
• На очень больших объёмах (≥120 ГБ) константы radix снова могут перевесить, но пока доминирует кэш-эффективность сортировки.
• Всё обсуждение подчёркивает: конкретные константы и архитектура CPU важнее «чистой» Big-O.

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

«О боже, это потрясающе» — Джесси Айзенберг

Осталось 3 бесплатных поиска.
Регистрация → для безлимита.

• Введи имена или нажми «Случайный»
• Добавь себя → и увидь связи с историей

Подпишись на Substack → для новых открытий.

• Проект «Network of Time» строит кратчайший путь между двумя известными людьми по цепочке проверенных фотографий, где каждое ребро = совместное фото.
• Алгоритм — обычный поиск кратчайшего пути по ручному графу; данные добавляются и уточняются автором с 2019 г.
• Пользователи заметили, что маршруты иногда выглядят «круговыми» (Carson → Letterman → Obama → Cooper), но после добавления недостающих фото путь сократился до Carson → Leno → Cooper.
• Все современные персонажи уже связаны в одну компоненту; интерес вызывают «исторические аутлайеры» вроде Гарриет Табман и Эдгара По, которых пока не удаётся присоединить.
• С 2023 г. сложнее проверять подлинность фото: приходится тщательнее следить за метаданными и источниками.

Что такое сложность?
Если бы мы знали ответ, все были бы мастерами.

В мае 2020-го на форуме предложили ввести метрику «сложности» позиций. Я критиковал статью FM Дэвида Пэна и сопутствующий код. С тех пор интерес к теме вырос, а Lichess обзавёлся блогами — пора довести критику до конца.

Золотая курица
Автор обещает революцию: позиционные тренажёры, «человечные» движки, диагностику слабых мест. Если бы это было реально, продукты уже продавались бы массово, а читеры получили бы инструмент оценки риска.

Тезисы

• Сложность — одномерная величина, передаваемая нейросети через потери в сантиходах (ACPL).
• Она же должна мгновенно показывать, насколько позиция трудна.
  Интуиция не заменяет доказательств.

Логика
Даже принимая тезисы, выводы сомнительны:

1. «Сложные» позиции не обязаны быть интересными или полезными для тренировки.
2. Текущая система рейтинга головоломок (Эло) медленна, но работает.
3. Автоматическое «понимание» дебютов вместо зубрёки — фантазия.
4. Сложность ≠ интерес ≠ польза.
   5–6. Разница в ошибках между сильными и слабыми игроками не даёт готовых учебников или экзаменов.
5. Большие базы данных снабжены метаданными (контроль времени, рейтинг), но это не делает «интуитивные» позиции измеримыми.

Итог
Метрика, основанная на ACPL, — это маркетинг, а не наука. Настоящая сложность требует глубже: учёта человеческого восприятия, стиля, психологии.

• Ищут позиции, которые сложны для слабых и легки для сильных игроков; простой способ — сравнивать лучший ход на мелкой и глубокой глубине.
• Обсуждают различие «сложности» (количество вариантов) и «остроты» (цена ошибки), а также проблему формализации этих понятий.
• Показывают проекты: MCP-сервер со Stockfish и Maia для имитации игроков разного уровня, тренажёры, визуализацию линий.
• Отмечают, что LLM плохо объясняют позиции, а решение шахмат полным перебором практически невозможно из-за размера пространства.

Как 20-летний алгоритм помогает понять эмбеддинги трансформеров

Чтобы понять, о чём думает LLM, когда она слышит «Java», нужно разложить внутренние векторы на понятные человеку концепции. Это формулируется как задача dictionary learning: эмбеддинг представляется как разреженная сумма базовых векторов-концептов. В 2023 г. Bricken и др. предложили учить словарь через sparse autoencoder (SAE), отказавшись от классических методов из-за масштабируемости и опасения «слишком сильного» восстановления признаков.

Мы показали, что 20-летний алгоритм KSVD, с минимальными доработками, справляется с миллионами примеров и тысячами измерений. Наивная реализация требовала бы 30 дней; наша версия DB-KSVD ускорена в 10 000 раз и работает 8 минут. DB-KSVD обобщает k-means, но позволяет приписывать объект сразу нескольким «кластерам» (концептам).

Библиотека KSVD.jl доступна из Python:

import torch, juliacall; jl = juliacall.Main
jl.seval("using KSVD")
Y = torch.rand(128, 5000, dtype=torch.float32)
res = jl.ksvd(Y.numpy(), 256, 3)  # словарь 256, sparsity 3

На бенчмарке SAEBench DB-KSVD и расширение MatryoshkaDB-KSVD показывают результаты, сравнимые с SAE, по шести метрикам: восстановление эмбеддингов, разделение концептов, их интерпретируемость и др.

• В чате поделились скрытым гемом — второй половиной двухчасового видео Леланда Мак-Иннеса (автора UMAP) о построении эмбеддингов через пред-преобразования и SVD.
• Участники отметили отличное время публикации: идея пригодилась для текущих задач.
• Основная претензия — авторы не расшифровали сразу аббревиатуры, особенно KSVD, что замедлило чтение.
• Уточнили: KSVD ≠ обычный SVD, это алгоритм разреженного кодирования с избыточным базисом и разреженными активациями.

Big O — способ описать, как время работы функции растёт с ростом входных данных, без привязки к конкретным секундам.

Рассмотрим 4 основные категории:

---

O(n) — линейное время

function sum(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) total += i;
  return total;
}

• sum(1e9) ≈ 1 с
• sum(2e9) ≈ 2 с
  Время пропорционально n.

---

O(1) — константное время

function sum(n) {
  return (n * (n + 1)) / 2;
}

• sum(1e9) и sum(100e9) выполняются почти мгновенно.
  Время не зависит от n.

---

Ключевые идеи

• O = «order of growth»; описывает рост, а не абсолютное время.
• O(1) ≠ «быстро», а «не растёт с размером входа».
• При достаточно большом n O(1) всегда обгонит O(n).

• Обсуждение статьи о нотации Big O разделилось на «лайтовое» восхищение визуализациями и «экспертные» споры о точности определений.
• Новички признаются, что статья впервые открыла им глаза на сложность алгоритмов, а ветераны IT спорят, что за 40 лет ни разу не пригодилась.
• Критика сводится к тому, что автор описывает «поп-культурный» вариант Big O, путая его с Θ-нотацией и worst-case.
• Практики напоминают: на реальном железе константы, кэш и NUMA могут перечеркнуть асимптотику, а O(n²) при малых n часто быстрее «константного» хэша.
• Люди делятся шпаргалками (bigocheatsheet.com, visualgo.net) и просят ещё интерактивных уроков.

Алгоритм CRDT для совместного текста

Каждый символ получает уникальный id: site (идентификатор узла) и clock (локальный счётчик, увеличиваемый после каждой операции), а также parent — указатель на предыдущий символ.

• Вставка
  parent ставится на символ перед точкой вставки (null — в начало). Порядок символов задаётся прямым обходом дерева: родители идут раньше потомков.

• Сортировка при одинаковом parent
  Сначала по убыванию counter, затем по site. При вставке перед символом с тем же parent берём его counter + 1.

• Удаление
  id символа попадает в множество удалённых (tombstone). Значение можно забыть, но позиция нужна для корректного порядка.

Оптимизации

1. Последовательные вставки одного узла объединяются в блок: массовая вставка стоит как одна операция.
2. Блоки хранятся в отсортированном массиве; вставка — O(log n) без явного дерева.
3. Удаления группируются диапазонами по site и clock.

Плюсы и минусы

• Плюсы: разумный расход памяти, быстрые запросы/обновления.
• Минусы: сложная логика слияния, только рост метаданных, сборка мусора требует координации.

Интерактивный пример
Четыре пира, задержка сети, редактирование кликом. Исходник — crdt-text-buffer.js.

Полезные ссылки

• josephg.com/blog/crdts-go-brrr/ — эффективная реализация.
• archagon.net/blog/2018/03/24/data-laced-with-history/ — деревья и сборка мусора.

• Обсуждали RGA — CRDT-алгоритм для списков и текста, который Automerge раньше использовал до перехода на FugueMax.
• У RGA есть редкая проблема: при вставке элементов в обратном порядке у разных пользователей возникает чередование.
• Упомянули Eg-Walker — новый подход от Loro.dev, который вызвал интерес у участников.

C-Tubes: из плоского — в пространственное
Исследователи EPFL создали способ строить сложные изогнутые 3D-формы из плоских листов бумаги, металла или пластика без растяжения и складок.

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

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

Плюсы устойчивости

• Минимум отходов: листы режутся без высечек.
• Лёгкие конструкции требуют меньше материала и энергии.
• Плоские заготовки легко транспортировать и перерабатывать.

Работа получила honorable mention на SIGGRAPH 2025 и может изменить подходы в архитектуре, дизайне мебели и света.

• Критика: при раскрое из прямоугольных листов много отходов, хотя они перерабатываются.
• Примеры из открытой статьи и сайта показывают больше вариантов и анимаций.
• Потенциальное применение — воздуховоды из склеенных C-труб, но нужны нестандартные угловые соединители.
• В EPFL уже построили живую бамбуковую арку с вьющимися растениями, но она не использует C-Tube.
• Суть метода — развёртываемые поверхности без растяжения; алгоритм превосходит предыдущие и имеет практическую ценность.

День 2: строим дерево Хаффмана

Переписал bz2.adb на чистые структуры:
Bit_Writer, MTF, RLE, Burrows_Wheeler, Huffman.
Каждая структура = пакет + скрытый тип + конструктор Create, методы Encode, Flush, Reset.

Huffman

• Считаем частоты 256 байт + 2 служебных символа (RUNA, RUNB).
• Строим дерево: Node (частота, символ, левый, правый).
• Сортируем список узлов по частоте, склеиваем два минимальных, повторяем, пока не останется один корень.
• Коды длиной ≤ 20 бит (требование BZip2).
• Генерируем таблицу Code_Length[0..257] и Code_Value[0..257].

Оптимизация

• Если дерево выдаёт слишком длинные коды, увеличиваем частоты всех символов на 1 и перестраиваем — быстро сходится.
• Память: дерево живёт только во время построения, затем храним только таблицы.

Интеграция
Huffman.Encode получает поток MTF/RLE-символов, пишет в Bit_Writer:

1. 16-битная маска 0x425A ("BZ").
2. 8-битная версия 0x68.
3. Таблица длин кодов (передаём как 4-битные значения).
4. Сами данные: коды Хаффмана + биты RLE-последовательностей.

Итог за день

• 400 строк Ada, 0 зависимостей.
• Код компилируется gnatmake -O2 bz2.adb за 0.3 с.
• Тест: echo "abracadabra" | ./bz2 > out.bz2, bunzip2 принимает без ошибок.

Завтра: многопоточность и буферизация.

• Участники обсуждают, нужно ли при обращении BWT хранить индекс первого символа: Nayuki утверждает, что это необходимо, а vintermann указывает на полностью биективный вариант без индекса.
• Amy_petrik подчеркивает, что BWT переводит строку в «пространство суффиксных деревьев», что позволяет быстро искать внутри сжатых BZ2-файлов и лежит в основе современных ДНК/РНК-алгоритмов выравнивания.
• Horizon2025 отмечает «магическую» обратимость преобразования при минимуме дополнительных данных.

Предложен детерминированный алгоритм времени O(m log^{2/3} n) для задачи кратчайших путей из одного источника (SSSP) во взвешенных ориентированных графах с неотрицательными весами в модели сравнение-сложение. Впервые превзойдена граница O(m + n log n) алгоритма Дейкстры на разреженных графах, что доказывает его неоптимальность для SSSP.

• Обсуждали статью о новом алгоритме для разреженных графов.
• Алгоритм даёт ускорение только при средней степени < 3, если граф не триллионных размеров.
• MarkusQ уточнил: при m < 3n это ≈ степень < 6, так что двумерные решётки всё ещё выигрывают.
• Вывод: улучшение полезно, но не универсально.

Хвостовая рекурсия превращает рекурсию в цикл: компилятор заменяет вызов на безусловный jmp, поэтому стек не растёт.

Обычная рекурсия кладёт промежуточные значения в стек, тратит O(n) памяти и вытесняет кэш.
Цикл же держит результат в аккумуляторе, использует O(1) памяти и линейное время.

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

Пример суммы списка

Обычная версия:

(define (sum l)
  (if (empty? l) 0
      (+ (first l) (sum (rest l)))))

Хвостовая версия:

(define (sum l acc)
  (if (empty? l) acc
      (sum (rest l) (+ acc (first l)))))

Аргументы l и acc перезаписываются «на месте», как переменные цикла.

Упражнение 1 — счётчик чётных/нечётных:

(define (even-odd l [e 0] [o 0])
  (if (empty? l) (cons e o)
      (let ([x (first l)])
        (if (even? x)
            (even-odd (rest l) (add1 e) o)
            (even-odd (rest l) e (add1 o))))))

Упражнение 2 — сглаживание дерева:
используйте аккумулятор-список и обход в обратном порядке, чтобы сохранить хвостовой вызов.

• Теоретически хвостовая рекурсия и циклы эквивалентны: любую хвостовую рекурсию можно превратить в цикл (и наоборот), но взаимно-рекурсивные функции требуют дополнительной работы.
• На практике циклы чаще проще для чтения и не ломают стек, тогда как хвостовая рекурсия нуждается в оптимизации (TCO), которую не все языки поддерживают (Python, V8 её нет).
• Некоторые языки (Scala, Clojure, F#) дают компромиссные конструкции (@tailrec, recur), сохраняющие функциональный стиль и гарантирующие отсутствие переполнения стека.
• Вместо явной хвостовой рекурсии часто достаточно высокоуровневых комбинаторов вроде fold/map, но они не всегда позволяют досрочный выход и могут расходовать O(N) памяти.
• Участники сходятся во мнении: владеть обоими подходами полезно, выбор зависит от языка, задачи и привычек команды.

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

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

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

Графы описывают вершины и ребра с весами (длина, время и т.п.). Задача: по данному источнику найти кратчайшие пути до всех вершин. Алгоритм Дейкстры (1956) идет «волной» наружу: зная оптимальные пути к ближайшим, находит пути к дальним. Но конечный результат — упорядоченный набор кратчайших расстояний, и потому скорость ограничена сортировкой. В 1984 году Тарьян с соавтором улучшили Дейкстру до этого предела: чтобы ускориться дальше, нужно избегать сортировки.

В конце 1990-х — начале 2000-х Торуп и другие обошли барьер для частных случаев, вводя ограничения на веса. Обобщить техники на произвольные веса не удавалось, и прогресс застопорился. Ран Дуань не согласился с пессимизмом и стремился сломать барьер для всех графов — и прошлой осенью добился цели.

Идея Дуани (созревшая к 2021 году): вместо того чтобы на каждом шаге сканировать всю «границу» уже исследованной области, как делает Дейкстра (что со временем замедляет ход), группировать соседние граничные вершины в кластеры и рассматривать по одному представителю из каждого. Это уменьшает число кандидатов и может вести не к ближайшей вершине — значит, зависимость от сортировки исчезает. Главная трудность — доказать, что кластеризация действительно ускоряет процесс на каждом шаге и в сумме.

За следующий год Дуань проработал идею и к осени 2022-го был уверен, что технические барьеры преодолимы.

• Обсуждение вокруг нового алгоритма SSSP с детерминированной сложностью O(m log^(2/3) n), который улучшает Дейкстру на разреженных графах; ссылку дали на arXiv: 2504.17033.
• Участники отмечают, что выигрыш зависит от структуры графа: для дорожных сетей обычно m ≈ c·n (c ~ 4–6 для ориентированных), что даёт O(n log^(2/3) n); для очень плотных графов (m ~ n^2) преимущество может исчезать.
• Возникают вопросы о сравнении логарифмических степеней, применимости к задачам вроде TSP с почти полными графами, и сохранении гарантии глобального минимума как у Дейкстры.
• Некоторые считают алгоритм сложнее Дейкстры, но отмечают теоретическую значимость прорыва и отсутствие «фancy math», что делает результат удивительным.
• Обсуждают возможные гибриды с рандомизацией и практическое влияние на реальные графы (улицы, геймдев).
• Есть скепсис о «позднем открытии» и комментарии про то, что практики могли бы дойти до подобных идей, но не оформляют их академически.
• Вспоминают вклад классиков (Тарjan и др.) и проводят аналогию с TimSort: практичная оптимизация поверх классики.