邻域内不超过1点的并行滤波方法

Question

我有一个23x23x30的空间，每个1x1x1的立方体代表一个点，其中一些23x23x30点填充了从-65 to -45到5x5x30的数字，我想确保在一个填充点周围的5x5x30的任何给定区域中不应该有超过1个数字，如果在5x5x30的任何区域中有多个点，这些点最小的数字应该去掉。我已经用嵌套的for循环以串行方式完成了这个操作，但这是非常昂贵的操作。我想把这个操作并行化。我有n个核心，每个核心在23x23x30的总区域中有自己的子区域，没有任何重叠。我可以收集这些“子区域”并构建上面提到的23x23x30的完整区域，这样所有核心都可以在拥有自己的“子区域”的同时访问23x23x30的完整区域。我不确定在python中是否有可用于这种操作的库。在我的应用程序中，8个进程将用大约3500点填满这个23x23x30空间，现在我在所有8个进程上做这个“过滤”操作（即复制工作）这是资源浪费，所以我必须并行地做这个“过滤”以有效地使用可用资源。你知道吗

下面是序列码：self.tntatv_stdp_ids是一个字典，它的键是step1，step2….在维度中最多30步，z。这些键具有该步骤中填充的点的编号（1 to 529）。注意，在代码的串行实现中，z维度中的每个步骤中的点都来自1 to 529。你知道吗

self.cell_voltages是一个字典，在维度中有step1，step2….到30步，z。每个键都给出了一个点上的数字。你知道吗

     a_keys = self.tntatv_stdp_ids.keys()

    #Filter tentative neuron ids using suppression algo to come up with final stdp neuron ids. 
    for i in range(0,len(a_keys)):
        b_keys= list(set(a_keys) - set([a_keys[i]]))
        c_keys = self.tntatv_stdp_ids[a_keys[i]]

        for j in range(0,len(b_keys)):
            d_keys=self.tntatv_stdp_ids[b_keys[j]]
            for k in c_keys[:]:
                key = k 
                key_row= key/(image_size-kernel+1)
                key_col = key%(image_size-kernel+1)
                remove =0
                for l in d_keys[:]:
                    target = l 
                    tar_row = target/(image_size-kernel+1)
                    tar_col = target%(image_size-kernel+1)

                    if(abs(key_row-tar_row) > kernel-1 and abs(key_col-tar_col) > kernel-1):
                        pass
                    else:
                        if(self.cell_voltages[a_keys[i]][key]>=self.cell_voltages[b_keys[j]][target]):
                            d_keys.remove(target)
                        else:
                            remove+=1
                if(remove):
                    c_keys.remove(key)

在这个操作结束时，如果在30的23x23x1区域中有多个剩余点，那么可以通过查看23x23x1点的剩余填充点中的哪个具有最高的数量来选择这些3023x23x1区域中的每个30区域的最终赢家点。这样，最大赢家数可以是30中所有点的23x23x30，每个23x23x1点1个。也可以少于30，这取决于从多少23x23x30点开始填充。你知道吗

Answer 1

此问题可能不需要并行化：

# Generate a random array of appropriate size for testing
super_array = [[[None for _ in range(30)] for _ in range(529)] for _ in range(529)]
for _ in range(3500):
    super_array[random.randint(0, 528)][random.randint(0, 528)][random.randint(0,29)] = random.randint(-65, -45)

第一步是构建已填充节点的列表：

filled = []
for x in range(len(super_array)):
    for y in range(len(super_array[0])):
        for z in range(len(super_array[0][0])):
            if super_array[x][y][z] is not None:
                filled.append((x, y, z, super_array[x][y][z]))

然后，将列表从高到低排序：

sfill = sorted(filled, key=lambda x: x[3], reverse=True)

现在，生成一个阻塞网格：

block_array = [[None for _ in range(529)] for _ in range(529)]

并遍历列表，在查找节点时封锁邻域并删除已占用邻域中的节点：

for node in sfill: 
    x, y, z, _ = node
    if block_array[x][y] is not None:
        super_array[x][y][z] = None  # kill node if it's in the neighborhood of a larger node
    else: # Block their neighborhood
        for dx in range(5):
            for dy in range(5):
                cx = x + dx - 2
                cy = y + dy - 2
                if 529 > cx >= 0 and 529 > cy >= 0:
                    block_array[cx][cy] = True

注意事项：

• 它使用一个滑动邻域，因此它检查以每个节点为中心的5x5。从最高点到最低点进行检查很重要，因为这样可以确保被删除的节点之前没有强制删除其他节点。

• 通过执行ranges而不是一个完整的529x529数组，您可以更有效地执行此操作，但是邻域阻塞只需不到1秒，从生成的数组到修剪的最终列表的整个过程仅需1.2秒。

• 只需在任何z堆栈中添加值最高的节点，就可以改进填充节点列表的构建。这将减少必须排序的列表的大小，如果大量节点以相同的x，y值结束。

在23x23x30上，大约需要18毫秒，同样包括构建3d阵列的时间：

timeit.timeit(prune_test, number=1000)
17.61786985397339