OSt's blog

By OSt, 9 years ago, In Russian,

Здравствуйте. Продолжаю делиться своими наработками в области оценки производительности реализаций некоторых вещей на Java.

Часто в задачах на геометрию приходится искать расстояние от одной точки до другой.

Я нашёл 2 способа:

1. Стандартный : 

double dx = x1 - x2
double dy = y1 - y2

double res =  Math.sqrt(dx * dx + dy * dy);

2. Использование метода hypot() из модуля Math.

double dx = x1 - x2
double dy = y1 - y2

double res  = Math.hypot(dx, dy);


С первым всё предельно просто и понятно.

Второй же куда интересней и привлекательней, особенно если почитать о нем в javaDoc

"Returns sqrt(x2 +y2) without intermediate overflow or underflow."

Вроде о чудо - Sun создали очень хороший и грамотный метод для вычисления подобных вещей.

Но как оказалось - есть не слабая ложка дёгтя в этой бочке мёда. Это просто колоссальные временные затраты.

Ниже приведу результаты работы программы, которая оценивала время работы алгоритма для вычисления расстояний между точек:

(Тестовая машина  и софт такие же, как и в предыдущем посте.)

---With Hypot---
N Points = 1000
RunTime=1125 (millsec)
---With Sqrt---
N Points = 1000
RunTime=15 (millsec)

---With Hypot---
N Points = 3000
RunTime=13578 (millsec)
---With Sqrt---
N Points = 3000
RunTime=47 (millsec)

---With Hypot---
N Points = 6000
RunTime=61063 (millsec)
---With Sqrt---
N Points = 6000
RunTime=406 (millsec)

---With Hypot---
N Points = 9000
RunTime=135516 (millsec)
---With Sqrt---
N Points = 9000
RunTime=562 (millsec)

---With Hypot---
N Points = 10000
RunTime=164141 (millsec)
---With Sqrt---
N Points = 10000
RunTime=797 (millsec)

Как видно из результатов hypot() по времени отстаёт от sqrt() более чем в 200 раз.

Вывод : если вам нужна скорость - используйте стандартный метод, а если возможен вариант с переполнением - то придётся раскошелиться на hypot().

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