I_love_Tanya_Romanova's blog

By I_love_Tanya_Romanova, 5 years ago, In Russian,

Предыстория: я уже много раз слышал/читал о том, что double начинает дико тупить, если получаются числа меньше 1e-306. Подобные разговоры всплывали после одного из контестов в зоне NEERC, после одного из раундов TC, еще видел такие фразы в обсуждении некоторых задач на различных online judge. Обычно советуют лечить это с помощью if (value<eps)value=0; Так как это мне всегда помогало, то выглядело вполне правдоподобно. Насколько это правда на самом деле?

Актуальная проблема: недавно столкнулся с похожей проблемой на СF. Сравните 3 сабмита: 7256779, 7256781, 7256786. Они отличаются только в void mult, при этом первое решение работает в десяток раз медленней двух остальных. Один из АС сабмитов действительно с костылем if(value<eps), в другом же разница в том, что две переменные заменены на локальные вместо глобальных. Кто-то может более-менее понятно объяснить, откуда такая разница в продуктивности?

Идем дальше. Выбросим из кода все лишнее) Этот код работает быстро и без проблем. Если переписать его вот так, в стиле кода, из-за которого и была создана эта тема, то продуктивность резко падает после 7 итерации (46 мс для 7 итераций, 1092 мс для 8 итераций, 2698 мс для 9 итераций). Обратите внимание, что в этом коде уже есть if (value<eps), но оно не помогает. Если сделать переменные локальными, как было в одном из примеров выше, то решение начинает проседать на одну итерацию позднее (62 мс для 8 итераций, 1653 мс для 9 итераций). Почему вообще так? И почему в этом случае костыль с <eps абсолютно никак не влияет на ситуацию — хотя в начальной задаче, в, казалось бы, аналогичной ситуации, локализация переменных/eps-костыль — одинаково полезные, с любым одним из этих фиксов решение отрабатывает 70 итераций за 7 секунд, без них — 11 итераций за 1.2 секунды, 12 итераций за 8 секунд, дальше TL.

 
 
 
 
  • Vote: I like it
  • +85
  • Vote: I do not like it