Обновить
1120.23

Программирование *

Искусство создания компьютерных программ

Сначала показывать
Порог рейтинга
Уровень сложности

Компактные структуры данных

Уровень сложностиСредний
Время на прочтение10 мин
Количество просмотров14K

Введение


Несколько месяцев назад в поисках идей по ускорению кода я изучал множество научных статей по computer science. Не буду притворяться, что хорошо их понимал, но меня не пугает непонятное, и я готов признать своё невежество1. Я обнаружил статью, написанную пятнадцать лет назад2, в которой было множество новых для меня концепций. Мне никак не удавалось в них разобраться.

Что же делать дальше? Можно искать другие статьи, чтобы они заполнили мои пробелы. Это рискованное предприятие, потому что они могут запутать ещё больше, но избежать этого нельзя. Я нашёл статью с нужной структурой данных, в которой упоминался исходный код с веб-сайта. Код был написан на C++, а я работаю на Rust, но решил, что всё равно стоит на него взглянуть. Однако зайдя на сайт, я не обнаружил там ресурс, поэтому я написал владельцу веб-сайта, который оказался преподавателем computer science.

Этот преподаватель (Гонсало Наварро) очень тепло меня принял и сразу же ответил мне3 4. И только в процессе общения с ним я осознал, что видел его фамилию на множестве статей в этой области. Оказалось, я познакомился с одним из специалистов мирового уровня в области компактных структур данных (succinct data structure). Невежество может завести очень далеко.

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

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

Я решил, что стоит немного о них рассказать.
Читать дальше →

Нововведения Java 24

Уровень сложностиСредний
Время на прочтение9 мин
Количество просмотров12K

Уже скоро, 18 марта, выйдет новая версия Java. Поэтому предлагаю посмотреть, какие в ней будут новшества, включая финализацию давно ожидаемых Stream Gatherers!

Читать далее

ИИ — напиши мне программу

Время на прочтение5 мин
Количество просмотров7.6K

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

Время шло. Статьи наподобие вышеуказанной попадались всё чаще. Сегодня вышла очередная CEO Anthropic: через полгода 90% кода будет писать ИИ. Через год — 100%

А так как в текущий момент я не пишу код рефлексирую о бессмысленности своего существования, я вспомнил про свою кладовку…

Честно сказать — сам пользуюсь постоянно всякими ИИ. Но использую их в качестве продвинутого поиска. Например, я точно знаю, что так можно сделать — но искать как синтаксически верно это реализовать лень. В этом ИИ мне помогает.

Или я хочу какую‑нибудь зубодробительную конструкцию — но не знаю можно ли сделать так в текущем языке или нет. ИИ и тут мне помогает.

Но вот писать код за меня…. Тут как говорится «наши полномочии всё…»

Почему так думаю и попытался изложить в текстовом виде.

Читать далее

Доставка день в день: погружение в базовые алгоритмы поиска и назначения курьеров в Яндекс Доставке

Уровень сложностиСложный
Время на прочтение27 мин
Количество просмотров7K

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

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

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

Читать далее

Как я решал задачу 2025 года. Часть 1

Уровень сложностиСредний
Время на прочтение9 мин
Количество просмотров4.7K

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

Равенства следующие:

2025 = 45^2 = (1+2+...+9)^2 = 1^3 + 2^3 + ... + 9^3

Некоторые, возможно, ещё помнят, что в углублённой школьной (или вузовской) программе встречалось равенство 1^3 + 2^3 + ... + n^3 = (1+2+...+n)^2 = n^2(n+1)^2/4. Собственно, оно тут и применяется. Кстати, согласно Википедии, это равенство называется тождеством Никомаха, древнегреческого математика (около 60-120 гг. н.э.).

На основе этих равенств можно сформулировать задачу:

Сколько существует способов расположить 1 квадратик со стороной 1, 2 квадратика со стороной 2, 3 квадратика со стороной 3, … , 8 квадратиков со стороной 8, 9 квадратиков со стороной 9 в квадрате со стороной 45, чтобы они не пересекались?

Читать далее

Как malloc() и free() управляют памятью в C

Уровень сложностиПростой
Время на прочтение8 мин
Количество просмотров22K

Привет, Хабр!

Сегодня рассмотрим, почему free() не всегда освобождает память, как работает malloc(), когда glibc действительно возвращает память в ОС, и как избежать фрагментации хипа. А так же напишем кастомный аллокатор.

Читать далее

Что бы стать программистом — программируйте

Уровень сложностиПростой
Время на прочтение3 мин
Количество просмотров83K

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

В чем может быть проблема? Ответ на этот вопрос у меня есть

Читать далее

За что безопасники будут гореть в аду?

Уровень сложностиПростой
Время на прочтение4 мин
Количество просмотров55K

Для привлечения внимания расскажу историю. Уже много лет живу далеко за пределами нашей всеми любимой родины. И на днях, понадобилось мне войти в старую почту gmail... Логин и пароль надежно сохранены. Однако Google не торопится впускать нас в собственную почту.
— Нам кажется что это не вы, подтвердите что это вы. Введите номер телефона когда-то использовавшийся при регистрации.
Что ж, и это можно. Ввожу номер.
— Увы, мы не можем отправить СМС на этот номер. Хотите завести другой аккаунт?

И еще пара историй...

Не покупайте грузовик для похода за хлебом и другие принципы программирования

Уровень сложностиПростой
Время на прочтение8 мин
Количество просмотров16K

Мне недавно встретился код вывода количества FPS на экран, написанный начинающим программистом, и в этом коде был базовый класс, класс-потомок, виртуальные функции, конструктор с множеством параметров, variant. Код позволял выводить любое количество счетчиков FPS на экран разными шрифтами, но все, что было на самом деле нужно, это простая функция на 3 строки, считающая количество FPS и выводящая его на экран.

Читать далее

Пишем свой загрузчик операционной системы Linux

Уровень сложностиСредний
Время на прочтение23 мин
Количество просмотров27K


Меня давно интересовал вопрос, насколько сложно написать собственный загрузчик операционной системы. Я не говорю о простой программе, выводящей «Hello, World!», а о полноценном загрузчике, который передаёт управление от встроенного программного обеспечения компьютера ядру операционной системы. Современные загрузчики представляют собой сложные программы, способные загружать множество операционных систем различными способами, учитывая массу нюансов, связанных с программным и аппаратным обеспечением. Читая их исходный код, легко утонуть в деталях и потерять понимание сути и реализации.


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

Читать дальше →

Вам не нужна Чистая архитектура. Скорее всего

Уровень сложностиСредний
Время на прочтение22 мин
Количество просмотров23K

Сейчас среди Java/Kotlin команд распространено применение Чистой (ака Гексагональной, ака Луковой — Clean, Hexagonal, Onion) архитектуры для разработки бакэндов прикладных приложений (да и Android‑приложений тоже). Однако это семейство архитектур в контексте прикладной разработки зачастую не даёт никаких преимуществ, а только привносит лишние церемонии и тем самым замедляет её.

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

Но перед тем как перейти к Чистой архитектуре, сначала надо разобрать принцип инверсии зависимостей (Dependency Inversion Principle, DIP).

Читать далее

Ультимативные крестики-нолики и iPXE

Время на прочтение10 мин
Количество просмотров6.8K

Привет, Хабр! Меня зовут Вова, я разработчик в Selectel. На днях меня осенило: загрузка сервера по сети — это прекрасный инструмент, из которого можно сделать что-нибудь необычное. Например, игру. У нас есть минимальный набор: командный интерпретатор, возможность скачивать и выполнять произвольный код.

Ранее я уже использовал инструменты не по назначению, когда создавал Морской бой на SQL, тетрис в QR-коде, крестики-нолики в DNS и Gravity Defied на sed. С прошлой «серии» ненормального программирования прошло почти два года — время вновь попробовать силы и придумать что-нибудь новое.
Читать дальше →

OpenIDE: первый взгляд

Уровень сложностиПростой
Время на прочтение3 мин
Количество просмотров18K

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

Ниже небольшой обзор и скриншоты в работе под FreeBSD, что наверное создателей немного удивит. Но я предупреждал ;-)

Читать далее

Ближайшие события

Симуляция воды над рельефом

Уровень сложностиПростой
Время на прочтение18 мин
Количество просмотров4.8K

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

Я одержим генерацией рельефа, играми на основе сеток, симуляциями и тому подобным. И часто во всём этом присутствует вода, или, по крайней мере, её присутствие кажется естественным.

Допустим, вы генерируете карту для стратегической игры, но не хотите, чтобы границы карты были заполнены непроходимой пустотой (как в олдскульных RTS). Разве не будет здорово, если граница будет заполнена водой, как на этой карте из одного моего заброшенного проекта?

Читать далее

Повышаем привилегии в Windows через CVE-2024-30085

Уровень сложностиСложный
Время на прочтение21 мин
Количество просмотров7K

CVE-2024-30085 — это уязвимость в подсистеме Windows Cloud Files Mini Filter. Код подсистемы располагается в cldflt.sys — это драйвер минифильтра, и он относится к предустановленному клиенту облачного сервиса Microsoft OneDrive.

Уязвимость фигурировала на прошедшем в Ванкувере Pwn2Own 2024, где команда ресёрчеров Team Theori использовала эксплойт для этой уязвимости в цепочке эксплойтов, осуществляющих Guest-to-Host-Escape (побег из виртуальной машины) из-под управления VMware workstation, за что и получила свои заслуженные 13 очков Master of Pwn.

В этой статье мы рассмотрим корни уязвимости CVE-2024-30085 и техники эксплуатации, применимые во время эксплуатации кучи в ядре Windows 10 22H2 19045.3803.

Читать далее

Наш архитектурный подход к Python приложениям

Уровень сложностиПростой
Время на прочтение15 мин
Количество просмотров16K

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

Читать далее

3200% нагрузки на процессор

Уровень сложностиСредний
Время на прочтение15 мин
Количество просмотров19K

Совсем недавно моя машина была в таком запущенном состоянии, что я едва мог подключиться к ней через ssh. 3200% нагрузки на CPU — полностью использовались все 32 ядра хоста! Сравните это с моим последним багом, когда использовалось всего одно ядро, то есть 100%

К счастью, я использовал среду выполнения Java 17, у которой были дампы потоков с указанием времени CPU!

Читать далее

Сортируем сотни млн строк в разы быстрее библиотечных алгоритмов. А не замахнуться ли нам на ммм… на O(n)?

Уровень сложностиСредний
Время на прочтение14 мин
Количество просмотров17K

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

Кто-то в личное время покоряет Эверест, кто-то стрит-драйвит, кто-то на нижней Волге ловит спиннингом судаков и жерехов (я тоже, кстати, раз в году), кто-то разводит мадагаскарских шипящих тараканов, а кто-то развлекает себя эзотерикой. А я вот внерабочее время развлекаю себя тем, что напрягаю свой мозг математическими и алгоритмическими проблемами. Придумываю что-нибудь эдакое, необычное. Жаль, что за эту деятельность не платят. Говорят, такое напряжение мозга поможет в старости спастись от болезни Альцгеймера. Во всяком случае, весьма на это надеюсь.

И, рассуждая совсем о другой проблеме, но где имеет место быть сортировка большого количества объектов, в плане алгоритма сортировки объектов, меня осенило. Быстренько проверил кодом — ого, работает! Рассчитываю, что вам понравится.

Читать далее

OAuth 2.0

Уровень сложностиПростой
Время на прочтение39 мин
Количество просмотров21K

Вы когда‑нибудь логинились на сайте, используя аккаунт Google или Facebook? Или подключали приложение, требующее доступа к GitHub? Если да, то вы уже сталкивались с OAuth2, зная того или нет.

OAuth2 — наиболее популярный и расширяемый фреймворк авторизации. Он позволяет интегрировать различные системы, делегируя доступ к вашим данным одного сервиса другому. Но фишка в том, что большая часть людей понятия не имеет, как именно OAuth2 на самом деле работает.

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

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

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

Читать далее

Как использовать Cline и Roo Code в качестве AI-ассистента для кода?

Уровень сложностиПростой
Время на прочтение7 мин
Количество просмотров36K

Почти год назад мы рассмотрели подборку AI-ассистентов для кода, сегодня же мне хотелось бы сосредоточить внимание на одном конкретном, а именно — Cline, номер 1 на OpenRouter. Предлагаю вместе пробежаться по настройке и интеграции, а также использовании Cline в качестве ИИ-ассистента.

*А также мы поговорим про Roo Code — форке Cline, но совсем немного, поскольку они абсолютно идентичны в настройке и функционале.

Приятного прочтения!

Читать далее

Вклад авторов