elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Эффективный vs хороший
elizarov

В классическом анализе алгоритмов программистов учат писать эффективные алгоритмы, в том время как на практике нужен хороший код. Эффективные структуры данных и алгоритмы не всегда работают быстрей, и уж тем более не всегда являются лучшим решением стоящей перед программистом задачи. Чтобы наилучшим образом решить поставленную задачу, всегда нужно учитывать фактические ограничения и область применения. Бывает и так, что лучше, условно, написать за 1 час код, который будет потом отрабатывать за 1 секунду, чем потратить неделю, чтобы написать код который работает за 100 мс.

В соревнованиях по программированию задача перед программистом стоит максимально четко. Все ограничения и требования четко заданы. Чтобы победить, нужно написать самое простое решение, которое им всем удовлетворяет. В качестве примера, давайте посмотрим на задачу "Flights" с последнего полуфинала Чемпионата Мира.

Условие задачи, по своей сути, очень простое. Даны n парабол, представляющих траектории полета ракет по оси x. Надо ответь на m вопросов следующего вида: если взять параболы с номерами от t1 до t2, то какой у них будет максимум в интервале координат от x1 до x2?

Очевидно, что эту задачу можно решать "в лоб". Для каждого запроса можно пробежаться по соответствующему набору парабол, найти максимум для каждой параболы в интервале от x1 до x2 и выбрать максимум из них. Поиск максимума одной параболы можно делать разными способами. В любом случае, надо сделать несколько проверок, посмотрев относительное положение интервала запроса и параболы, и может посчитать значение параболы в одной из точек x1 или x2. Наиболее быстрым оказывается расчет полностью в вещественной арифметике, если квадратный трехчлен вычислять по схеме Горнера используя два вещественных умножения и два вещественных сложения: (a * x + b) * x + c. Удивительно, но это оказывается даже быстрей чем расчет через корни по схеме произведения биномов: a * (x - p) * (x - q), где в данной задаче можно сделать целочисленные разности и одно умножение в целых числах, оставив только одно вещественное умножение.

При максимальных по условию задачи n=50000 и m=20000, на моей машине ~2.4GHz членам жюри удалось добиться минимального времени работы такого решения примерно 6 секунд в худшем случае, то есть около 300 мкс на запрос или 6 нс на параболу.

Однако, по условиям соревнования участники должны были уложиться в 3 секунды на похожей машине. Как этого можно добиться? Для этого нужно построить эффективную структуру данных, которая позволит выполнять запросы эффективней, не тратя время на расчет всех n парабол при каждом запросе, то есть быстрее чем за O(n).

Такая структура данных организуется в несколько уровней. Нам нужно построить дерево отрезков по параболам, так чтобы любой диапазон парабол от t1 до t2 покрывался просмотром O(log n) узлов дерева. В каждом узле нам нужно будет эффективно искать максимум в диаппазоне координат от x1 до x2. Для этого нам придется построить кусочно-парабольную функцию максимума соответствующих парабол и дерево отрезков по координатам на ней в каждом узле интервального дерева по номерам парабол. Получившаяся структура данных, теоретически, даст нам возможность ответить на любой запрос за время порядка O(log2 n).

При n=50000 это, теоретически, более чем в 100 раз быстрей. Что же получается на практике? Эффективный алгоритм работает около 1.5 секунды то есть всего в 4 раза быстрей, правда без особых оптимизаций. Откуда же берется такая разница? Дело в том, что описанная выше структура данных занимает огромный объем памяти. Даже теоретически можно оценить занимаю память под эту структуру данных как O(n log n), а на практике её реализация "в лоб" занимает сотни мегабайт памяти. Память, это новый диск и работа со структурой такого размера, которая даже близко не влезает в кэш процессора, это дорогое удовольствие.

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


  • 1
1. Вы неправильно употребляете слова "практика", "эффективный" и "теоретический".
2. Вы употребляете слово "хороший" в текстах на серьёзные темы. Как приличному человеку, Вам должно быть стыдно!
3. Проблемы в данном случае возникают не из-за применения теории, а из-за незнания этой самой теории.

Это не серьезный текст, а скорее философский. Слово "хороший" как бы намекает.

Рома, по-моему, ты только что поговорил с ботом :)

А на основании чего ты сделал вывод, что он бот?

Мне так кажется по полному отсутствию привязки комента к тексту, кроме ключевых слов :)

к сожалению, я хуже

Стыдно не знать, что nponeccop — не бот ;-)

  • 1
?

Log in

No account? Create an account