Самый быстрый способ вычисления центроида набора координатных кортежей в python без numpy

Я работаю над проектом, который невероятно чувствителен к времени (к сожалению, должен быть в python), и одна из функций, которая широко используется, - это функция, которая вычисляет центр тяжести списка (x, y) кортежи. Чтобы проиллюстрировать:

def centroid(*points):
    x_coords = [p[0] for p in points]
    y_coords = [p[1] for p in points]
    _len = len(points)
    centroid_x = sum(x_coords)/_len
    centroid_y = sum(y_coords)/_len
    return [centroid_x, centroid_y]

где

>>> centroid((0, 0), (10, 0), (10, 10), (0, 10))
[5, 5]

Эта функция работает довольно быстро, приведенный выше пример завершается в среднем 1,49e-05 секунд в моей системе, но я ищу самый быстрый способ вычисления центроида. У вас есть идеи?

Одним из других решений, которые я имел, было сделать следующее (где l - список кортежей):

map(len(l).__rtruediv__, map(sum, zip(*l)))

который работает между 1,01e-05 и 9,6e-06 секунд, но, к сожалению, преобразование в список (путем окружения всего оператора в list( ... )) почти удваивает время вычисления.

EDIT: предложения приветствуются в чистом питоне, но не numpy.

EDIT2: только что выяснилось, что если для длины списка кортежей сохранена отдельная переменная, то моя реализация выше с помощью map работает надежно в течение 9,2e-06 секунд, но все еще существует проблема с обращением к список.

EDIT3:

Теперь я принимаю ответы только на чистом питоне, а не в numpy (извините за те, которые уже ответили в numpy!)

Ответы

Ответ 1

import numpy as np

data = np.random.randint(0, 10, size=(100000, 2))

это быстро

def centeroidnp(arr):
    length = arr.shape[0]
    sum_x = np.sum(arr[:, 0])
    sum_y = np.sum(arr[:, 1])
    return sum_x/length, sum_y/length

%timeit centeroidnp(data)
10000 loops, best of 3: 181 µs per loop

удивительно, что это намного медленнее:

%timeit data.mean(axis=0)
1000 loops, best of 3: 1.75 ms per loop

numpy кажется мне очень быстрым...

Для полноты:

def centeroidpython(data):
    x, y = zip(*data)
    l = len(x)
    return sum(x) / l, sum(y) / l
#take the data conversion out to be fair!
data = list(tuple(i) for i in data)

%timeit centeroidpython(data)
10 loops, best of 3: 57 ms per loop

Ответ 2

Это наивная реализация numpy, я не могу здесь разыграть, поэтому мне интересно, как это сделать:

import numpy as np

arr = np.asarray(points)
length = arr.shape[0]
sum_x = np.sum(arr[:, 0])
sum_y = np.sum(arr[:, 1])
return sum_x / length, sum_y / length

Вы передаете точки centroid() в виде отдельных параметров, которые затем помещаются в один кортеж с *points. Было бы быстрее просто передать список или итератор с точками.

Ответ 3

Просто для полноты я изменил функцию Retozi, чтобы она принимала вектор любого измерения:

def centeroidnp(arr):
    length, dim = arr.shape
    return np.array([np.sum(arr[:, i])/length for i in range(dim)])