Эта статья посвящена бинарным деревьям поиска. Недавно делал статью про сжатие данных методом Хаффмана. Там я не очень обращал внимание на бинарные деревья, ибо методы поиска, вставки, удаления не были актуальны. Теперь решил написать статью именно про деревья. Пожалуй, начнем.
Дерево — структура данных, состоящая из узлов, соединенных ребрами. Можно сказать, что дерево — частный случай графа. Вот пример дерева:
Это не бинарное дерево поиска! Все под кат!
Читать полностью »
Эта статья может быть интересна тем, кто занимается сжатием данных или хочет написать собственный архиватор.
Статья написана, в основном, по материалам блога, который ведёт Fabian Giesen.
Читать полностью »
Всем привет! Сегодня я расскажу о своих экспериментах с системами частиц. Основной целью было нахождение простых правил, которые бы порождали интересное поведение.
Классический пример системы с простыми правилами и сложным поведением — клеточные автоматы, именно на них я и ориентировался, пытаясь подобрать правила. Конечно же, для клеточных автоматов правила будут в большинстве случаев проще. Но частицы могут быть красивее!
Под катом много мегабайт гифок.
От переводчика: публикуем для вас перевод статьи Стива Меррита, сотрудника Google, который рассказывает о том, как он решает типичные проблемы программирования. Пост будет полезен, в первую очередь, начинающим программистам.
В этой статье я расскажу о своей стратегии решения проблем, возникающих в ходе работы над проектом, от старта до финиша. Я использую ее в ежедневном рабочем процессе в Google, а также при работе с кодерами любых уровней (коллегами, выпускниками bootcamps, студентами университетов). Структурированная методика минимизирует затраты времени на отладку и одновременно приводит к созданию более качественного кода.
Кстати, эта же стратегия зачастую срабатывает в ходе собеседований в крупных технологичных корпорациях. Три года назад я получил работу в Google благодаря ей.
Читать полностью »
Шум Перлина придуман в 1983 году Кеном Перлином (получившим за это достижение премию Американской Академии кинематографических искусств и наук). Видите ли, в те времена все стремились к фотореализму, но его всегда не хватало. Кен Перлин придуман этот алгоритм шума, чтобы избавиться от жалкого «компьютерного» внешнего вида 3D-моделей. Шум — это генератор случайных чисел в компьютерной графике. Это случайный неструктурированный паттерн, он полезен в тех случаях, когда требуется источник подробных деталей, недостающих в очевидной структуре1. Шум Перлина — это многомерный алгоритм, используемый в процедурной генерации, текстурах, генерации рельефа, генерации карт, генерации поверхностей, генерации вершин, и так далее, и тому подобное.Читать полностью »
На рисунке ниже изображена трехмерная реконструкция сердца, полученная в результате работы современного томографа:
Для масштаба указана толщина луковицы аорты — 3.2 см, подумать только! Однако, когда у людей возникают проблемы с сердцем из-за сосудов, то речь, как правило, идет вовсе не о таких больших. На изображении видно, что сердце окружено более мелкими сосудами, и некоторые из них ответвляются прямо из крупных артерий. Это так называемые коронарные артерии, которые питают кровью непосредственно сердце. Если в них происходит сужение просвета (стеноз), например, из-за образования кальция, то уменьшается поток крови. Когда стеноз ярко выражен, то случается некроз ткани, другими словами инфаркт. Далее я расскажу о нашем подходе к вычислению границ сосудов, который в результате позволяет автоматически находить сужения и давать им оценку.
Читать полностью »
Жак Кернер — старший инженер-разработчик ПО в Avalanche Studios.
Как будто раньше игра была недостаточно безумной
Серия игр Just Cause и Avalanche Studios известны своей технологией открытого мира, обеспечивающего разнообразный и увлекательный игровой процесс. В последней версии игры — Just Cause 4 — добавлены ветер и погодные катаклизмы, ставшие новинкой в стеке технологий, углубляющих игровой процесс. Но экстремальные природные условия изначально задумывались не просто как способ симуляции более правдоподобного мира. Ярость природы управляется силами зла, противостоящими Рико Родригесу. Мы намеревались сделать так, чтобы ветер проявлялся более явно и экстремальные погодные условия не выглядели как внезапные события, чуждые этому миру. В этой статье представлены техники, разработанные нами для реализации ветра во всех его проявлениях с физической точки зрения, а также реакции на него всех объектов.
[Под катом около 120 МБ файлов GIF]
Читать полностью »
Почти у всех рекомендательных систем есть трудности с новым или редким контентом — поскольку с ним взаимодействовала лишь незначительная часть пользователей. В своём докладе на встрече «Яндекс изнутри» Даниил Бурлаков поделился набором трюков, которые используются в рекомендациях Музыки, и подробно разобрал популярную модель Singular Value Decomposition (SVD).
Плюс у нас есть такие исполнители, которые называются композиторами и обычно проставляются правообладателями просто веером. Только у одного Моцарта было «записано» более миллиона композиций.
— Всем привет! Меня зовут Даниил Бурлаков, я руковожу командой рекомендаций в Медиасервисах. Сегодня хочу рассказать про некоторые проблемы, которые мы решаем, когда занимаемся рекомендациями в Музыке.
В 1943 году американские нейропсихологи Мак-Каллок и Питтс разработали компьютерную модель нейронной сети, а в 1958 первая работающая однослойная сеть распознавала некоторые буквы. Сейчас же нейросети для чего только не используются: для прогнозирования курса валют, диагностики болезней, автопилотов и построения графики в компьютерных играх. Как раз про последнее и поговорим.
Евгений Туманов работает Deep Learning инженером в компании NVIDIA. По итогам его выступления на конференции HighLoad++ мы подготовили рассказ о применении Machine Learning и Deep Learning в графике. Машинное обучение не заканчивается на NLP, Computer Vision, рекомендательных системах и задачах поиска. Даже если вы не очень знакомы с этим направлением, то сможете применить наработки из статьи в своей области или индустрии.
Рассказ будет состоять из состоит из трех частей. Мы сделаем обзор задач в графике, которые решаются с помощью машинного обучения, выведем главную идею, и опишем кейс применения этой идеи в определенной задаче, а конкретно — в рендеринге облаков.Читать полностью »
В 2018 наша команда традиционно приняла участие в RecSys Challenge. Это ежегодный конкурс по рекомендательным системам, проводимый в рамках конференции RecSys. Он не такой масштабный, как конкурсы на Kaggle, но считается одним из самых престижных соревнований по рекомендательным системам. В этот раз задача была музыкальной — нужно было построить систему автоматического продолжения плейлистов. В этом посте я подробно рассказываю о нашем решении. Приглашаю под кат.
