Рубрика «Алгоритмы» - 29

Как был побит рекорд в решении задачи коммивояжёра - 1

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

Они посчитали, что даже если Нэтану не удастся её решить, то в процессе работы он многому научится. Он согласился на эту идею. «Я не знал, что мне нужно бояться», — говорит Кляйн. «Я был всего лишь начинающим аспирантом, поэтому не понимал сложность этой задачи».
Читать полностью »

Как разработчику научного ПО мне приходится много программировать. И большинство людей из других научных областей склонны думать, что программирование — это «просто» набросать код и запустить его. У меня хорошие рабочие отношения со многими коллегами, в том числе из других стран… Физика, климатология, биология и т. д. Но когда дело доходит до разработки ПО, то складывается отчётливое впечатление, что они думают: «Эй, что тут может быть сложного?! Мы просто записываем несколько инструкций о том, что должен сделать компьютер, нажимаем кнопку „Выполнить” и готово — получаем ответ!»

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

Люди не понимают, что информатика учит вас теории вычислений, сложности алгоритмов, вычислимости (то есть можем ли мы действительно что-то вычислить? Слишком часто мы считаем само собой разумеющимся, что можем!) Информатика даёт знания, логику и методы анализа, помогающие написать код, который выполнится за минимальное количество времени или с минимальным использованием ресурсов.
Читать полностью »

image

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

Здравствуйте, друзья, как вы думаете, если мы напишем такой код:

s = a+b;
z = s-a;
t = b-z;

то не кажется ли вам, что в результате его выполнения получится, что t=0? С точки зрения привычной математики действительных чисел это и правда так, а вот с точки зрения арифметики с плавающей запятой в переменной t будет кое-что другое. Там будет то, что спасает нас от потери точности при сложении чисел $a$ и $b$. Кого интересует данная тема, прошу под кат.

Сложение двух чисел с плавающей запятой без потери точности - 3

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

Article

Вы сталкивались когда-нибудь с построением (непрерывного) пути обхода кривой на плоскости, заданной отрезками и кривыми Безье?

Вроде бы не сильно сложная задача: состыковать отрезки кривых в один путь и обойти его "не отрывая пера". Замкнутая кривая обходится в одном направлении, ответвления — в прямом и обратном, начало и конец в одном узле.

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

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

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

Приключение чисел в ASCII-ландии. Часть 0x01u. Беззнаковые целые числа - 1

Думаю, с переводом чисел в ASCII строки в своей жизни сталкивался каждый программист. В свое время для меня было удивительно узнать, что перевод десятичной цифры в равнозначный ASCII символ – операция сложения. С этим знанием я ложился спать, и с этим же знанием я бодро просыпался утром. Но однажды я задал себе вопрос – а как переводятся числа с плавающей запятой: Float или Double!? С этого момента, сна в моей жизни, а тем более крепкого и спокойного – стало меньше. Уверен, не я один задавался этим вопросом, и более того, не я один нашел ответ на оный. Но я думаю, есть те, кто заблудился, те, кто до сих пор неровно дышит от полного непонимания, что же происходит под капотом этих ваших трансляторов, компиляторов и прочего-прочего. Более того, не только полное отсутствие знаний в трансляции чисел нарушало мое психическое равновесие: люди, услышавшие мои душевные страдания, кидали сомнения в нужности и полезности этого знания. Мне говорили так: “Ну раскроешь ты завесу тайны, а дальше то что?! Напишешь свой велосипед, который будет работать в сто раз медленнее?! Иди ка ты, Ваня, асфальт укладывай, а мы тут великим займемся – вон, JSON пришел, надо еще подумать, как его переложить...”. Я же, парировал: “Нет, я напишу мотоцикл! Он будет быстр как Ямаха, а его рев будет устрашать даже матерых программистов!”.Читать полностью »

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

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

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

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

Как генерируются UUID - 1

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

Современную реализацию UUID можно проследить до RFC 4122, в котором описано пять разных подходов к генерированию этих идентификаторов. Мы рассмотрим каждый из них и пройдёмся по реализации версии 1 и версии 4.
Читать полностью »

Задача движения юнитов в играх является одной из ключевых задач, стоящих перед разработчиками игр. От того, как двигаются игровые юниты, во многом зависит восприятие всего геймплея в целом.
Традиционно считается, что достаточно реализовать алгоритм поиска пути и дальше всё будет работать само собой.
На практике же мы имеем совсем другую ситуацию.
Алгоритмы поиска пути разобраны досконально.
Нужен поиск пути с весами? A*. Нужен поиск для большого количества юнитов? Flow Field или кластеризация.
По большому счету по поиску пути не осталось не разобранных вопросов.
И вот, поиск пути реализован и довольный игродел запускает свою игру… И видит, что болванчики полностью оправдывают своё название. Они конечно находят путь и едут туда, куда им сказали. Но при этом спотыкаются о препятствия… Толкаются друг с другом или проезжают насквозь… Упираются друг в друга при встречном движении…
Эти проблемы и будем сегодня решать.
Реализация маневрирования юнитов в играх (избегание столкновений) - 1

Disclaimer

Данная статья не претендует на исчерпывающее решение обозначенной проблемы.
Я лишь рассказываю о том, как конкретно мне видится решение, над которым я работал. Это решение в оттюнингованном виде попало в один из зарелизенных в этом году РТС проектов, но осталось ли там на данный момент я не знаю. Комментарии и дополнения приветствуются.

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

Ещё один велосипед: храним юникодные строки на 30-60% компактнее, чем UTF-8 - 1

Если вы разработчик и перед вами стоит задача выбора кодировки, то почти всегда правильным решением будет Юникод. Конкретный способ представления зависит от контекста, но чаще всего тут тоже есть универсальный ответ — UTF-8. Он хорош тем, что позволяет использовать все символы Юникода, не тратя слишком много байт в большинстве случаев. Правда, для языков, использующих не только латиницу, «не слишком много» — это как минимум два байта на символ. Можно ли лучше, не возвращаясь к доисторическим кодировкам, ограничивающим нас всего 256 доступными символами?

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


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