推荐学习书目
› 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
这是一个创建于 2003 天前的主题，其中的信息可能已经有所发展或是发生改变。
有一个长度为 50 万的字符串列表，现在要查找某个字符串是不是这些字符串的字串，找到所有符合的字符串. 我用 python 遍历实现了一遍，性能不太满足，各位有没有什么建议？
 |
1
kirigaya 2019-06-04 13:59:27 +08:00
动态规划里的字符串查找？
|
 |
2
goreliu 2019-06-04 14:02:03 +08:00 via Android
可以用 c 实现试试，如果性能还不行的话再用 kmp 优化下。直接在 python 优化可能效果不佳。
|
 |
3
VDimos 2019-06-04 14:11:19 +08:00 via Android
你代码呢？
|
 |
4
pmispig 2019-06-04 14:17:00 +08:00
你肯定用的单线程姿势吧，这个可以优化成多线程的
|
 |
5
geelaw 2019-06-04 14:17:47 +08:00
字串 => 子串？
首先选择一个不出现在任何字符串里的一个字符 c，例如 c 选择 \0，然后把所有字符串接在一起 S = s1 \0 s2 \0 ... \0 sn，接着制作 S 的后缀树（线性时间），然后就可以很容易做你需要的事情了。 具体实现上，你不需要真的构造出 S 这个字符串，在制作后缀树的过程中可以 virtually 表示它。 |
 |
6
hmzt 2019-06-04 14:20:25 +08:00
正则,应该比你自己写的快
|
 |
7
testeststs 2019-06-04 14:23:52 +08:00
python 能没有现成的轮子？我不信。
没做过这么长的字符串，大概需要多少时间？ |
 |
8
dongyx 2019-06-04 17:27:35 +08:00
不放设列表里有 n 个字符串，每个串长为 m。不管怎么做，第一次匹配都逃不了 O(nm)的时间复杂度。
如果你就匹配一次，直接用 KMP 挨个匹配就好，O(nm)。 如果你有多个模式串，要匹配多次，建议先把 n 个文本串建成一颗 Trie 树，建树的时间是 O(nm)，以后每次匹配的时间只需要 O(m)。 |
|
9
dongyx 2019-06-04 17:31:40 +08:00
不好意思，上面第二个方案说错了，是把 n 个文本串的所有后缀建成一颗 Trie 树，建树时间是 O(n * m^2)。
|
 |
10
HelloAmadeus OP @geelaw 是子串，不好意思搞错了。后缀树研究过一点，不确定好不好用，试一下实现一个
|
|
11
HelloAmadeus OP @dongyx 是多次匹配，trie 树考虑过，内存占用不能接受
|
 |
12
kedadiannao220 2019-06-05 09:19:26 +08:00
sed
awk |
 |
14
bnbdfg 2019-06-05 11:36:23 +08:00
50 万长度，python 不太好实现你这种性能要求
|
 |
15
BiteTheDust 2019-06-05 11:55:55 +08:00
用后缀自动机可以很简单的实现
|
 |
16
longchisihai 2019-06-06 14:24:26 +08:00
试试看 flashtext
|
Select Language