Python 处理文件的性能优化

知乎的面试题..?

把topics存set里面，再用in

@czheo python的set做iteration比list慢啊。
这么大的数量，而且彼此之间没有相关性，用并行方式来做有很好的通用性。

猜测: topics = [topic0, topic1, ... topicn],topic = 'aaa bbb ccc ... zzz'
几个点:
1. 慢主要是文件读取?
2. topics本身还是比较复杂，是不是再预处理一下会比较好?
3. 为什么要把tweet再次打散才进行比较？直接用类似string.contain之类的方法是否可以?
4. 这种对比和统计，是不是可以用dict来做会比较快？

1. topic 放 set，线性查找
2. topics 分片，并行处理

其实 in set（1500）的话几乎没什么时间开销，就是 IO 的速度了，所以分片不见得有什么好的效果

感觉是CPU瓶颈，不知道Python字符串比较效率如何

@eriale 已经实现过Hadoop版本了，现在需要跑单机的版本

我觉得搜索一条微博有没有包含"1500个topic"之一是不是转成正则表达式来匹配会更快一些?
觉得搜索1500次应该很慢

另外读文件如果能一次读多行(如1000行),减少IO操作的次数会不会快一些

另外如果能利用到多核的话肯定会更好一些,所以可以看有几核,就起几个进程分别做肯定能更快的

@leiz
1.topic大部分是一个中文单词，有一部分是几个单词的组合，比如说：“爸爸去哪儿 多多”。
2.没有把tweet打散啊。还是一条一条的比较。试过string的方法，速度好像更慢。
3.嗯，dict查找应该会比list快点。但是这里仅仅是使用了in操作，你的意思是说，把每个tweet都拆分存到dict里面？

@clino
1.用正则速度应该会更慢。
2.嗯，有道理。原来文件小的时候，用readlines一次全部读完，速度会快点。我试试分块的效率怎么样

这个排版有问题，看不到缩进。建议你把所有缩进的空格都换成"."

如果我没猜错你用了三层for循环，100,000,000 * 1500 * n（n是啥我还没看懂）。至少在我的工作里极少用到>=3的for循环，用到了基本就是代码写得有问题了。

你把代码重排个版我再看看

@wwttc 你可以试试,只要每次使用正则预编译好的对象,我猜测会比循环搜索更快
因为正则预编译以后,有点相当于搜索的规则给索引了

如果这是一道题目，考的一定是算法。。。

你大概需要一个高级数据结构来支撑这个需求。各种空间换时间。

绝非暴力能过的。。

f = file("largefile")
....for line in f:
........try:
............tweet_time = line.split(',',3)[2].split()[0] # 微博发布时间
............tweet = line.split(',',3)[-1] # 微博内容
............for topic in topics:
................topic_items = topic.split() # 每个topic可能有多个词组成
................isCOntain= True
................for item in topic_items:
....................if item not in tweet:
........................isCOntain= False
........................break
....................if isContain:
........................pass # 该微博包含该topic
........except:
............continue
f.close()

首先，topic是固定的，没理由在循环内每次拆解，移到循环外面
这种多对多简单in比较，我会考虑用pandas或者sql

这么简单的查找为什么不直接用grep...

你先看看这样行不行。可能有语法错误，没测试
with file("largefile") as f:
....topic_items_list = [t.split() for t in topics] # 每个topic可能有多个词组成
....for line in f:
........tweet_time = line.split(',',3)[2].split()[0] # 微博发布时间
........tweet = line.split(',',3)[-1] # 微博内容
........for topic_items in topic_items_list:
............if all(item in tweet for item in topic_items):
................pass # do sth

@captainhcg
我最早也是用all函数，测试了下发现速度要比现在的慢。

@yangqi
grep是快多了，但是我这边由于某种原因要求是用Python来做

@imn1
topic必须要拆的啊。比如说topic为“爸爸去哪儿 多多”，然后一条微博是“爸爸去哪儿节目中的多多”，这样如果不拆就统计不出来这条微博了

@takato
其实也不是题目，是自己需要处理数据和Hadoop进行对比

另外一点很重要，推特是中文的还是英文的。中文的用 in 就可以（分词先不讨论），英文务必用正则的 \b （否则java和Javascript就会混淆）。这一题推荐用正则，但我不认为在这里用正则和用all有本质区别。

@wwttc 没说不拆啊
你在外面拆啊，干嘛for微博信息每行拆一次，那不重复执行上亿次么？

我觉得这是个建立倒排索引的过程 你可以查查相关的资料
你的处理过程的时间复杂度是O(nml) n是文件数 m是topics 数 l是文件的平均长度
你可以试试怎么把m 去掉或者l去掉

@imn1 哦~明白了

@captainhcg 中文的

@sleeperqp 虽然对倒排索引不是很了解,但我想如果用倒排索引这种是不是就要先分词?

突然想到两种方法：
一种是直接对源文本建立倒排索引，然后对这些索引最后与topics求交
另外一种是对元文本建立倒排索引的过程中，用hash之类的判断在不在topics里
这样就可以去掉m

@wwttc
topics是固定的吧？

为什么要放在第一个for里面？

topics分片成topic的语句放for外面，做成set，可能会好一点

@clino 后面看到是中文，如果这样我觉得分词还是有必要的 就算纯文本匹配也是有误差的
所以我觉得还是先分词下然后再做处理比较好~

@wwttc 还有，用表达式或map套函数要比for快不是一般的多，尤其适合这种各项无关联的列表

也许你可以试试把文件切成几片
然后使用 multiprocessing.Pool 里面带的 map

from multiprocessing import Pool
pool = Pool()
pool.map(func, iter) #just like map

................isCOntain= True
................for item in topic_items:
....................if item not in tweet:
........................isCOntain= False
........................break
....................if isContain:

楼主你这段代码是不是有点问题？最后一个if的缩进是不是多了？

@shoumu 嗯，是啊。多缩进了。。。

我觉得大的数量级上优化空间不多，只好改进下常数时间了

* 不要 split 多次
* item 按照出现概率排序
* 先对 tweet 进行单字过滤（如果 topic 中的某个单字不存在，就不会匹配了）
* 用 topic 建词表，用这个词表对 tweet 切词，倒排或者怎么地都行

但是，这些改进都是 一亿 * (1500 * n) 后面这部分的效率。
它取决于 topic 平均长度，重复单词概率等特征。

1，把topic放在循环外拆开，必须的。
2，把这1亿条微博数据拆成10或是100个文件，放到不同机器上，再开多线程。
3，把微博的数据读到内容放到内存里，成为hash的键值，全部读完再来做比较。

空间换时间，简单暴力。

@wwttc 数据放出来 需求放出来 做成一个测试题吧。就叫大家一起来优化. :D

为什么不用github gist?

在不使用hash的前提下, 对所有topic item建立AC自动机. 然后针对每条微博在AC自动机上做多串匹配, 其时间复杂度渐进上界为O(n+km), 其中n是所有微博的字符总数, k是微博条数(即一亿), m是所有topic的字符总数.

抱歉, #40 的时间复杂度写错了, 应该是O(n+m+z), 其中n是所有微博的字符总数, m是所有topic的字符总数, z是topic item命中次数.

这个问题我在曹政博客上看到过相似的，后来一搜，知乎上貌似有人给过一些思路。

==============================
曹政@caoz 的开发工程师招聘问题三：如何实现一个快速有效的，基于自定义词典精确匹配的分词系统？修改

一个典型问题，目前政府有屏蔽词表，每个网站都要遵守，发帖的时候会自动替换屏蔽词；另一个场景是诸如新浪新闻等媒体往往有商业词表，发新闻的时候会自动建立关键词铆接。这个相当于一个简单的基于词典的分词系统，下面的问题就是，如何实现一个快速有效的，基于自定义词典精确匹配的分词系统，一是要满足每天几万篇，几十万篇文章发布的要求；另一个必须的要求是，当词库倍增扩展时（比如10万词），效率的影响不允许是线性降低的。

answer1
==============================
这个有很多办法，其实跟分词不一样，就是一个字符串匹配问题。
方法1，双哈希：
有2个哈希表，第一个是缩小范围的判定哈希，第二个是不同字数屏蔽词的哈希表。
每当我们读到一个字，就到第一个表里取一下，可以得到以这个字开头的屏蔽词的长度分别有哪些，比如(2，3，5)。然后分别从这个字开始，分2，3，5个字的词，去查第二个哈希表，查到了则返回危险，否则继续判定下一个字。
复杂度：O(L*n)，L为以每个字开头的词长度的平均个数，n为输入流长度。（真绕）

方法2，有限自动机：
有限自动机说白了就是手工展开的正则表达式，把词表综合成一个巨大的有限自动机，每输入一个字就到自动机里查表，跳转状态，到匹配状态则为危险句子，到结束符则不危险。
时间复杂度：O(n)
空间复杂度：不可估计，可能会很大
方法3，一些其它字符串匹配算法的变形：
具体没细想，类似kmp，rk，bm的变形或许也能解决这个问题。


总之，最笨的方法是前向最大匹配，复杂度O(m*max(L))，其中max(L)为最长屏蔽词的长度。
一个好的匹配算法可以减少L的长度，检测并跳过没必要的计算。


answer2
==============================

由于敏感词范围有限，可以按字节将所有词分成N段。每字节共256种可能，维护一棵trie树，节点为256个指针。每个指针标识一字节，（比如第3个指针表示0x03这个字符）。所以一个M个字节的词被切成M份，为trie树中从根节点到第M层的一条链路。将所有待过滤词全部输入后，就能形成一棵查询trie树。其中敏感词对应的路径为通的，并且最后一个是页节点（比如abcde是敏感词，那么第5层的e对应的指针就是空的）。如果非敏感词，则无此通路或者有此通路但还有后续节点。

比如abcde是敏感词，abcdf不是
abcdf***是一个待过滤的字符串，在前四个字节匹配后，在第四层的f对应那个指针就为空。匹配失败
abc对应的c节点还有后续节点，那么abc也就不在敏感词中

在查询时，通过将文章按字节在trie树中进行查找，如果能一直有路径到叶节点，那么目前这条从根节点到叶节点的路径就是第三词。

如果不是，很明显我们需要将文章向后移一位再做对比。这样其实复杂度非常高。

解决这个问题可以引入KMP算法并将其扩展，将每个节点在匹配失败后，文章的下一字节应该到哪个节点重新开始匹配计算出来，将文章下一字节直接与这个节点进行匹配，这样每次文章只需要遍历一次。复杂度为O(n)，n为文章长度。

至于空间复杂度，最坏的情况下，当所有敏感词链路没有交集时，由于使用trie树结构，整个数据会膨胀(256+256)＊4 = 2048 倍，两个256分别表示一个节点中的两套指针（子节点指针与KMP需要的指针），4表示一个字节变成了4个字节（如果是32位机器的话）。 当然，如果将所有节点在一个数组下分配的话，就不需要存指针了，存数组位置即可。数据小数组可以2^16长，这时就变成2字节了，数据大2^32个节点差不多也够了吧。而且在64位机下也一样。

所以10w级别的词，按每个词平均10字节算，一共1M，最坏情况下需要2G内存实现。


http://www.zhihu.com/question/19918081

主要是 大文件切成小文件，整成多线程，还有就是readlines(size)，size看内存大小 吧～

楼主后来结果如何?什么方法有效?