python - 将多个数组组合成一个分箱数组(性能)

Question

我在[(x,y),(x,y),..]中有一组(15-25)个数组形式(每个数组大约 250k 坐标对)，我试图通过将它们分箱来平均(分箱到 65.000 箱!!)。我尝试了几种选择，但到目前为止，所有选项的性能都不是最佳的，我想知道是否有更有效的方法来做到这一点。

我的第一个方法(这个方法使用二分查找，这也是我迄今为止取得的最好的性能，平均每组数组1分钟多一点。)

def findNearest(self,array,value):
    if value >= array[0][0] and value <= array[-1][0]:
        diff = 1
        # First Pass
        a = 0
        b = len(array)
        while a < b:
            mid = (a+b)//2
            if array[mid][0] > value:
                b = mid
            else:
                a = mid+1
        if array[a][0] - value < diff:
            diff = array[a][0] - value
            index = a
        # Second Pass
        a = 0
        b = len(array)
        while a < b:
            mid = (a+b)//2
            if array[mid][0] < value:
                a=mid+1
            else:
                b=mid
        if array[a][0] - value < diff:
            diff = array[a][0] - value
            index = a
        return a    

# Section of another function that performs the summing
combinedSpectra = numpy.zeros(shape=(arraySize,2))
for index, i in enumerate(combinedSpectra):
    i[0] = ... # This generates the x-coordinates of the numpy array
for i in arraySet:
    for j in i:
        combinedSpectra[self.findNearest(combinedSpectra,float(j[0]))][1] += float(j[1]) 

我的第二种方法(此方法使用所有数组的串联列表，在 x 坐标上对它们进行排序，并使用 x 坐标的顺序来保持尽可能有限的 double for 循环。但是，此方法比第一种方法慢得多，主要用于说明我尝试过的替代方法。)

fullSet = []
for i in arraySet:
    for j in i:
        fullSet.append(j)
fullSet.sort(key = lambda tup: tup[0])
combinedSpectra = numpy.zeros(shape=(arraySize,2))
for index, i in enumerate(combinedSpectra):
    i[0] = ... # This generates the x-coordinates of the numpy array
for index1, i in enumerate(combinedSpectra[:-2]):
    for index2, j in enumerate(fullSet):
        if float(j[0]) >= float(combinedSpectra[index1+1][0]):
            break
        else:
            combinedSpectra[index1][1] += float(j[1])

第三种方法(此方法将二分查找与完整集合相结合。此方法也只需要不到 1 分钟，因此比方法 1 稍好。)

fullSet = []
for i in array[lowTime:highTime]:
    for j in i[1]:
        fullSet.append(j)
fullSet.sort(key = lambda tup: tup[0])
for i in fullSet:
    try:
        combinedSpectra[self.findNearest(combinedSpectra,float(i[0]))][1] += float(i[1])
    else:
        pass

第四种方法(按照 Simons Gibbons 的建议使用 numpy.digitize。此方法总共也需要 1 分钟多一点(平均 1 分 15 秒)。) p>

combinedSpectra = numpy.zeros(shape=(arraySize,2))
bins = []
for index, i in enumerate(combinedSpectra):
    i[0] = float(LOW_MZ) + index*(float(1)/float(SUM_SPECTRUM_RESOLUTION))
    bins.append(float(LOW_MZ) + index*(float(1)/float(SUM_SPECTRUM_RESOLUTION)))
fullSet = []
mz = []
for i in arraySet:
    for j in i[1]:
        fullSet.append(j)
        mz.append(j[0])
fullSet.sort(key = lambda tup: tup[0])
mz.sort()
mzArray = numpy.asarray(mz)
binsArray = numpy.asarray(bins)
test = numpy.digitize(mzArray,bins)
for index, i in enumerate(fullSet):
    combinedSpectra[test[index]-1][1]] += i[1]

我遇到的问题是，这一步对于整个程序的性能至关重要，因此我正在寻找替代方法来尝试使用我的数据，看看哪种方法可以提供最佳性能。

PS:关于我的数组中的数据的一些注释(以防止混淆):

1. 输入数组的长度不同
2. 输入数组(因此)具有不同的 x 坐标

Answer 1

由于您已经在使用 numpy，我建议将您的输入数据集转换为 numpy 数组(使用 np.asarray )，然后使用 np.digitize进行分箱。

虽然这仍然在幕后进行二分搜索，但它将在快速编译的 C 代码中执行此操作!

在我进行的快速测试中，这将在不到半秒的时间内处理 250k 点的数组。

<小时/>

如果您的 x 中的垃圾箱是单调递增的，您可以使用 np.searchsorted它应该做与 np.digitize 相同的事情，只是速度更快(数字化有时会退回到缓慢的线性搜索)

使用此方法替换方法 4 中对数字化的调用

numpy.searchsorted(bins, mzArray)