关于 python 除法效率问题


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)

wordlist

import

除法

25 条回复 • 2016-04-23 11:24:42 +08:00

MrGba2z

2016-04-22 03:32:51 +08:00 via iPhone

我怎么觉得是 log 的问题

ShiHou

2016-04-22 03:33:30 +08:00

我不太懂这函数是在干嘛.. 暂且理解为统计每一个字母的出现频率然后取 log 吧

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

<script src="https://gist.github.com/Lyken17/5bffba48807fea6efd77.js"></script>

SlipStupig

2016-04-22 04:02:09 +08:00

@ShiHou 差不多就这个意思，数据量大了后就开始特别慢了，也就是 20 多万而已

ShiHou

2016-04-22 04:21:23 +08:00

初来乍到不会贴代码，具体实现看我的 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

2016-04-22 04:25:05 +08:00

因为在笔记本上跑，我的测试数据是 1w 左右。上面的结果都是在 1w 数据下测试出来的。

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

简单的数值计算建议使用向量计算，复杂的操作可以考虑多线程。想再快一点可以考虑用 conda 的 jit 。

SlipStupig

2016-04-22 06:45:39 +08:00

@ShiHou 这种运算下面多线程和 coroutine 并不能带来速度多少的优势

ShiHou

2016-04-22 06:55:58 +08:00

@SlipStupig 能带来优势的，把数据规模继续放大，或是将操作变复杂， N 线程就能带来 N 倍的提速。

不过这里用线程池主要是为了方便改写成分布式，之前处理 NLP 留下的个人习惯。

SlipStupig

2016-04-22 08:10:36 +08:00

@ShiHou 感谢你的热心帮助，我测试了才知道主要速度卡在统计词频上面，跟多线程啥都没关系。后来想起来 python 本身就自带词频统计模块, collections,发现在最近记忆力下降了
代码就变成了
counter = [i for i in xrange(100000)]
# 得到某一个词的词频就是
counter[words] # 变成了查 hash 了
实际测试速度：处理 30 万词，消耗 6 秒

calease

2016-04-22 08:13:52 +08:00 via iPhone

楼主为什么不试试用 cProfile 自己优化，随便配一个 visualizer 就行。

yepinf

2016-04-22 10:24:53 +08:00

数值运算，为何要使用脚本。。

SlipStupig

2016-04-22 13:42:54 +08:00

@calease 我肯定测试过的啊，
@yepinf 用 c++也不一定比我快啊

yeyuexia

2016-04-22 16:54:29 +08:00

用 cmath 能快一些吧，主要瓶颈楼上也说了是算词频。
还有，@ShiHou 多线程快的前提是有 block 发生，没有 block 的话反而会慢。楼主这种情况要优化的话请选择多进程。

SlipStupig

2016-04-22 17:10:15 +08:00

@yeyuexia numpy log 和 math 比较还没 math 快, 进程线程协程都没有什么用，用了反倒会变慢，毕竟不是 IO 密集型操作

yeyuexia

2016-04-22 17:18:38 +08:00

@SlipStupig 我说多进程的原因就是 python 的多线程只能利用一个 CPU

Zzzzzzzzz

2016-04-22 17:24:30 +08:00

你们白争了, 虽然 @ShiHou 说的是用多线程, 但他贴的代码里用的是多进程.

SlipStupig

2016-04-22 17:33:42 +08:00

@Zzzzzzzzz @yeyuexia 我早看到了啊，这些都没什么用，多核计算并不能提高这块的计算速度来到多大的性能提升， cmath 和 math 比较好像并没有多大个区别

FlowMEMO

2016-04-22 17:43:46 +08:00

建议先 profiling 再进行优化，这样更有针对性

yeyuexia

2016-04-22 18:30:50 +08:00

@SlipStupig 我试了一下 cmath 确实没啥提升，反倒降了 orz 。话说我不理解你到底想要什么 @ShiHou 的代码之前没看，刚看了下感觉他已经写的很全了，优化效果也在上面，结果你说 numpy 没用，多进程没用。本来你给的代码就这么多我们还能怎么帮你优化呢？要不换 c 代码？

SlipStupig

2016-04-22 18:32:27 +08:00

@yeyuexia numpy log 没啥用，但是用矩阵计算性能优化很大，这个不是 c 和 Python 的问题是算法复杂度的问题

yeyuexia

2016-04-22 18:43:01 +08:00

@SlipStupig 关于矩阵计算我倒是希望能求教下。顺便楼主我希望你能在确认一下我们之前是不是上下文一致……

Allianzcortex

2016-04-22 19:15:23 +08:00

计算密集型开多线程的作用不大呀。用 numpy

billlee

2016-04-22 20:53:13 +08:00

@SlipStupig 这个就是 C 和 python 的问题，楼主这个算法用矩阵算和手写是一样的， numpy 快就是因为它内部的循环是用 C/Fortran 实现。

ShiHou

2016-04-23 02:57:09 +08:00

@SlipStupig 233 你说得对. 我本来是想表达多进程的，结果糊涂达成多线程了。 Python 有 GIL 锁导致计算密集时多进程没用。

@SlipStupig 用 Numpy 把所有的词频做成矩阵，对矩阵一次性求 log 比循环过去 log 快很多。矩阵快的原因有两个，一是底层用 c 写，循环比脚本语言快。二是矩阵的内置操作基本都做了优化，比如 N^2.73 复杂度的矩阵乘。

ShiHou

2016-04-23 02:57:51 +08:00

@ShiHou s/多进程没用 /多线程没用... 这两个词太像了我下次还是说 process 和 thread 吧

SlipStupig

2016-04-23 11:24:42 +08:00

@ShiHou GIL 是全局解释锁，会导致多线程没用，进程之间是没有隔离的