问一个 numpy pandas 相关的问题

[guolingbing]

求大佬们指教

我有两个矩阵
a = [[1,3,4],[2,5,3],[2,4,6],[6,5,3]]
b = [[2,4,5],[2,4,6],[1,3,4]]

a 和 b 长度不等，但里面的向量维数都是 3，
我现在有一个需求：
找出 b 中 a 包含的向量，也就是[2,4,6][1,3,4]，修改这些向量，直到 b 中不含有 a 包含的向量

现在的问题是 a 和 b 都很大，如果用遍历的方法一个一个判断效率比较低，各位大佬有没有什么好办法，直接可以选取 b 中 a 包含的向量的方法呢？

[EmdeBoas]

不直接选取可以考虑这样做:用一个乘数 hash 把 a 映射到一个 set 里面，比如 hash(x)=3x[0]+33x[1]+333x[2],然后去同样遍历 b，放不进 set 就说明存在了，按 index 去掉就好了，复杂度是 n，不过这样做 hash.函数选的不好可能就会误报……直接选取的想法也有，不过现在手边没电脑没法验证……中午回去了试试

[imn1]

大也是内存问题
你这个需求是整行相同，实际上就是一维，用列表表达式 in 就可以了
df 格式的话，用 df.isin

[guolingbing]

@EmdeBoas 其实我想做的是 用 numpy 或者 pandas 的矩阵方法直接选取相交的向量，如果要遍历的话其实 numpy 内置了比较方法，不用哈希也行，直接
for v in b:
if v in a :

就可以了

[guolingbing]

@imn1 感谢，我马上去试试，isin 好像可行

[princelai]

我自己随便写了个，思路就是 hash 值变为 index，然后用 pandas 的 index 对齐

import pandas as pd
import random
import itertools

a3 = pd.Series(random.sample(list(itertools.permutations(range(10),3)),100))
a = a3.apply(lambda x:list(x))
a.index = [hash(tuple(i)) for i in a.values]
a= pd.DataFrame(a)
a.columns = ['value_a']
a['idx_a'] = range(len(a))

b3 = pd.Series(random.sample(list(itertools.combinations(range(10),3)),50))
b = b3.apply(lambda x:list(x))
b.index = [hash(tuple(i)) for i in b.values]
b= pd.DataFrame(b)
b.columns = ['value_b']
b['idx_b'] = range(len(b))

b.iloc[pd.concat([a,b],axis=1,join='inner').idx_b.values]

[guolingbing]

@princelai 赞，我同时也在 stackoverflow 上问了这个问题，感觉这个方法更简洁，我之前也是想到先把一个向量转换为 tuple，这样就能 hash 了，但操作有些复杂
http://stackoverflow.com/questions/44103188/how-can-i-select-one-matrix-vectors-which-in-another-matrix

[khowarizmi]

@guolingbing 在 stackoverflow 上的方法 ```np.in1d``` 用的就是嵌套遍历 a, b 两个数组，算法复杂度在 O(nm)，数据量上去会有问题。

[guolingbing]

@khowarizmi 实际上 np.in1d 我用起来很快的，要比遍历快的多，我现在用答案上提供的 in2d 的方法，大概两个 50W 的向量几秒就完成了,我估计是 numpy 和 pandas 会自动 hash

[khowarizmi]

@guolingbing 刚才我源码看了一半，说法不是很准确。正确的应该是，当两个数组长度相当的时候，np.in1d 用的是 merge sort 所以速度应该已经是较快的了。只有在一个数组较短的时候 np.in1d 才使用了嵌套遍历（它说这种情况下嵌套遍历会相当快）。所以这里你使用的那个方法速度确实已经足够了。

[khowarizmi]

@guolingbing 但我还是觉得 np.in1d 是帮你把复杂度从 O(nm) 降到 O((n+m)log(n+m)), 使用用 hash 应该能更快，因为复杂度理论上只有 O(max(n, m)) 。