在没有numpy的情况下在python中计算一组坐标元组的质心的最快方法 [英] Fastest way to calculate the centroid of a set of coordinate tuples in python without 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(点)centroid_x = sum(x_coords)/_lencentroid_y = sum(y_coords)/_len返回 [centroid_x, centroid_y]

哪里

<预><代码>>>>质心((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( ... ) 中包围整个语句)几乎翻倍 计算时间.

欢迎在纯 python 中提出建议，但不是 numpy.

刚刚发现，如果为元组列表的长度保留一个单独的变量，那么我上面使用 map 的实现可以在 9.2e-06 秒内可靠地运行，但仍然存在转换回列表的问题.

编辑 3:

现在我只接受纯 python 的答案，而不接受 numpy 的答案(抱歉那些已经用 numpy 回答过的人！)

解决方案

import numpy as np数据 = np.random.randint(0, 10, size=(100000, 2))

这里很快

def centeroidnp(arr):长度 = arr.shape[0]sum_x = np.sum(arr[:, 0])sum_y = np.sum(arr[:, 1])返回 sum_x/长度，sum_y/长度%timeit centeroidnp(数据)10000 个循环，最好的 3 个:每个循环 181 µs

令人惊讶的是，这要慢得多:

%timeit data.mean(axis=0)1000 个循环，最好的 3 个:每个循环 1.75 毫秒

numpy 对我来说似乎很快...

为了完整性:

def centeroidpython(data):x, y = zip(*数据)l = len(x)返回 sum(x)/l, sum(y)/l#把数据转换出来是公平的！data = list(tuple(i) for i in data)%timeit centeroidpython(数据)10 个循环，最好的 3 个:每个循环 57 毫秒

I've been working on a project that is incredibly time sensitive (that unfortunately has to be in python) and one of the functions that is used extensively is a function that calculates the centroid of a list of (x, y) tuples. To illustrate:

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]

where

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

This function runs fairly quickly, the above example completing in an average of 1.49e-05 seconds on my system but I'm looking for the fastest way to calculate the centroid. Do you have any ideas?

One of the other solutions I had was to do the following (where l is the list of tuples):

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

Which runs in between 1.01e-05 and 9.6e-06 seconds, but unfortunately converting to a list (by surrounding the whole statement in list( ... )) nearly doubles computation time.

EDIT: Suggestions are welcome in pure python BUT NOT numpy.

EDIT2: Just found out that if a separate variable is kept for the length of the list of tuples, then my above implementation with map runs reliably under 9.2e-06 seconds, but there's still the problem of converting back to a list.

EDIT3:

Now I'm only accepting answers in pure python, NOT in numpy (sorry to those that already answered in numpy!)

解决方案

import numpy as np

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

this here is fast

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

surprisingly, this is much slower:

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

numpy seems very quick to me...

For completeness:

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

这篇关于在没有numpy的情况下在python中计算一组坐标元组的质心的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！