Pull to refresh
286
0.1
Владимир @32bit_me

Программист

Send message

Три теоремы о сортировках

Level of difficultyMedium
Reading time12 min
Views14K

Я знаю многих программистов и руководителей в IT компаниях, которые недолюбливают математиков и в частности считают их далёкими от жизни идиотами из-за их утверждений в духе "нельзя отсортировать последовательность быстрее, чем за nlogn" -- ведь это очевидным образом неверно, есть же сортировка подсчетом и radix sort. Нюанс в том, что описанное выше -- это распространённая некорректная трактовка одной из ключевых теорем об алгоритмах сортировок, корректное утверждение выглядит так: "не существует алгоритма, который бы гарантированно находил перестановку n элементов, приводящую к возрастающему порядку, быстрее чем за nlogn используя только операции попарного сравнения". В этом утверждении больше слов, оно более сложно в плане когнитивного восприятия, ключевой момент обозначил жирным шрифтом, чувствуете разницу?

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

Если я ещё не убедил Вас прочитать статью, то вот моя последняя попытка: в статье объясню почему пузырёк -- это бесполезная фигня, но внезапно практически также работающая сортировка вставками -- это супер важная сортировка, являющаяся частью std::sort в MSVC, GCC и Clang. Расскажу, каким интересным свойством оптимальности обладает сортировка выбором, являющаяся в теории такой же неэффективной как пузырёк.

Читать далее

Модифицируем алгоритм Брезенхэма для рейкаста в стиле Wolf3D

Level of difficultyEasy
Reading time10 min
Views2.6K

Недавняя статья о рендеринге полигонов для «Денди» завершилась (уже в камментах) небольшой интрижкой: «хочу реализовать 2.5D, но не уверен, что получится плавная камера». Естественно, мимо такого я пройти не мог :) и сейчас прикладываю максимум усилий к тому, чтобы плавная камера на этом несуразном железе таки получилась. По мне, шутер (даже 2.5 D) без мышки, хотя бы пополамной или RS232, и плавной камеры с высокими FPS — не шутер, а вот остальное можно смело принести в жертву драйву (и принесём!)

Наивный алгоритм, он же DDA, знают все. Но ветвления на каждом шаге, с делениями, умножениями и сравнениями — это явно не про «Денди» сказано. К счастью, у нас есть намного более быстрый алгоритм — алгоритм рисования линий Брезенхэма. Нужно только его немножко доработать напильником, чтобы он годился для того, для чего мы его собираемся использовать!

Оригинального «Брезентыча» я особо подробно расписывать не буду. Если ещё его не знаете — просто прочитайте, а я сразу перейду к тому, чем он нам неугоден в его каноничном виде.

Да уж небось я знаю, как «Брез» работает!

О новых алгоритмах хеш-таблиц

Reading time1 min
Views17K

Хотелось бы прокомментировать публикацию Ильи Кабанова в Медузе по поводу новых разработок в алгоритмах хеширования: "Optimal Bounds for Open Addressing Without Reordering" (Farach-Colton, Krapivin, and Kuszmaul, 2025) и последующую "The Bathroom Model: A Realistic Approach to Hash Table Algorithm Optimization" (Wang, 2025). И особенно кликбейтное: "в перспективе метод Крапивина и его коллег может ускорить многие процессы в интернете."

Я около 7 лет очень плотно занимался темой хеш-таблиц и написал много их вариантов: Koloboke, SmoothieMap, memory-mapped вариации.

Я потерял к теме интерес с выходом гугловской SwissTable (2018), и ее фейсбучного варианта F14, которые основаны на SIMD. Они проверяют загруженность ячеек и совпадения "тега" элемента сразу блоками по 8 соседних слотов. Поэтому на любых разумных загрузках таблиц (до 90%) - "цепочка проверки" очень редко превышает 1 (то есть, одну проверку 8-элементного блока).

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

Именно эти разработки, а не Крут и не статья Yao, которую "опровергли" новые работы, стали "практическим концом теории" хеш-таблиц, на мой взгляд.

SwissTable стали стандартным алгоритмом хеш-таблиц в Расте, и, буквально в этом месяце, в Golang 1.24.

В заключение, отвечая Илье Кабанову: к "ускорению интернета" эти теоретические алгоритмы не приведут :)

Читать далее

Установка PostgreSQL в Linux

Level of difficultyEasy
Reading time8 min
Views19K

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

При обучении студентов работе с базами данных мной была выбрана СУБД PostgreSQL --- хотя она и считается несколько сложной для изучения, чем та же MySQL, это достаточно популярный и к тому же бесплатный продукт, с открытым исходным кодом, и самое главное --- у неё есть в том числе и российские корни. С литературой по PostgreSQL ситуация оказалась двоякой: с одной стороны, книг по ней не так уж и много, как хотелось бы (мейнстримом является MySQL, многие примеры оттуда работают и здесь), в результате чего найти хорошее объяснение или примеры по тому или иному вопросу может быть затруднительно. С другой стороны, с 2015 года компания Postgres Professional делает полный перевод документации PostgreSQL на русский язык, за что им огромное спасибо. Но... Всё равно этого не хватает. В общем, если вам нужно установить PostgreSQL и вы уже столкнулись при установке с какими-то трудностями, добро пожаловать под кат!

Читать далее

Операционная система в 1 000 строках кода (часть 1)

Level of difficultyMedium
Reading time11 min
Views37K

Всем привет! В этой небольшой книге (серии статей, — прим. пер.) мы с нуля, шаг за шагом, напишем скромную ОС.

▍ Навигация по частям



Вы можете насторожиться, услышав, что разработка ОС или ядра, в частности, их базовых функций на удивление проста. Даже система Linux, которая воспринимается как масштабный опенсорсный проект, на стадии версии 0.01 включала всего 8 413 строк кода. Сегодня ядро Linux действительно огромно, но начиналось оно, как и типичный хобби-проект, с крохотной базы кода.

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

Но сразу предупрежу — процесс окажется не так прост, как выглядит на первый взгляд. Самой сложной частью создания собственной ОС является отладка. И мы не сможем использовать для этого printf, пока её не реализуем. Здесь вам потребуется освоить различные техники и приёмы отладки, которые в разработке ПО вы никогда не использовали. В частности, начиная «с нуля», вы будете встречать сложные этапы вроде процесса загрузки и страничной организации памяти. Но не пугайтесь, «отлаживать ОС» мы тоже научимся!

Чем сложнее отладка, тем больше радости от получения рабочего продукта. Так что приглашаю вас погрузиться в захватывающий мир разработки операционных систем!
Читать дальше →

ЭВМ ЕС-1030. Оперативная память

Level of difficultyMedium
Reading time19 min
Views2.4K

Продолжение цикла, посвящённого процессору ЭВМ ЕС-1030. Хотя, строго говоря, оперативная память в состав процессора не входит, её характеристики и режимы работы весьма значительно влияют на устройство и работу процессора, а поэтому заслуживают внимания.

Читать далее

Алгоритмы. Рекурсивные функции. Часть I

Level of difficultyMedium
Reading time12 min
Views6.4K

Определение. Алгоритм – некоторая конечная последовательность предписаний (правил, инструкций и т.п.), однозначно определяющая процесс преобразования исходных P и промежуточных данных в результат Q решения задачи.


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

Абстракция потенциальной осуществимости. Как уже отмечалось, алгоритмический процесс при выработке результата Q из исходных данных P совершает несколько отдельных шагов. Число таких шагов может быть настолько велико, что достижение результата Q является практически неосуществимым. Однако в теории алгоритмов мы не учитываем практическую неосуществимость и считаем возможным выполнить любое конечное число шагов. Это положение называется абстракцией потенциальной осуществимости. Это же положение предполагает, что мы можем оперировать со сколь угодно большими объектами, например, сколь угодно длинными словами и т.п.


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

Читать далее

Тестирование лучших self-hosted аналогов Notion

Level of difficultyEasy
Reading time6 min
Views33K

image


Хабр, в связи с уходом Notion выросла потребность в аналогичном решении, которое бы было сопоставимо удобной Wiki, Task Manager — платформе. 


Я испробовал десять self-hosted решений и нашел несколько почти идеальных! Вы можете развернуть их у себя на сервере, при работе над совместными проектами с командой или для ведения личных записей.

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

Unix на работе. Часть вторая, программная

Level of difficultyEasy
Reading time12 min
Views16K

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

Из первых рук и на основе многолетней практики.

Читать далее

Век поиска кратчайшего решения задачи о кратчайшем пути

Level of difficultyMedium
Reading time22 min
Views12K

TL;DR Очень подробный разбор алгоритмов решения задачи о кратчайшем пути от классики до двунаправленного А* и ALT с кодом и примерами на OSM

Люди пытались найти более быстрые способы передвижения на протяжении всей своей истории. Появление качественной дорожной системы в римской империи в своё время привело к её расцвету, но со временем выяснилось, что и в продуманных дорожных системах бывают забавные изъяны, как например в небезызвестной задаче о кёнигсбергских мостах, считающейся отправной точкой возникновения теории графов. Неудивительно и то, что с развитием вычислительной техники логистические задачи стали одними из первых, над которыми трудились первопроходцы компьютерных наук. Задача о кратчайшем пути -- одна из них, звучит достаточно просто: есть несколько городов и дорог, соединяющих пару городов между собой, мы хотим попасть из города А в город Б пройдя при этом минимальное расстояние. Первый системный подход к этой задаче был описан в работе Эгервари в 1931г., спустя 25 лет Эдсгер Дейкстра придумал алгоритм, который сейчас является частью любого уважающего себя базового курса алгоритмов на графах. На нём же, будем честны, заканчиваются знания о кратчайших путях у большинства профессиональных разработчиков, ибо сценариев, где реализации с википедии/stackoverflow будет не хватать, крайне мало.

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

Читать далее

Linux From Scratch на Zynq UltraScale+ MPSoC

Level of difficultyHard
Reading time17 min
Views7.2K

В данной статье я постараюсь описать процесс создания кастомного образа Linux на Zynq UltraScale+ MPSoCс. Каждый необходимый компонент будет собран отдельно с использованием соответствующих утилит. Статья разбита на разделы, которые шаг за шагом знакомят вас с процессом сборки и запуска системы на данной платформе.

Читать далее

Xv6: учебная Unix-подобная ОС. Глава 8. Файловая система

Level of difficultyMedium
Reading time21 min
Views3.2K

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

Файловая система xv6 предлагает Unix-подобные файлы, директории и пути и хранит данные на virtio-диске.

Глава расскажет, какие задачи решает файловая система xv6.

Читать далее

Одноплатные ПК весны 2024 года: что предлагает рынок разработчику?

Reading time6 min
Views25K

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

Полигон для творчества за 1500 р. Ч1: Позовите Кряка

Level of difficultyHard
Reading time10 min
Views12K

Приветствую вас, друзья! Не знаю как вам, а мне нравится разбирать всякие штучки, узнавать, как они работают, и применять их в своих проектах. По ходу дела начинается настоящее увлекательнейшее расследование, технический детектив.

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

Проведём расследование, поищем JTAG, узнаем способы и отследим разводку BGA, поработаем с ПЛИС, … и много других действительно интересных вещей. Кряк уже заинтересовался!

Как там у нас обычно? «Сломать, а потом читать инструкцию». Инструкций и документации нет, поэтому будем экспериментировать ломать! ☺
Читать дальше →

Как написать свою маленькую ОС

Level of difficultyEasy
Reading time7 min
Views50K


Большое начинается с малого. Например, ядро Linux 0.0.1 состояло всего из 10 239 строк кода, из них 20% комментарии. Такой проект вполне может осилить студент в качестве курсовой или дипломной работы, программируя по вечерам на домашнем ПК (собственно, Линус и написал его во время учёбы в университете, когда вернулся из армии).

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

Xv6: учебная Unix-подобная ОС. Глава 1. Интерфейсы операционной системы

Level of difficultyMedium
Reading time14 min
Views17K

Эта книга рассказывает о принципах работы операционных систем на примере xv6. Операционная система xv6 реализует базовый интерфейс, который Кен Томпсон и Деннис Ритчи предложили в операционной системе Unix, и подражает внутреннему устройству Unix. Комбинации простейших механизмов Unix дают удивительную свободу действий. Современные операционные системы признали успех Unix и реализуют похожие интерфейсы - BSD, Linux, macOS, Solaris, и даже Microsoft Windows. Изучение xv6 поможет понять работу и других операционных систем.

Читать далее

Книги, о которых редко говорят

Reading time4 min
Views51K

Дал ему подборку книг, он приходит месяца через два, и с порога такой сразу:
— Я с друзьями не могу разговаривать.
— Ну да есть такой, недостаточек.
интервью Жака Фреско

Читать далее

Поговорим об оптимизирующих компиляторах. Сказ восьмой: размотка циклов

Level of difficultyMedium
Reading time12 min
Views9.9K

Есть оптимизации, польза от которых очевидна всегда или почти всегда. Например, не делать лишнюю проверку лучше, чем делать. Не считать два раза одно и то же обычно лучше, чем считать (если только мы не упёрлись в нехватку регистров или имеем другие подобные проблемы на нижнем уровне). Вычислять выражения вне цикла выгоднее, чем в цикле. И так далее.

Но есть оптимизации, применение которых имеет как плюсы, так и минусы. Выиграв в одном месте, мы можем получить отрицательные эффекты в другом. Например, сэкономив на количестве проверок, мы можем раздуть общий объём кода и поломать микрооптимизации. Каноничным примером такой оптимизации, решение вопроса об использовании которой больше похоже на искусство, чем на науку, является размотка циклов (Loop Unrolling), о которой мы сегодня поговорим. В статье я попробую осветить как можно больше (хотя, наверное, и не все) соображения о том, почему эту оптимизацию может быть нужно или не нужно применять.

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

Читать далее

Графика древности: палитры, часть 2/2

Level of difficultyEasy
Reading time26 min
Views11K

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

Автосборка Fsbl, U-Boot, linux kernel и установка debian для arm64 для Zynq Ultrascale zcu106

Level of difficultyMedium
Reading time15 min
Views6.6K

В данной статье описывается способ создания минималистичного образа sd карты c debian arm64 на примере отладочной платы с zynq ultrascale zcu106. Данный способ можно использовать для создания загрузочных образов других устройств с соответствующими изменениями. Битстрим, ядро Linux и dts для удобства разработки размещаются отдельными файлами.

Также описан способ загрузки по сети ядра Linux, dts и корневой файловой системы debian, который позволит сократить время разработки и ресурс карты памяти.

Читать далее
1
23 ...

Information

Rating
5,020-th
Date of birth
Registered
Activity