Как стать автором
Обновить
168.37

Алгоритмы *

Все об алгоритмах

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

Вороной, Манхэттен, рандом

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

Это история про то, как не довести дело до конца, но получить уйму опыта, и вообще ни разу не обломаться.

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

Осторожно, очень много картинок!

Читать далее
Всего голосов 22: ↑22 и ↓0 +22
Комментарии 8

Новости

Шпаргалка для алгособеса — алгоритмическая сложность, структуры данных, методы сортировки и Дейкстра

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

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

Так уж повелось, что любой уважающий себя работодатель перенимает передовые^✻ методики FAANG — по этой причине практически во всех IT-собесах есть она: секция алгоритмов. Кто-то ей рад, кто-то не очень, но секция есть и уходить пока не планирует. Поэтому нужно закатать рукава и достойно встретить суровую реальность.

Читать далее
Всего голосов 82: ↑81 и ↓1 +80
Комментарии 19

Работа процессора (физический препроцессор) без счётчика команд

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

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

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

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

Читать далее
Всего голосов 9: ↑3 и ↓6 -3
Комментарии 2

Компилятор за выходные: избавляемся от переменных

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

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

Продолжаем разговор о минималистичном компиляторе, который вполне реально написать за выходные. Задачей стоит транслировать код из придуманного мной языка в x86 ассемблер. Мой компилятор состоит из 611 строк кода, при этом не имеет ни единой зависимости:

ssloy@khronos:~/tinycompiler$ cat *.py|wc -l

611

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

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

Читать далее
Всего голосов 34: ↑33 и ↓1 +32
Комментарии 26

Истории

Зачем учить алгоритмы?

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

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

Читать далее
Всего голосов 16: ↑11 и ↓5 +6
Комментарии 13

Реализация слоев в NN (часть 1)

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

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

Читать далее
Всего голосов 9: ↑9 и ↓0 +9
Комментарии 6

Закон парадокса в логике и математике

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

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

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

Читать далее
Всего голосов 7: ↑6 и ↓1 +5
Комментарии 87

Минималистическая модель живой клетки в браузере

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

Вы когда-нибудь задумывались, как действуют клетки — элементарные единицы живой материи? Я программист, но одновременно увлекаюсь клеточной биологией. Поэтому я решил смоделировать работу простейшей клетки на TypeScript. Вообще, клетки невероятно сложны; по оценкам учёных, человеческая клетка в среднем содержит 100 триллионов атомов. По-прежнему очень мало известно о том, как все эти биомолекулы взаимодействуют в клетке, поэтому в точности смоделировать работу клетки невозможно.

Размышляя на эту тему, я нашёл статью Fundamental behaviors emerge from simulations of a living minimal cell (Фундаментальные виды поведения возникают на основе моделирования простейшей живой клетки). Опираясь на кинетические параметры, авторы статьи создали модель взаимодействия молекул и химических реакций между ними в простейшей известной клетке. Затем эта симуляция запускается, и на её  основе можно наблюдать такие процессы как репликация ДНК, метаболизм и синтез белков.

Читать далее
Всего голосов 13: ↑13 и ↓0 +13
Комментарии 8

Как языковая модель предсказывает следующий токен (часть 1)

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

Я обучил небольшой (порядка 10 миллионов параметров) трансформер по превосходному туториалу Let’s build GPT: from scratch, in code, spelled out Андрея Карпати. После того, как он заработал, я захотел максимально глубоко понять, как он устроен внутри и как создаёт свои результаты.

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

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

Если вы знакомы с трансформерами и хотите сразу узнать вывод, то он таков: каждый блок трансформера (содержащий слой многоголового внимания и сеть с прямой связью) изучает веса, связывающие конкретный промт с классом строк, найденных в обучающем корпусе. Распределение токенов, соответствующее этим строкам в обучающем корпусе, и есть приблизительно то, что блок выводит как прогноз для следующего токена. Каждый блок может ассоциировать один и тот же промт со своим классом строк обучающего корпуса, что приводит к другому распределению следующих токенов, а значит, и к другим прогнозам. Окончательный результат работы трансформера — это линейное сочетание прогнозов каждого блока.

Читать далее
Всего голосов 24: ↑24 и ↓0 +24
Комментарии 5

Детекция объектов. YOLO. Часть 2

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

Кто такой YOLO? 🤔

Когда пытаешься разобраться в работе YOLO по статьям в интернете, постоянно натыкаешься на примерно такое объяснение: «Алгоритм делит изображение сеткой SxS, где каждому элементу этой сетки соответствует N ббоксов с координатами, предсказаниями классов и тд...». Но лично мне становилось только непонятнее от такого высокоуровнего описания.. Ведь в исследованиях часто всё происходит примерно так: перебирают гипотезы, пока не получат приемлемый результат, а потом уже придумывают красивое описание. Поэтому для ясности хочется в данной статье рассказать, как вообще приходили к идеям, которые ложились в основу YOLOv1 и последующих версий.

Читать далее
Всего голосов 6: ↑6 и ↓0 +6
Комментарии 0

Звёзды-родственники: зачем и как мы их ищем, данные + код (Python)

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

В настоящее время, благодаря передовым обсерваториям, космическим телескопам и миссиям, включающим (но не ограничивающимся) Hubble, Kepler, Gaia, возможности для изучения звезд и их скоплений вышли на новый уровень. Технологии позволяют не только проникнуть в глубины космоса, но и наблюдать реальность с невиданной ранее детализацией. Благодаря им и обнаруживаются "звёзды-родственники" (т.е. звёзды, образовавшиеся из одного облака). Эти объекты обладают схожими характеристиками, включая химический состав, возраст и скорость движения.

Выявление звезд общего происхождения имеет важное значение для наших попыток понять устройство мира на глобальном уровне.

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

Посмотреть наверх
Всего голосов 16: ↑16 и ↓0 +16
Комментарии 0

Новая архитектура в интерпретации древних

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

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

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

Читать далее
Всего голосов 12: ↑7 и ↓5 +2
Комментарии 12

Тестируем многоядерный процессор методом Кнута и Python’а

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

В 1978 году вышел третий том монографии Дональда Кнута «Искусство программирования», где автор рассматривает алгоритмы сортировки и поиска. Помимо самих алгоритмов описаны аппаратные характеристики компьютера и их влияние на производительность при работе с алгоритмами.

В 2024 году мы с вами возьмём классические алгоритмы сортировки и посмотрим, как работает современный многоядерный процессор при сортировке нескольких массивов на одном и нескольких логических ядрах. Мы напишем приложение с графическим интерфейсом (GUI) на фреймворке Qt, обойдем глобальную блокировку интерпретатора (GIL), воспользуемся несколькими потоками, на один из которых переложим выполнение асинхронного цикла событий, и распараллелим этот поток для реализации параллельных вычислений.

Читать далее
Всего голосов 21: ↑19 и ↓2 +17
Комментарии 13

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

One Day Offer от УЦСБ
Дата 17 февраля
Время 10:00
Место
Онлайн

Построение планов параллельного выполнения программ для процессоров со сверхдлинным машинным словом (проект)

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

Процессоры архитектуры  сверхдлинного машинного слова (VLIW - Very Long Instruction Word) относятся к специфическим классам архитектур, прямо нацеленным на использование внутреннего параллелизма в алгоритмах (программах), причём параллелизм этот анализируется и планируется к рациональному использованию при вычислениях на программном уровне; собственно аппаратная часть освобождается от процедур распараллеливания  (и поэтому должна стать проще и экономичнее использующих внутреннее распараллеливание).

VLIW-подход основан на идее загрузки во входной буфер процессора одновременно набора (bundle) допускающих параллельное выполнение  машинных команд и исполнения этого ряда команд аналогично единой команде в процессорах классической архитектуры. VLIW-процессоры реализуют параллелизм уровня ILP (Instruction-Level Parallelizm, параллелизм уровня машинных инструкций) и SMP (Symmetric MultiProcessing, системы с общей памятью)   идеологему работы с оперативной памятью. Несмотря на выпуклое преимущество (программным путём дешевле реализовать сложные процедуры параллелизации), работа VLIW-процессоров сопряжена с известными проблемами. Среди них называют статичность полученных планов параллельного выполнения и проблемы с излишней неравномерностью времени доступа к оперативной памяти разных вычислительных ядер   (временна́я антиплотность кода,   следствием является резкое снижение производительности из-за неизбежности  определять время выполнения всей связки команд сверхдлинного слова по продолжительности наиболее длинной из них).

Читать далее
Всего голосов 13: ↑12 и ↓1 +11
Комментарии 21

Метод конечных элементов своими руками

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

Метод конечных элементов (МКЭ) применяют в задачах упругости, теплопередачи, гидродинамики — всюду, где нужно как-то дискретизировать уравнения сплошной среды или поля. На Хабре было множество статей с красивыми картинками о том, в каких отраслях и с помощью каких программ этот метод приносит пользу. Однако мало кто пытался объяснить МКЭ от самых основ, с простенькой учебной реализацией, желательно без упоминания частных производных через каждое слово.

Мы напишем МКЭ для расчёта упругой двумерной пластины на прочность и жёсткость. Код займёт 1200 строк. Туда войдёт всё: интерактивный редактор, разбиение модели на треугольные элементы, вычисление напряжений и деформаций, визуализация результата. Ни одна часть алгоритма не спрячется от нас в недрах MATLAB или NumPy. Код будет ужасно неоптимальным, но максимально ясным.

Размышление над задачей и написание кода заняли у меня неделю. Будь у меня перед глазами такая статья, как эта, — справился бы быстрее. У меня её не было. Зато теперь она есть у вас.

Читать далее
Всего голосов 66: ↑66 и ↓0 +66
Комментарии 54

Поисковый движок в 80 строках Python

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

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

Давайте поговорим о целях. Слышали когда-нибудь о «кризисе сложности обнаружения маленьких веб-сайтов»? Проблема в том. что маленькие веб-сайты наподобие моего невозможно найти при помощи Google или любого другого поискового движка. Какова же моя миссия? Сделать эти крошечные веб-сайты снова великими. Я верю в возвращение славы этих малышей вдали от SEO-безумия Google.

В этом посте я подробно расскажу о процессе создания поискового движка с нуля на Python. Как обычно, весь написанный мной код можно найти в моём GitHub (репозиторий microsearch). Эта реализация не будет притворяться готовым к продакшену поисковым движком, это лишь полезный пример, демонстрирующий внутреннюю работу поискового движка.

Кроме того, мне стоит признаться, что в заголовке поста я слегка преувеличил. Да, поисковый движок действительно реализован примерно в 80 строках Python, но я ещё и писал вспомогательный код (краулер данных, API, HTML-шаблоны и так далее), из-за которого весь проект становится немного больше. Однако я считаю, что интересная часть проекта находится в поисковом движке, который состоит из менее чем 80 строк.

P.S. Написав этот пост и microsearch, я осознал, что пару лет назад нечто похожее написал Барт де Гёде. Моя реализация очень похожа на работу Барта, но я считаю что кое-что улучшил, в частности: (1) мой краулер асинхронный, что сильно ускоряет работу, (2) я реализовал пользовательский интерфейс, позволяющий взаимодействовать с поисковым движком.

Читать далее
Всего голосов 29: ↑29 и ↓0 +29
Комментарии 4

Разбираем самый маленький JPEG в мире

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

Недавно на Хабре была опубликована статья Разбираем самый маленький PNG в мире. Интересно, а какой самый маленький файл JPEG? В ответах на StackOverflow и Reddit можно встретить размеры 107, 119, 125, 134, 141, 160 байтов. Все они представляют серый прямоугольник 1 на 1. И кто прав? Все правы, просто такая разница объясняется различными режимами кодирования и степенью строгости соответствия стандарту. Описание всех нюансов разрослось до целой статьи cо всеми необходимыми подробностями для более-менее хорошего знакомства с самыми маленькими jpeg-ами. После краткой теории разберем 159-байтный файл на КДПВ, а затем рассмотрим способы его уменьшения.

Читать далее
Всего голосов 40: ↑40 и ↓0 +40
Комментарии 6

Стеки и Очереди в Swift

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

В этой статье мы исследуем две фундаментальные структуры данных, которые являются неотъемлемой частью программирования на Swift: стеки и очереди. Они представляют собой коллекции элементов с особыми правилами для добавления и удаления элементов. Стеки работают по принципу "последним пришел, первым ушел" (LIFO), что делает их идеальными для задач, связанных с обратной навигацией или отменой действий. Очереди, следуя принципу "первым пришел, первым ушел" (FIFO), идеально подходят для задач, требующих обработки элементов в порядке их поступления, например, в управлении задачами или потоками данных.

Читать далее
Всего голосов 6: ↑4 и ↓2 +2
Комментарии 6

Pandas в pandas'е: упаковываем документацию в датафрейм

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

Документация к сложным библиотекам на питоне (напр. pandas) хранится в doc-строках и разбросана по сотням страниц сайта. В этой статье мы с помощью небольшого кода упакуем её (информацию из документации для каждого класса и метода) в... датайфрейм. Но зачем? Во-первых, это прикольно так её можно быстро искать и анализировать. Во-вторых, изучим некоторые встроенные питоновские средства работы с документацией. Наконец, такой датафрейм потенциально может стать основой для обучения/дообучения GPT-моделей писать более корректный, безошибочный, использующий всевозможные функции и их аргументы, код...

Читать далее
Всего голосов 3: ↑3 и ↓0 +3
Комментарии 0

Два сапога — пара, а три — уже community: как алгоритмы на графах помогают собирать группы товаров

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

Привет, Хабр! Меня зовут Иван Антипов, я занимаюсь ML в команде матчинга Ozon. Наша команда разрабатывает алгоритмы поиска одинаковых товаров на сайте. Это позволяет покупателям находить более выгодные предложения, экономя время и деньги.

В этой статье мы обсудим кластеризацию на графах, задачу выделения сообществ, распад карате-клуба, self-supervised и unsupervised задачи — и как всё это связано с матчингом.

Читать далее
Всего голосов 70: ↑70 и ↓0 +70
Комментарии 12

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