首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python 学习手册
Python Cookbook
Python 基础教程
Python Sites
PyPI - Python Package Index
http://www.simple-is-better.com/
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
V2EX  ›  Python

问一个 numpy pandas 相关的问题

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

    我有两个矩阵
    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
        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.函数选的不好可能就会误报……直接选取的想法也有,不过现在手边没电脑没法验证……中午回去了试试
        2
    imn1   2017-05-22 08:49:49 +08:00   ♥ 1
    大也是内存问题
    你这个需求是整行相同,实际上就是一维,用列表表达式 in 就可以了
    df 格式的话,用 df.isin
        3
    guolingbing   2017-05-22 08:53:06 +08:00 via Android
    @EmdeBoas 其实我想做的是 用 numpy 或者 pandas 的矩阵方法直接选取相交的向量,如果要遍历的话其实 numpy 内置了比较方法,不用哈希也行,直接
    for v in b:
    if v in a :

    就可以了
        4
    guolingbing   2017-05-22 08:57:14 +08:00 via Android
    @imn1 感谢,我马上去试试,isin 好像可行
        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]
        6
    guolingbing   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
        7
    khowarizmi   2017-05-22 14:20:34 +08:00
    @guolingbing 在 stackoverflow 上的方法 ```np.in1d``` 用的就是嵌套遍历 a, b 两个数组,算法复杂度在 O(nm),数据量上去会有问题。
        8
    guolingbing   2017-05-22 15:00:50 +08:00
    @khowarizmi 实际上 np.in1d 我用起来很快的,要比遍历快的多,我现在用答案上提供的 in2d 的方法,大概两个 50W 的向量几秒就完成了,我估计是 numpy 和 pandas 会自动 hash
        9
    khowarizmi   2017-05-22 15:31:26 +08:00
    @guolingbing 刚才我源码看了一半,说法不是很准确。正确的应该是,当两个数组长度相当的时候,np.in1d 用的是 merge sort 所以速度应该已经是较快的了。只有在一个数组较短的时候 np.in1d 才使用了嵌套遍历(它说这种情况下嵌套遍历会相当快)。所以这里你使用的那个方法速度确实已经足够了。
        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)) 。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   949 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 19ms · UTC 22:24 · PVG 06:24 · LAX 15:24 · JFK 18:24
    ♥ Do have faith in what you're doing.