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
SlipStupig
V2EX  ›  Python

关于 python 除法效率问题

  •  
  •   SlipStupig · 2016-04-22 03:06:58 +08:00 · 4614 次点击
    这是一个创建于 3127 天前的主题,其中的信息可能已经有所发展或是发生改变。

    做一个除法计算发现速度出奇的慢有什么办法提高呢?

    以下是我代码的一个 demo

    
    import string
    import random
    from math import log
    
    wordlist = [i for i in xrange(100000)]
    
    def calc(words):
        log(wordlist.count(words)/len(wordlist)) +1) * (wordlist)
    
    map(clac, wordlist)
    
    
    25 条回复    2016-04-23 11:24:42 +08:00
    MrGba2z
        1
    MrGba2z  
       2016-04-22 03:32:51 +08:00 via iPhone
    我怎么觉得是 log 的问题
    ShiHou
        2
    ShiHou  
       2016-04-22 03:33:30 +08:00
    我不太懂这函数是在干嘛.. 暂且理解为统计每一个字母的出现频率然后取 log 吧

    大概能提供几个优化的思路,先试一下怎么插代码。

    <script src="https://gist.github.com/Lyken17/5bffba48807fea6efd77.js"></script>
    SlipStupig
        3
    SlipStupig  
    OP
       2016-04-22 04:02:09 +08:00
    @ShiHou 差不多就这个意思,数据量大了后就开始特别慢了,也就是 20 多万而已
    ShiHou
        4
    ShiHou  
       2016-04-22 04:21:23 +08:00   ❤️ 5
    初来乍到不会贴代码, 具体实现看我的 notebook 吧
    https://github.com/Lyken17/TempJupyterNotebook/blob/master/Untitled.ipynb

    首先, len(worldlist)在每次函数里面是要单独取地计算的,可以用变量代替避免每次反复读取。
    时间: 1.75 s per loop -> 1.69 s per loop

    第二,操作时间主要花在了 count 和 log 上,调用内置 count 会把所有数组遍历一遍统计,相当于共进行了 O(N^2)次操作,可以用一次循环统计完搞定。(这一步是主要的优化)
    时间: 1.69 s per loop -> 3.67 ms per loop

    第三, map 的操作是可以用多线程来优化的。 p=Pool(4), p.map 就可以实现并行了。但由于优化过后的结果已经很好,小规模数据集时看不出太大区别。
    时间: 3.6 ms per loop -> 2.51 ms per loop

    第四,你的 map 操作是简单的数值计算。所以可以考虑把计算向量化,利用 Numpy 来操作。 Numpy 是 c-wrapper + 多核优化,速度比原生 python 要快。
    时间: 2.51 ms per loop -> 1.43 ms per loop
    ShiHou
        5
    ShiHou  
       2016-04-22 04:25:05 +08:00
    因为在笔记本上跑,我的测试数据是 1w 左右。上面的结果都是在 1w 数据下测试出来的。

    主要的瓶颈就是 count 这一步把算法从线性复杂度变成平方复杂度了,导致数据集一大直接爆炸。 built in 的函数虽然方便,但不要在大数据上乱用,很容易造成性能瓶颈。

    简单的数值计算建议使用向量计算,复杂的操作可以考虑多线程。想再快一点可以考虑用 conda 的 jit 。
    SlipStupig
        6
    SlipStupig  
    OP
       2016-04-22 06:45:39 +08:00
    @ShiHou 这种运算下面多线程和 coroutine 并不能带来速度多少的优势
    ShiHou
        7
    ShiHou  
       2016-04-22 06:55:58 +08:00   ❤️ 1
    @SlipStupig 能带来优势的,把数据规模继续放大,或是将操作变复杂, N 线程就能带来 N 倍的提速。

    不过这里用线程池主要是为了方便改写成分布式,之前处理 NLP 留下的个人习惯。
    SlipStupig
        8
    SlipStupig  
    OP
       2016-04-22 08:10:36 +08:00
    @ShiHou 感谢你的热心帮助,我测试了才知道主要速度卡在统计词频上面,跟多线程啥都没关系。后来想起来 python 本身就自带词频统计模块, collections,发现在最近记忆力下降了
    代码就变成了
    counter = [i for i in xrange(100000)]
    # 得到某一个词的词频就是
    counter[words] # 变成了查 hash 了
    实际测试速度:处理 30 万词,消耗 6 秒
    calease
        9
    calease  
       2016-04-22 08:13:52 +08:00 via iPhone
    楼主为什么不试试用 cProfile 自己优化,随便配一个 visualizer 就行。
    yepinf
        10
    yepinf  
       2016-04-22 10:24:53 +08:00
    数值运算,为何要使用脚本。。
    SlipStupig
        11
    SlipStupig  
    OP
       2016-04-22 13:42:54 +08:00
    @calease 我肯定测试过的啊,
    @yepinf 用 c++也不一定比我快啊
    yeyuexia
        12
    yeyuexia  
       2016-04-22 16:54:29 +08:00
    用 cmath 能快一些吧,主要瓶颈楼上也说了是算词频。
    还有,@ShiHou 多线程快的前提是有 block 发生,没有 block 的话反而会慢。楼主这种情况要优化的话请选择多进程。
    SlipStupig
        13
    SlipStupig  
    OP
       2016-04-22 17:10:15 +08:00
    @yeyuexia numpy log 和 math 比较还没 math 快, 进程线程协程都没有什么用,用了反倒会变慢,毕竟不是 IO 密集型操作
    yeyuexia
        14
    yeyuexia  
       2016-04-22 17:18:38 +08:00
    @SlipStupig 我说多进程的原因就是 python 的多线程只能利用一个 CPU
    Zzzzzzzzz
        15
    Zzzzzzzzz  
       2016-04-22 17:24:30 +08:00
    你们白争了, 虽然 @ShiHou 说的是用多线程, 但他贴的代码里用的是多进程.
    SlipStupig
        16
    SlipStupig  
    OP
       2016-04-22 17:33:42 +08:00
    @Zzzzzzzzz @yeyuexia 我早看到了啊,这些都没什么用,多核计算并不能提高这块的计算速度来到多大的性能提升, cmath 和 math 比较好像并没有多大个区别
    FlowMEMO
        17
    FlowMEMO  
       2016-04-22 17:43:46 +08:00
    建议先 profiling 再进行优化,这样更有针对性
    yeyuexia
        18
    yeyuexia  
       2016-04-22 18:30:50 +08:00
    @SlipStupig 我试了一下 cmath 确实没啥提升,反倒降了 orz 。话说我不理解你到底想要什么 @ShiHou 的代码之前没看,刚看了下感觉他已经写的很全了,优化效果也在上面,结果你说 numpy 没用,多进程没用。本来你给的代码就这么多我们还能怎么帮你优化呢? 要不换 c 代码?
    SlipStupig
        19
    SlipStupig  
    OP
       2016-04-22 18:32:27 +08:00
    @yeyuexia numpy log 没啥用,但是用矩阵计算性能优化很大,这个不是 c 和 Python 的问题是算法复杂度的问题
    yeyuexia
        20
    yeyuexia  
       2016-04-22 18:43:01 +08:00
    @SlipStupig 关于矩阵计算我倒是希望能求教下。顺便楼主我希望你能在确认一下我们之前是不是上下文一致……
    Allianzcortex
        21
    Allianzcortex  
       2016-04-22 19:15:23 +08:00
    计算密集型开多线程的作用不大呀。用 numpy
    billlee
        22
    billlee  
       2016-04-22 20:53:13 +08:00
    @SlipStupig 这个就是 C 和 python 的问题,楼主这个算法用矩阵算和手写是一样的, numpy 快就是因为它内部的循环是用 C/Fortran 实现。
    ShiHou
        23
    ShiHou  
       2016-04-23 02:57:09 +08:00
    @SlipStupig 233 你说得对. 我本来是想表达多进程的,结果糊涂达成多线程了。 Python 有 GIL 锁导致计算密集时多进程没用。

    @SlipStupig 用 Numpy 把所有的词频做成矩阵,对矩阵一次性求 log 比循环过去 log 快很多。 矩阵快的原因有两个,一是底层用 c 写,循环比脚本语言快。二是矩阵的内置操作基本都做了优化,比如 N^2.73 复杂度的矩阵乘。
    ShiHou
        24
    ShiHou  
       2016-04-23 02:57:51 +08:00
    @ShiHou s/多进程没用 /多线程没用... 这两个词太像了 我下次还是说 process 和 thread 吧
    SlipStupig
        25
    SlipStupig  
    OP
       2016-04-23 11:24:42 +08:00
    @ShiHou GIL 是全局解释锁,会导致多线程没用,进程之间是没有隔离的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1044 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 19:47 · PVG 03:47 · LAX 11:47 · JFK 14:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.