Рубрика «algorithms»

Под капотом сортировок в STL - 1

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

При написании статьи я использовал стандарт C++17. В качестве реализаций рассматривал GCC 10.1.0 (май 2020) и LLVM/Clang 10.0.0 (март 2020). В каждой и них есть своя реализация STL, а значит и std алгоритмов.

Читать полностью »

Привет! Представляю вашему вниманию перевод статьи "ECS back and forth — Part 1 — Introduction" автора Michele skypjack Caini.

ECS back and forth

Часть 1 — Введение.

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

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

Почему я должен использовать ECS?

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

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

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

Читать полностью »

Привет! Представляю вашему вниманию перевод статьи
"How does a relational database work".

Когда дело доходит до реляционных баз данных я не могу не думать, что чего-то не хватает. Они используются везде. Существует множество различных баз данных: от небольшого и полезного SQLite до мощной Teradata. Но есть только несколько статей, которые объясняют, как работает база данных. Вы можете искать сами по запросу "howdoesarelationaldatabasework" («как работают реляционные базы данных») чтобы увидеть, как мало результатов. Более того, эти статьи — короткие. Если же вы ищете последние модные технологии (BigData, NoSQL или JavaScript), вы найдете больше углубленных статей, объясняющих, как они работают.

Являются ли реляционные базы данных слишком старыми и слишком скучными, чтобы их можно было объяснить вне университетских курсов, исследовательских работ и книг?

image

Читать полностью »

Всем привет! Новогодние праздники подошли к концу, а это значит, что мы вновь готовы делиться с вами полезным материалом. Перевод данной статьи подготовлен в преддверии запуска нового потока по курсу «Алгоритмы для разработчиков».

Поехали!


Метод обратного распространения ошибки – вероятно самая фундаментальная составляющая нейронной сети. Впервые он был описан в 1960-е и почти 30 лет спустя его популяризировали Румельхарт, Хинтон и Уильямс в статье под названием «Learning representations by back-propagating errors».Читать полностью »

Привет! Представляю вашему вниманию перевод статьи «Don’t Ever Ignore Reinforcement Learning Again» автора Michel Kana, Ph.D.

Обучение с учителем и обучение без учителя — это ещё не все. Все это знают. Начните с OpenAI Gym.

image

Собираетесь победить чемпиона мира по шахматам, нардам или го?

Есть способ, который позволит вам это сделать — обучение с подкреплением.
Читать полностью »

Завершилось мое участие в чемпионате по программированию. Я неплохо прошел квалификацию, решив 4 из 6 задач и шел на 20 месте, поэтому были надежды и в финале попасть топ 20.
Но к сожалению не удалось попасть даже в топ-100. После драки кулаками не машут, но я смог решить еще несколько задач по завершению. Предлагаю вашему вниманию все решенные мной задания.
Читать полностью »

И снова здравствуйте. Прежде чем уйти на выходные хотим поделиться с вами переводом материала, который был подготовлен специально для базового курса «iOS-разработчик».

Выбираем правильную структуру данных в Swift - 1


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

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

Разбираемся в основах Blockchain: Задача Византийских Генералов. Часть 1 - 1


Блокчейн – это децентрализованная система, состоящая из различных субъектов, которые действуют в зависимости от своих стимулов и имеющейся у них информации.

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

Ускоряем распределенную обработку больших графов с помощью вероятностных структур данных и не только - 1

Одним из самых ценных ресурсов любой социальной сети является "граф дружб" — именно по связям в этом графе распространяется информация, к пользователям поступает интересный контент, а к авторам контента конструктивный фидбэк. При этом граф является еще и важным источником информации, позволяющим лучше понять пользователя и непрерывно совершенствовать сервис. Однако в тех случаях когда граф разрастается, технически извлекать из него информацию становится все сложнее и сложнее. В данной статье мы поговорим о некоторых трюках, используемых для обработки больших графов в OK.ru.

Читать полностью »

Алгоритмы – одна из центральных тем в программировании, они повсюду (особенно на собеседованиях, ха-ха).

image
(Разве можно обойтись в таком посте без «баяна»?)

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


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js