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)
1
MrGba2z 2016-04-22 03:32:51 +08:00 via iPhone
我怎么觉得是 log 的问题
|
2
ShiHou 2016-04-22 03:33:30 +08:00
我不太懂这函数是在干嘛.. 暂且理解为统计每一个字母的出现频率然后取 log 吧
大概能提供几个优化的思路,先试一下怎么插代码。 <script src="https://gist.github.com/Lyken17/5bffba48807fea6efd77.js"></script> |
3
SlipStupig OP @ShiHou 差不多就这个意思,数据量大了后就开始特别慢了,也就是 20 多万而已
|
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 |
5
ShiHou 2016-04-22 04:25:05 +08:00
因为在笔记本上跑,我的测试数据是 1w 左右。上面的结果都是在 1w 数据下测试出来的。
主要的瓶颈就是 count 这一步把算法从线性复杂度变成平方复杂度了,导致数据集一大直接爆炸。 built in 的函数虽然方便,但不要在大数据上乱用,很容易造成性能瓶颈。 简单的数值计算建议使用向量计算,复杂的操作可以考虑多线程。想再快一点可以考虑用 conda 的 jit 。 |
6
SlipStupig OP @ShiHou 这种运算下面多线程和 coroutine 并不能带来速度多少的优势
|
7
ShiHou 2016-04-22 06:55:58 +08:00 1
|
8
SlipStupig OP @ShiHou 感谢你的热心帮助,我测试了才知道主要速度卡在统计词频上面,跟多线程啥都没关系。后来想起来 python 本身就自带词频统计模块, collections,发现在最近记忆力下降了
代码就变成了 counter = [i for i in xrange(100000)] # 得到某一个词的词频就是 counter[words] # 变成了查 hash 了 实际测试速度:处理 30 万词,消耗 6 秒 |
9
calease 2016-04-22 08:13:52 +08:00 via iPhone
楼主为什么不试试用 cProfile 自己优化,随便配一个 visualizer 就行。
|
10
yepinf 2016-04-22 10:24:53 +08:00
数值运算,为何要使用脚本。。
|
11
SlipStupig OP |
12
yeyuexia 2016-04-22 16:54:29 +08:00
用 cmath 能快一些吧,主要瓶颈楼上也说了是算词频。
还有,@ShiHou 多线程快的前提是有 block 发生,没有 block 的话反而会慢。楼主这种情况要优化的话请选择多进程。 |
13
SlipStupig OP @yeyuexia numpy log 和 math 比较还没 math 快, 进程线程协程都没有什么用,用了反倒会变慢,毕竟不是 IO 密集型操作
|
14
yeyuexia 2016-04-22 17:18:38 +08:00
@SlipStupig 我说多进程的原因就是 python 的多线程只能利用一个 CPU
|
16
SlipStupig OP |
17
FlowMEMO 2016-04-22 17:43:46 +08:00
建议先 profiling 再进行优化,这样更有针对性
|
18
yeyuexia 2016-04-22 18:30:50 +08:00
@SlipStupig 我试了一下 cmath 确实没啥提升,反倒降了 orz 。话说我不理解你到底想要什么 @ShiHou 的代码之前没看,刚看了下感觉他已经写的很全了,优化效果也在上面,结果你说 numpy 没用,多进程没用。本来你给的代码就这么多我们还能怎么帮你优化呢? 要不换 c 代码?
|
19
SlipStupig OP @yeyuexia numpy log 没啥用,但是用矩阵计算性能优化很大,这个不是 c 和 Python 的问题是算法复杂度的问题
|
20
yeyuexia 2016-04-22 18:43:01 +08:00
@SlipStupig 关于矩阵计算我倒是希望能求教下。顺便楼主我希望你能在确认一下我们之前是不是上下文一致……
|
21
Allianzcortex 2016-04-22 19:15:23 +08:00
计算密集型开多线程的作用不大呀。用 numpy
|
22
billlee 2016-04-22 20:53:13 +08:00
@SlipStupig 这个就是 C 和 python 的问题,楼主这个算法用矩阵算和手写是一样的, numpy 快就是因为它内部的循环是用 C/Fortran 实现。
|
23
ShiHou 2016-04-23 02:57:09 +08:00
@SlipStupig 233 你说得对. 我本来是想表达多进程的,结果糊涂达成多线程了。 Python 有 GIL 锁导致计算密集时多进程没用。
@SlipStupig 用 Numpy 把所有的词频做成矩阵,对矩阵一次性求 log 比循环过去 log 快很多。 矩阵快的原因有两个,一是底层用 c 写,循环比脚本语言快。二是矩阵的内置操作基本都做了优化,比如 N^2.73 复杂度的矩阵乘。 |
25
SlipStupig OP @ShiHou GIL 是全局解释锁,会导致多线程没用,进程之间是没有隔离的
|