V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
guolingbing
V2EX  ›  Python

问一个 numpy pandas 相关的问题

  •  
  •   guolingbing · 2017-05-22 08:16:57 +08:00 via Android · 2300 次点击
    这是一个创建于 2503 天前的主题,其中的信息可能已经有所发展或是发生改变。
    求大佬们指教

    我有两个矩阵
    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 包含的向量的方法呢?
    10 条回复    2017-05-22 15:41:11 +08:00
    EmdeBoas
        1
    EmdeBoas  
       2017-05-22 08:48:13 +08:00 via Android   ❤️ 1
    不直接选取可以考虑这样做:用一个乘数 hash 把 a 映射到一个 set 里面,比如 hash(x)=3x[0]+33x[1]+333x[2],然后去同样遍历 b,放不进 set 就说明存在了,按 index 去掉就好了,复杂度是 n,不过这样做 hash.函数选的不好可能就会误报……直接选取的想法也有,不过现在手边没电脑没法验证……中午回去了试试
    imn1
        2
    imn1  
       2017-05-22 08:49:49 +08:00   ❤️ 1
    大也是内存问题
    你这个需求是整行相同,实际上就是一维,用列表表达式 in 就可以了
    df 格式的话,用 df.isin
    guolingbing
        3
    guolingbing  
    OP
       2017-05-22 08:53:06 +08:00 via Android
    @EmdeBoas 其实我想做的是 用 numpy 或者 pandas 的矩阵方法直接选取相交的向量,如果要遍历的话其实 numpy 内置了比较方法,不用哈希也行,直接
    for v in b:
    if v in a :

    就可以了
    guolingbing
        4
    guolingbing  
    OP
       2017-05-22 08:57:14 +08:00 via Android
    @imn1 感谢,我马上去试试,isin 好像可行
    princelai
        5
    princelai  
       2017-05-22 12:14:05 +08:00   ❤️ 1
    我自己随便写了个,思路就是 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
        6
    guolingbing  
    OP
       2017-05-22 13:21:56 +08:00
    @princelai 赞,我同时也在 stackoverflow 上问了这个问题,感觉这个方法更简洁,我之前也是想到先把一个向量转换为 tuple,这样就能 hash 了,但操作有些复杂
    http://stackoverflow.com/questions/44103188/how-can-i-select-one-matrix-vectors-which-in-another-matrix
    khowarizmi
        7
    khowarizmi  
       2017-05-22 14:20:34 +08:00
    @guolingbing 在 stackoverflow 上的方法 ```np.in1d``` 用的就是嵌套遍历 a, b 两个数组,算法复杂度在 O(nm),数据量上去会有问题。
    guolingbing
        8
    guolingbing  
    OP
       2017-05-22 15:00:50 +08:00
    @khowarizmi 实际上 np.in1d 我用起来很快的,要比遍历快的多,我现在用答案上提供的 in2d 的方法,大概两个 50W 的向量几秒就完成了,我估计是 numpy 和 pandas 会自动 hash
    khowarizmi
        9
    khowarizmi  
       2017-05-22 15:31:26 +08:00
    @guolingbing 刚才我源码看了一半,说法不是很准确。正确的应该是,当两个数组长度相当的时候,np.in1d 用的是 merge sort 所以速度应该已经是较快的了。只有在一个数组较短的时候 np.in1d 才使用了嵌套遍历(它说这种情况下嵌套遍历会相当快)。所以这里你使用的那个方法速度确实已经足够了。
    khowarizmi
        10
    khowarizmi  
       2017-05-22 15:41:11 +08:00
    @guolingbing 但我还是觉得 np.in1d 是帮你把复杂度从 O(nm) 降到 O((n+m)log(n+m)), 使用用 hash 应该能更快,因为复杂度理论上只有 O(max(n, m)) 。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3624 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 05:01 · PVG 13:01 · LAX 22:01 · JFK 01:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.