​​Алгосы нужны? Когда-то давно в одном из каналов прочитал о | //АйТи интерн

​​Алгосы нужны?

Когда-то давно в одном из каналов прочитал о книжке Джона Бентли “Programming Pearls”. Недавно добрался до нее, вычитал одну любопытную историю, ставящую под сомнения некоторые “договоренности” в IT.

Физик Андрей Аппеля симулировал движение 10 000 планет. По его подсчетам работа "брутфорсного" алгоритма заняла бы несколько лет. Поэтому ученому пришлось углубиться в тюнинг производительности программы.

Ему удалось переписать выполнение 1 шага алгоритма с O(N^2) на O(N*logN), что дало ускорение в 12 раз. Как это удалось сделать? Пришлось сделать модель менее точной за счет добавления предположений и упрощения исходной задачи, чтобы использовать дерево поиска. Еще он оптимизировал сам алгоритм, обрабатывая некоторые краевые случаи отдельно.

Вишенкой стало переписывание на ассемблер одной функции, время выполнение которой занимало 98% от времени работы программы, а также покупка более производительного оборудования и изменение разрядности чисел с 64 бит на 32 бита.

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

Это еще один урок, и он не только про алгоритмы и структуры данных, но и про то, что разработка программного обеспечения это всегда компромиссы ("trade-off", его чаще используют в сленге) и программные системы - это не сферический конь в вакууме, а что-то работающее в реальном мире.

Получается, что алгоритмы все же нужны?

@it_intern
#алгоритмы #книги