Как оптимизировать вычисление периметра треугольника, минимизируя использование квадратных корней

Что проверяют

Хватит ли у вас честности сказать, что точный периметр по координатам без трёх корней не посчитать, и умеете ли вы искать выигрыш там, где он реально есть. Следом спрашивают, как вы докажете, что оптимизация что-то дала.

Как отвечать

Периметр это сумма трёх длин, каждая равна Math.sqrt(dx*dx + dy*dy). Сумма корней в общем случае не сводится к одному корню, поэтому для отдельного произвольного треугольника три вызова остаются. Выигрыш ищут в другом:

• сравнения без корня: если длина нужна, чтобы сравнить или отфильтровать («сторона длиннее порога», «ближайшая точка»), сравнивайте квадраты: dx*dx + dy*dy > r*r;
• переиспользование рёбер: в сетке треугольников внутреннее ребро общее для двух соседей. Посчитайте его длину один раз и сохраните, корней на всю сетку станет почти вдвое меньше;
• частные случаи: сторона, параллельная оси, имеет длину Math.abs(dx), корень не нужен;
• ранний выход: сумма |dx| + |dy| по сторонам даёт оценку периметра сверху. Если даже она меньше порога, точный периметр тоже меньше, и корни не нужны;
• приближения: если допустима погрешность в проценты, длину можно оценить без корня, но такой компромисс точности согласуют заранее.

Скажите и главное: Math.sqrt в HotSpot это интринсик, который компилируется в одну аппаратную инструкцию, сам корень стоит недорого. Прежде чем оптимизировать, замерьте через JMH: узким местом часто оказываются аллокации объектов Point или промахи кеша. Math.hypot точнее на крайних значениях и защищает от переполнения, но заметно медленнее.

Где спотыкаются

Пишут код, который считает квадраты сторон, потом всё равно берёт три корня, и называют это оптимизацией.

Путают периметр с площадью. Площадь считается вообще без корней, через векторное произведение: половина модуля (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1). Формула Герона требует тех же длин сторон и ещё одного корня.

Оптимизируют без замера: заменяют Math.sqrt самописной аппроксимацией и получают код медленнее и неточнее интринсика.