Способ ускорения вычисления расстояния между вершинами с помощью numpy

Я боролся с алгоритмом, связанным с сопоставлениями с векторами трехмерного треугольника. К сожалению, он очень медленный в местах, и я пошел туда и обратно по различным методам, чтобы попытаться его улучшить. Одна вещь, с которой я борюсь, - это ускорение расчета расстояния.Способ ускорения вычисления расстояния между вершинами с помощью numpy

У меня есть две группы треугольников, которые были разбиты на три точки, каждый из которых имеет вектор 3d float (xyz). Расчеты я использую являются:

diffverts = numpy.zeros(( ntris*3, ntesttris*3, 3), dtype = 'float32') 
    diffverts += triverts.reshape(ntris*3, 1, 3) 
    diffverts -= ttriverts.reshape(1, ntesttris*3, 3) 
    vertdist = (diffverts[:,:,0]**2 + diffverts[:,:,1]**2 + diffverts[:,:,2]**2) ** 0.5

этот расчет быстрее:

diffverts = triverts.reshape(ntris*3, 1, 3) - ttriverts.reshape(1, ntesttris*3, 3) 
    vertdist = (diffverts[:,:,0]**2 + diffverts[:,:,1]**2 + diffverts[:,:,2]**2) ** 0.5

Есть ли более быстрый способ для заполнения дифференциала верт часть (которая занимает самый длинный) и/или расстояние часть который также занимает много времени? Этот код называется много раз из-за количества тестируемых групп. Кроме того, попытка сделать это только по индексам в verts вызывает другие проблемы с дальнейшими вычислениями при попытке вернуться к некоторым логическим тестам (т. Е. Это только один из множества вычислений, поэтому лучше всего работать на уровне трех точек.

Я использую NumPy и питона

источник

2014-02-13 user1942439

Я не знаю о слишком большом количестве, но если вам нужны только относительные расстояния, оставьте квадратный корень. Квадратный корень - довольно медленная операция в целом. Кроме того, я не уверен, как он оптимизирует это, но иногда «pow (n, 2)» виды вещей медленнее, чем «n * n». – Hans

Привет, Ханс, да, я могу уйти от squareroot, хотя мне нужно применить расстояние в форме soem к моим результатам позже. Тем не менее, я не думаю, что это очень помогает скорости (относительно). В этом примере через базовый набор петель, которые я просматриваю (т. Е. Со всеми группами), настройка части diff verts составляет около 60-70% времени v, когда фактическая дистанционная часть составляет около 30-40% – user1942439

С какими размерами вы работаете? – Hans

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

Посмотрите на scipy.spatial.cKDTree. Помощь должна быть понятной.

источник

2014-02-13 15:52:57

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

Есть; если вы используете cKDTree, вся грубая силовая подстановка каждой точки по сравнению со всеми остальными никогда не произойдет. –

У вас есть пример того, как использовать cKDTree для получения a) точек на заданном расстоянии. б) фактическое расстояние и в) булевский массив triverts * ttriverts в размере, чтобы сказать, какие из них были действительными? Если я не смогу добраться до всех трех этапов, то это не так много, я боюсь. Мне нужно b для использования позже, и мне нужно c, чтобы сравнить с 3 другими углами. – user1942439

Я думаю, что diffverts занимает достаточно памяти, чтобы вызвать промахи в кеше. К сожалению, в то время как это решение очень изящно, вам, вероятно, лучше всего вычислить все расстояние за один раз, чтобы избежать необходимости сохранять массив промежуточных значений n * m * 3. Как ни безобразие, я бы просто вложил в петли.

источник

2014-02-13 17:02:27 Hans

Я также использую некоторые внутренние вычисления для расчета трех углов вычисления. Они примерно на 10 * быстрее для тех же размеров. Я также делал некоторые тесты ранее против некоторых вложенных циклов, но они были медленнее. Так как количество тестируемых групп вложено в любом случае, чтобы вырезать цикл. – user1942439

Когда я устал, чтобы выполнить сравнение с оригиналом (см. Комментарий в первом ответе), я получил ошибку памяти, поэтому вы, вероятно, правы, что часть проблемы связана с размерами. Я расстроюсь и посмотрю, поможет ли это. – user1942439

Способ ускорения вычисления расстояния между вершинами с помощью numpy

ответ

Смежные вопросы