比numpy的in1d掩码函数做得更好：有序数组？

2018-06-24 23:19:28

该操作需要尽可能快地应用于包含数百万个元素的实际数组。这是该问题的简单版本。

所以，我有一个随机数组（通常是数百万个元素）。

totalIDs = [5,4,3,1,2,9,7,6,8 ...]

我有另一个数组（通常是数以万计）的独特整数，我可以创建一个掩码。

subsampleIDs1 = [5,1,9]
subsampleIDs2 = [3,7,8]
subsampleIDs3 = [2,6,9]
...

我可以用numpy做

mask = np.in1d（totalIDs，subsampleIDs，assume_unique = True）

然后我可以使用掩码提取我想要的另一个数组的信息（比如列0包含我想要的）。

变量= allvariables [掩码] [：，0]

现在考虑到ID在两个阵列中都是唯一的，是否有任何方法可以显着提高速度。构建与数百万个ID（totalID）匹配的数千个点（子样本ID）的掩码需要很长时间。

我想过一遍，写出一个索引的二进制文件（以加速未来的搜索）。

for i in range(0,3):
    mask = np.in1d(totalIDs,subsampleIDs,assume_unique=True)
    index[mask] = i

其中X在subsampleIDsX中。然后我可以这样做：

for i in range(0,3):
    if index[i] == i:
        rowmatch = i
        break

variable = allvariables[rowmatch:len(subsampleIDs),0]

对？但是这也很慢，因为循环中有一个条件来查找它第一次匹配的时间。有没有更快的方法来查找数字第一次出现在有序数组中，以便条件不会减慢循环？

我建议你在Pandas中使用DataFrame。 DataFrame的索引是totalID，您可以通过以下方式选择子采样df.ix[subsampleIDs] ： df.ix[subsampleIDs] 。

首先创建一些测试数据：

import numpy as np
N = 2000000
M = 5000
totalIDs = np.random.randint(0, 10000000, N)
totalIDs = np.unique(totalIDs)
np.random.shuffle(totalIDs)
v1 = np.random.rand(len(totalIDs))
v2 = np.random.rand(len(totalIDs))

subsampleIDs = np.random.choice(totalIDs, M)
subsampleIDs = np.unique(subsampleIDs)
np.random.shuffle(subsampleIDs)

然后将数据转换为DataFrame：

import pandas as pd
df = pd.DataFrame(data = {"v1":v1, "v2":v2}, index=totalIDs) 
df.ix[subsampleIDs]

DataFrame使用散列表将索引映射到它的位置，它非常快。

通常，这种索引最好使用DB（使用适当的列索引）来执行。

另一个想法是将totalIDs排序一次，作为预处理阶段，并实现自己的in1d版本，避免排序所有内容。 in1d的numpy实现（至少在我安装的版本中）非常简单，应该很容易复制和修改。

编辑：

或者，更好的是，使用桶排序（或基数排序）。这应该给你O（N + M），N是totalIDs的大小，M是sampleIDs的大小（乘以一个你可以通过改变桶数来玩的常量）。在这里，你也可以将totalIDs拆分成只有一次的桶，这会给你一个漂亮的O（N + M1 + M2 + ...）。

不幸的是，我没有意识到一个粗糙的实现，但我确实发现：http://en.wikipedia.org/wiki/Radix_sort#Example_in_Python

链接地址: http://www.djcxy.com/p/69921.html

上一篇: doing better than numpy's in1d mask function: ordered arrays?

下一篇: Node.js and TeamCity