将多个数组组合成一个二进制数组（性能）

Question

我有一组[(x,y),(x,y),..]形式的（15-25）数组（每个数组大约250k个坐标对），我试图通过将它们（放入65.000bins！！）进行平均。我尝试了几个选项，但到目前为止，所有选项的性能都是次优的，我想知道是否有更有效的方法来做到这一点。你知道吗

我的第一个方法（此方法使用二进制搜索，这也是我迄今为止获得的最佳性能，平均每一组数组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坐标的顺序来保持尽可能有限的双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

第四种方法（使用数字化正如西蒙斯·吉本斯所说。这种方法总共需要1分钟多一点（平均1米15秒）。）

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数组（使用^{}），然后使用^{}进行装箱。你知道吗

虽然这仍然在幕后进行二进制搜索，但它将在快速编译的c代码中完成！你知道吗

在我做的一个快速测试中，这将在不到半秒钟的时间内处理25万个点的数组。你知道吗

---

如果你在x中的垃圾箱是单调递增的，你可以改为使用^{}，它应该做与np.digitize相同的事情，只是速度更快（数字化有时会退回到缓慢的线性搜索）

若要使用此方法，请在方法4中替换对数字化的调用

numpy.searchsorted(bins, mzArray)