t***q
发帖数: 418 | 1 有两个LIST,一个LIST 2000行左右的数据。另一个LIST 3000行左右的数据。现在对
2000行的LIST的每一行，要遍历3000行的LIST的每一行，做一些运算，然后对于2000行
的LIST的每一行，可以给出3000行左右的值，再对这3000行左右的值取MAX。
写了一个PYTHON程序，算这样一个东西要花26分钟。据说这不EFFICIENT.
想问一下，怎样写才能提高SCRIPT的EFFICIENCY?
一般来讲这样的程序，运算的比较快的话，需多少分钟？
如果是一个3000行，和100，000行的LIST，做这样的运算，比较快的程序，完成这样的
运算得多长时间？多谢！有包子！ |
n*******e
发帖数: 4894 | 2 具体什么运算？
【在 t***q 的大作中提到】
: 有两个LIST,一个LIST 2000行左右的数据。另一个LIST 3000行左右的数据。现在对
: 2000行的LIST的每一行，要遍历3000行的LIST的每一行，做一些运算，然后对于2000行
: 的LIST的每一行，可以给出3000行左右的值，再对这3000行左右的值取MAX。
: 写了一个PYTHON程序，算这样一个东西要花26分钟。据说这不EFFICIENT.
: 想问一下，怎样写才能提高SCRIPT的EFFICIENCY?
: 一般来讲这样的程序，运算的比较快的话，需多少分钟？
: 如果是一个3000行，和100，000行的LIST，做这样的运算，比较快的程序，完成这样的
: 运算得多长时间？多谢！有包子！
|
o***g
发帖数: 2784 | 3 你这2k * 3k能简化么？
【在 t***q 的大作中提到】
: 有两个LIST,一个LIST 2000行左右的数据。另一个LIST 3000行左右的数据。现在对
: 2000行的LIST的每一行，要遍历3000行的LIST的每一行，做一些运算，然后对于2000行
: 的LIST的每一行，可以给出3000行左右的值，再对这3000行左右的值取MAX。
: 写了一个PYTHON程序，算这样一个东西要花26分钟。据说这不EFFICIENT.
: 想问一下，怎样写才能提高SCRIPT的EFFICIENCY?
: 一般来讲这样的程序，运算的比较快的话，需多少分钟？
: 如果是一个3000行，和100，000行的LIST，做这样的运算，比较快的程序，完成这样的
: 运算得多长时间？多谢！有包子！
|
s***o
发帖数: 175 | |
t***q
发帖数: 418 | 5 就是每个LIST的每一行是一个string,对于每个STRING，用DIFFLIB.SEQUENCEMATCHER算
一个SIMILARITY RATIO,再对2000行STRING里的每一行，从它算出的3000行STRING的里
算出的SIMILARITY RATIO，取出3000行里SIMILARITY RATIO最大的那一行STRING.
【在 n*******e 的大作中提到】
: 具体什么运算？
|
g*******t
发帖数: 7704 | 6 这种优化要算法功底深厚，别浪费时间了
【在 t***q 的大作中提到】
: 有两个LIST,一个LIST 2000行左右的数据。另一个LIST 3000行左右的数据。现在对
: 2000行的LIST的每一行，要遍历3000行的LIST的每一行，做一些运算，然后对于2000行
: 的LIST的每一行，可以给出3000行左右的值，再对这3000行左右的值取MAX。
: 写了一个PYTHON程序，算这样一个东西要花26分钟。据说这不EFFICIENT.
: 想问一下，怎样写才能提高SCRIPT的EFFICIENCY?
: 一般来讲这样的程序，运算的比较快的话，需多少分钟？
: 如果是一个3000行，和100，000行的LIST，做这样的运算，比较快的程序，完成这样的
: 运算得多长时间？多谢！有包子！
|
z****e
发帖数: 54598 | 7 换成scala实现
【在 t***q 的大作中提到】
: 有两个LIST,一个LIST 2000行左右的数据。另一个LIST 3000行左右的数据。现在对
: 2000行的LIST的每一行，要遍历3000行的LIST的每一行，做一些运算，然后对于2000行
: 的LIST的每一行，可以给出3000行左右的值，再对这3000行左右的值取MAX。
: 写了一个PYTHON程序，算这样一个东西要花26分钟。据说这不EFFICIENT.
: 想问一下，怎样写才能提高SCRIPT的EFFICIENCY?
: 一般来讲这样的程序，运算的比较快的话，需多少分钟？
: 如果是一个3000行，和100，000行的LIST，做这样的运算，比较快的程序，完成这样的
: 运算得多长时间？多谢！有包子！
|
t***q
发帖数: 418 | 8 JAVA 呢？尤其java 对于 4000 * 100,000=400M这样的数据量，算起来快吗？多谢！
【在 z****e 的大作中提到】
: 换成scala实现
|
w****w
发帖数: 521 | 9 你把十万行分成50个job并行跑，多用几个core就行了。 |
p**r
发帖数: 5853 | 10 具体2个list之间的逻辑不清楚，
如果这部分逻辑上没法做优化的话，
那剩下的只能是做预处理，或堆硬件。 |
|
|
t***q
发帖数: 418 | 11 多谢，多谢。想问一下对于 4000× 100，000这样的数据，运算起来是要很费事吗？对
于JAVA来说。多谢！
【在 p**r 的大作中提到】
: 具体2个list之间的逻辑不清楚，
: 如果这部分逻辑上没法做优化的话，
: 那剩下的只能是做预处理，或堆硬件。
|
z****e
发帖数: 54598 | 12 应该跟scala差不多
【在 t***q 的大作中提到】
: JAVA 呢？尤其java 对于 4000 * 100,000=400M这样的数据量，算起来快吗？多谢！
|
n*******e
发帖数: 4894 | 13 遍历不费事，费时而已，但是好像你也没别的选择
【在 t***q 的大作中提到】
: 多谢，多谢。想问一下对于 4000× 100，000这样的数据，运算起来是要很费事吗？对
: 于JAVA来说。多谢！
|
p**r
发帖数: 5853 | 14 上次用java大概是7年了，你问问其他人，我基本都用c#做事。
很多事情你还是多研究算法，逻辑吧，语言差别应该不大。
之前跑过类似数据量，改了逻辑之后，
从大概10几分钟降到几十ms，基本就是淘汰+预处理，
缺点就是不那么real time的
【在 t***q 的大作中提到】
: 多谢，多谢。想问一下对于 4000× 100，000这样的数据，运算起来是要很费事吗？对
: 于JAVA来说。多谢！
|
t***q
发帖数: 418 | 15 多谢。那大概得多长时间呢？
2000×3000 PYTHON 的SCRIPT就花了26MINS.
4000*100,000对于JAVA呢？
有多耗时？
多谢！
【在 z****e 的大作中提到】
: 应该跟scala差不多
|
z****e
发帖数: 54598 | 16 我记得我上次用python半个多小时跑完的东西
用java只要几分钟就好，如果优化得好的话
比如打掉一些不必要的锁，几分钟就好
反正代码就这么点，你试试不就知道了
这点逻辑，如果eclipse等没啥问题的话
最多10分钟就能写出来了
你在这里等答案，小马过河，还不如动手试试 |
p**r
发帖数: 5853 | 17 问时间没意义的，硬件不同。
【在 t***q 的大作中提到】
: 多谢。那大概得多长时间呢？
: 2000×3000 PYTHON 的SCRIPT就花了26MINS.
: 4000*100,000对于JAVA呢？
: 有多耗时？
: 多谢！
|
t***q
发帖数: 418 | 18 多谢，多谢！
【在 p**r 的大作中提到】
: 上次用java大概是7年了，你问问其他人，我基本都用c#做事。
: 很多事情你还是多研究算法，逻辑吧，语言差别应该不大。
: 之前跑过类似数据量，改了逻辑之后，
: 从大概10几分钟降到几十ms，基本就是淘汰+预处理，
: 缺点就是不那么real time的
|
t***q
发帖数: 418 | 19 嗯，多谢！
【在 z****e 的大作中提到】
: 我记得我上次用python半个多小时跑完的东西
: 用java只要几分钟就好，如果优化得好的话
: 比如打掉一些不必要的锁，几分钟就好
: 反正代码就这么点，你试试不就知道了
: 这点逻辑，如果eclipse等没啥问题的话
: 最多10分钟就能写出来了
: 你在这里等答案，小马过河，还不如动手试试
|
z****e
发帖数: 54598 | 20 不不
python出了名的慢
解释器不行
jvm明显快很多
【在 p**r 的大作中提到】
: 上次用java大概是7年了，你问问其他人，我基本都用c#做事。
: 很多事情你还是多研究算法，逻辑吧，语言差别应该不大。
: 之前跑过类似数据量，改了逻辑之后，
: 从大概10几分钟降到几十ms，基本就是淘汰+预处理，
: 缺点就是不那么real time的
|
|
|
N********n
发帖数: 8363 | 21 divide & conquer, especially when there's no dependence b/t these
lists. |
z****e
发帖数: 54598 | 22 soga
你做的是倒排表
接近text相似度那种
你第一步先把数据转换
然后存起来，用的时候从转换后的数据中读
不要用list，用hashmap(java)或者python的dictionary
list效率太低，你每次都得遍历
复杂度很快就上去了，用hashmap，查找效率最快
超过tree
反正你也不需要频繁地插入或者修改数据不是？
我上次用hashmap对莎士比亚的全集做word counts
就用了4秒多，我都怀疑这么快是不是我弄错了
其他人用list，算了好久
【在 t***q 的大作中提到】
: 就是每个LIST的每一行是一个string,对于每个STRING，用DIFFLIB.SEQUENCEMATCHER算
: 一个SIMILARITY RATIO,再对2000行STRING里的每一行，从它算出的3000行STRING的里
: 算出的SIMILARITY RATIO，取出3000行里SIMILARITY RATIO最大的那一行STRING.
|
n*****t
发帖数: 22014 | 23 先 sort，运算 (1+3000)x2000 次
【在 t***q 的大作中提到】
: 有两个LIST,一个LIST 2000行左右的数据。另一个LIST 3000行左右的数据。现在对
: 2000行的LIST的每一行，要遍历3000行的LIST的每一行，做一些运算，然后对于2000行
: 的LIST的每一行，可以给出3000行左右的值，再对这3000行左右的值取MAX。
: 写了一个PYTHON程序，算这样一个东西要花26分钟。据说这不EFFICIENT.
: 想问一下，怎样写才能提高SCRIPT的EFFICIENCY?
: 一般来讲这样的程序，运算的比较快的话，需多少分钟？
: 如果是一个3000行，和100，000行的LIST，做这样的运算，比较快的程序，完成这样的
: 运算得多长时间？多谢！有包子！
|
z****e
发帖数: 54598 | 24 相似度有一个理论
你这里应该是26个字母
所以dimension = 26
然后normalize每个string
最后点乘后根据点乘结果做排序
就是倒排表
所以你可以把这个处理的结果存起来
下次读的时候，就不需要重新算一遍
直接从处理结果中取就行了，这样就可以优化整体效率 |
p**r
发帖数: 5853 | 25 懂了，多谢。
【在 z****e 的大作中提到】
: 不不
: python出了名的慢
: 解释器不行
: jvm明显快很多
|
s***o
发帖数: 175 | 26 2k x 3k
每次从2k取一个string 跟3k序列算相似度时，只需保存最大值即可，没必要3000个值
都保存，还要从新算最大值。 |
f***y
发帖数: 247 | 27 分成2000个job，每个跑一行不就完了。另外写个driver script控制parallelism
【在 t***q 的大作中提到】
: 有两个LIST,一个LIST 2000行左右的数据。另一个LIST 3000行左右的数据。现在对
: 2000行的LIST的每一行，要遍历3000行的LIST的每一行，做一些运算，然后对于2000行
: 的LIST的每一行，可以给出3000行左右的值，再对这3000行左右的值取MAX。
: 写了一个PYTHON程序，算这样一个东西要花26分钟。据说这不EFFICIENT.
: 想问一下，怎样写才能提高SCRIPT的EFFICIENCY?
: 一般来讲这样的程序，运算的比较快的话，需多少分钟？
: 如果是一个3000行，和100，000行的LIST，做这样的运算，比较快的程序，完成这样的
: 运算得多长时间？多谢！有包子！
|
d******e
发帖数: 2265 | 28 简单的多进程
queue 是2000行的表
复杂点上 celery多机器算
4个基本上算到2分钟够了
再复杂hadoop
【在 t***q 的大作中提到】
: 有两个LIST,一个LIST 2000行左右的数据。另一个LIST 3000行左右的数据。现在对
: 2000行的LIST的每一行，要遍历3000行的LIST的每一行，做一些运算，然后对于2000行
: 的LIST的每一行，可以给出3000行左右的值，再对这3000行左右的值取MAX。
: 写了一个PYTHON程序，算这样一个东西要花26分钟。据说这不EFFICIENT.
: 想问一下，怎样写才能提高SCRIPT的EFFICIENCY?
: 一般来讲这样的程序，运算的比较快的话，需多少分钟？
: 如果是一个3000行，和100，000行的LIST，做这样的运算，比较快的程序，完成这样的
: 运算得多长时间？多谢！有包子！
|
g*****g
发帖数: 34805 | 29 这种是典型ETL问题。数据量不大单机多线程即可。数据量大spark。 |
d******e
发帖数: 2265 | 30 如果你之需要最大的
可以先简单计算排除多数在蛮干
不是科班出身的?
【在 t***q 的大作中提到】
: 就是每个LIST的每一行是一个string,对于每个STRING，用DIFFLIB.SEQUENCEMATCHER算
: 一个SIMILARITY RATIO,再对2000行STRING里的每一行，从它算出的3000行STRING的里
: 算出的SIMILARITY RATIO，取出3000行里SIMILARITY RATIO最大的那一行STRING.
|
|
|
t***q
发帖数: 418 | 31 你好，多谢。我就是用的PYTHON 的DICTIONARY, 但是我就是不懂，如何才能做到不遍
历呢?
我觉得，我虽然用PYTHON 的DICTIONARY，但是方法还是遍历的：
我把两列STRING放到两个DICTIONARY里作为KEY，然后再对两组KEY遍历：
for k,k2 in itertools.product(dict1.keys(),my_dict1.keys()):
a=float(difflib.SequenceMatcher(None,k,k2).ratio())
if a>0.80:
my_dict3[k+"t"+k2]=a
for key2 in my_dict3.keys():
k1=key2.split("t")[0]
k2=key2.split("t")[1]
mydict[k1][k2]=my_dict3[key2]
k=key2.split("t")
keylist4=mydict.keys()
for key4 in keylist4:
key=max(mydict[key4].iteritems(),key=operator.itemgetter(1))[0]
print "%st%s" % (key4,key)
天，我倒是是哪里错了？谁来指导我？
多谢！
【在 z****e 的大作中提到】
: soga
: 你做的是倒排表
: 接近text相似度那种
: 你第一步先把数据转换
: 然后存起来，用的时候从转换后的数据中读
: 不要用list，用hashmap(java)或者python的dictionary
: list效率太低，你每次都得遍历
: 复杂度很快就上去了，用hashmap，查找效率最快
: 超过tree
: 反正你也不需要频繁地插入或者修改数据不是？
|
t***q
发帖数: 418 | 32 ding 多谢！
【在 t***q 的大作中提到】
: 你好，多谢。我就是用的PYTHON 的DICTIONARY, 但是我就是不懂，如何才能做到不遍
: 历呢?
: 我觉得，我虽然用PYTHON 的DICTIONARY，但是方法还是遍历的：
: 我把两列STRING放到两个DICTIONARY里作为KEY，然后再对两组KEY遍历：
: for k,k2 in itertools.product(dict1.keys(),my_dict1.keys()):
: a=float(difflib.SequenceMatcher(None,k,k2).ratio())
: if a>0.80:
: my_dict3[k+"t"+k2]=a
: for key2 in my_dict3.keys():
: k1=key2.split("t")[0]
|
l***z
发帖数: 61 | 33 可以试试numba库，给函数加上@jit，把python自动编译成llvm，性能应该会提高不少。
【在 t***q 的大作中提到】
: 有两个LIST,一个LIST 2000行左右的数据。另一个LIST 3000行左右的数据。现在对
: 2000行的LIST的每一行，要遍历3000行的LIST的每一行，做一些运算，然后对于2000行
: 的LIST的每一行，可以给出3000行左右的值，再对这3000行左右的值取MAX。
: 写了一个PYTHON程序，算这样一个东西要花26分钟。据说这不EFFICIENT.
: 想问一下，怎样写才能提高SCRIPT的EFFICIENCY?
: 一般来讲这样的程序，运算的比较快的话，需多少分钟？
: 如果是一个3000行，和100，000行的LIST，做这样的运算，比较快的程序，完成这样的
: 运算得多长时间？多谢！有包子！
|
t***q
发帖数: 418 | 34 有两个LIST,一个LIST 4000行左右的数据。另一个LIST 100,000行左右的数据。现在对
4000行的LIST的每一行，要遍历100,000行的LIST的每一行，用DIFFLIB.
SEQUENCEMATCHER算
一个SIMILARITY RATIO,再对4000行STRING里的每一行，从它算出的100,000行STRING的里
算出的SIMILARITY RATIO，取出100,000行里SIMILARITY RATIO最大的那一行STRING. |
l***z
发帖数: 61 | 35 你这个问题和生物信息里面序列比对非常类似，建议参考BLAST或者BWA程序的优化算法
，经过优化几千甚至 X 几百万的规模也可以做。
【在 t***q 的大作中提到】
: 有两个LIST,一个LIST 4000行左右的数据。另一个LIST 100,000行左右的数据。现在对
: 4000行的LIST的每一行，要遍历100,000行的LIST的每一行，用DIFFLIB.
: SEQUENCEMATCHER算
: 一个SIMILARITY RATIO,再对4000行STRING里的每一行，从它算出的100,000行STRING的里
: 算出的SIMILARITY RATIO，取出100,000行里SIMILARITY RATIO最大的那一行STRING.
|
l*******b
发帖数: 2586 | 36 Use a compiler, instead of interpreter :)
【在 t***q 的大作中提到】
: 有两个LIST,一个LIST 4000行左右的数据。另一个LIST 100,000行左右的数据。现在对
: 4000行的LIST的每一行，要遍历100,000行的LIST的每一行，用DIFFLIB.
: SEQUENCEMATCHER算
: 一个SIMILARITY RATIO,再对4000行STRING里的每一行，从它算出的100,000行STRING的里
: 算出的SIMILARITY RATIO，取出100,000行里SIMILARITY RATIO最大的那一行STRING.
|
z****e
发帖数: 54598 | 37 遍历不遍历跟dic本身的实现有关呀
就我的感觉，python的dic的使用比java的hashmap要慢不少
效率上
【在 t***q 的大作中提到】
: 你好，多谢。我就是用的PYTHON 的DICTIONARY, 但是我就是不懂，如何才能做到不遍
: 历呢?
: 我觉得，我虽然用PYTHON 的DICTIONARY，但是方法还是遍历的：
: 我把两列STRING放到两个DICTIONARY里作为KEY，然后再对两组KEY遍历：
: for k,k2 in itertools.product(dict1.keys(),my_dict1.keys()):
: a=float(difflib.SequenceMatcher(None,k,k2).ratio())
: if a>0.80:
: my_dict3[k+"t"+k2]=a
: for key2 in my_dict3.keys():
: k1=key2.split("t")[0]
|
t***q
发帖数: 418 | 38 那你觉得，我这个PYTHON DICTIONARY 的用法有什么问题？你能举个EFFICIENT 的例子
吗？多谢！
【在 z****e 的大作中提到】
: 遍历不遍历跟dic本身的实现有关呀
: 就我的感觉，python的dic的使用比java的hashmap要慢不少
: 效率上
|
t***q
发帖数: 418 | 39 天，我今儿个快晕了。我甚至，还写了个hadoop mapreduce streaming job,跑这个程
序。主要那个hadoop mapreduce STREAMING JOB, 运行没通过。否则，2，30分钟，应
该出结果了。 |
t***q
发帖数: 418 | |
|
|
z****e
发帖数: 54598 | 41 用法感觉没问题，用的话不可能有太大差异
如果你用这种工具还需要留意怎么用才更有效的话
那你还不如自己去实现呢
其实说白了，你就是觉得python效率太低
想要优化，有几个选择
你可以试试pypy，你也可以试试jython
最后你可以用java或者scala重新实现一遍逻辑
【在 t***q 的大作中提到】
: 那你觉得，我这个PYTHON DICTIONARY 的用法有什么问题？你能举个EFFICIENT 的例子
: 吗？多谢！
|
t***q
发帖数: 418 | 42 多谢，ZHAOCE，我主要,JAVA的程序就写过HELLO WORLD,今天看了一下JAVA的TUTORIAL
，觉得，这个东西，要我用JAVA实现，可能还是困难。不过，我确实该学学JAVA了。嗯
。包子已发。
【在 z****e 的大作中提到】
: 用法感觉没问题，用的话不可能有太大差异
: 如果你用这种工具还需要留意怎么用才更有效的话
: 那你还不如自己去实现呢
: 其实说白了，你就是觉得python效率太低
: 想要优化，有几个选择
: 你可以试试pypy，你也可以试试jython
: 最后你可以用java或者scala重新实现一遍逻辑
|
z****e
发帖数: 54598 | 43 你搞big data还是把java弄好点，然后scala
java不难，你一个月认真看看书，起步阶段不要偷懒
文科生都能学会，我见过好多学arts的学java，都能a
就怕起步阶段偷懒，老投机取巧
最后老是要还回去，python比java慢的一个主因就是dynamic type
动态类型非常吃性能，java和scala都是static type
TUTORIAL
【在 t***q 的大作中提到】
: 多谢，ZHAOCE，我主要,JAVA的程序就写过HELLO WORLD,今天看了一下JAVA的TUTORIAL
: ，觉得，这个东西，要我用JAVA实现，可能还是困难。不过，我确实该学学JAVA了。嗯
: 。包子已发。
|
a9
发帖数: 21638 | 44 他这个如果不优化算法，用任何语言在时间上都不会有数量级上的变化。
。嗯
【在 z****e 的大作中提到】
: 你搞big data还是把java弄好点，然后scala
: java不难，你一个月认真看看书，起步阶段不要偷懒
: 文科生都能学会，我见过好多学arts的学java，都能a
: 就怕起步阶段偷懒，老投机取巧
: 最后老是要还回去，python比java慢的一个主因就是dynamic type
: 动态类型非常吃性能，java和scala都是static type
:
: TUTORIAL
|
z****e
发帖数: 54598 | 45 他做的这个只是text analysis里面的一个作业而已
优化的方法我前面也说了，把normalized的结果存起来
下次用的时候读就好了，不用重新算，这样o(n)就可以搞定
如果有必要，再reduce，不过才10万个string，感觉没必要
这个方法老师应该在上课时候讲过
要么就是还没讲到
【在 a9 的大作中提到】
: 他这个如果不优化算法，用任何语言在时间上都不会有数量级上的变化。
:
: 。嗯
|
c****f
发帖数: 1102 | 46 可以试试把3K行那个切开来 换成3个1k行
然后写个worker 扔进去一个2K行里面的一行 查给的1K行
然后go worker（1， 1000， &wg）
等于你concurrent查询的小段 然后利用满CPU
应该会快点 |
t***q
发帖数: 418 | 47 嗨，后来，我一同学，用R 写了一个程序。那样的数据量，30多分钟就运行完了。
看来，我真是应该好好检讨一下，自己的CODE 不EFFICIENT. 多谢诸位。 |
S*A
发帖数: 7142 | 48 LZ 的这个问题是挺有意思的。
python difflib.sequencematcher 里面的解决的问题是 Longest common subsequence
problem
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
这个问题是 NP hard 的。
我觉得你有可能把他混淆成 Longest common substring problem
http://en.wikipedia.org/wiki/Longest_common_substring_problem
对于LZ的 LCS 问题（前者），我比较愚昧，没有看出你的倒排表能帮助些什么。
后者有可能。
你要是觉得还是可以有算法级别的加快可以用个简单 pseduo code 展示一下
如何 work 的。
【在 z****e 的大作中提到】
: 相似度有一个理论
: 你这里应该是26个字母
: 所以dimension = 26
: 然后normalize每个string
: 最后点乘后根据点乘结果做排序
: 就是倒排表
: 所以你可以把这个处理的结果存起来
: 下次读的时候，就不需要重新算一遍
: 直接从处理结果中取就行了，这样就可以优化整体效率
|
S*A
发帖数: 7142 | 49 longest common subsequent 复杂的地方不是在于找
出那些 substring 是有共同的，而是串那些 substring
加起来最长。你取其中一个substring, 就有可能要放弃
里面开始的另外一个 substring。
这个是要根据要比较的两个 string 来做的，不太觉得你
O（n）可以搞定一个 NP 问题。
【在 z****e 的大作中提到】
: 他做的这个只是text analysis里面的一个作业而已
: 优化的方法我前面也说了，把normalized的结果存起来
: 下次用的时候读就好了，不用重新算，这样o(n)就可以搞定
: 如果有必要，再reduce，不过才10万个string，感觉没必要
: 这个方法老师应该在上课时候讲过
: 要么就是还没讲到
|
g*******t
发帖数: 7704 | 50 我的意见，不值得优化，程序就让它跑几天，这才象高研究的样子， |
|
|
z****e
发帖数: 54598 | 51 楼主不是说了么？
找的是相似的string
你说的这个不是相似
是字面上的意思，就是最长的子串
subsequence
【在 S*A 的大作中提到】
: LZ 的这个问题是挺有意思的。
: python difflib.sequencematcher 里面的解决的问题是 Longest common subsequence
: problem
: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
: 这个问题是 NP hard 的。
: 我觉得你有可能把他混淆成 Longest common substring problem
: http://en.wikipedia.org/wiki/Longest_common_substring_problem
: 对于LZ的 LCS 问题（前者），我比较愚昧，没有看出你的倒排表能帮助些什么。
: 后者有可能。
: 你要是觉得还是可以有算法级别的加快可以用个简单 pseduo code 展示一下
|
z****e
发帖数: 54598 | 52 相似跟最长子串又不是一回事
你为啥那么热衷于本科生学的那些？
【在 S*A 的大作中提到】
: longest common subsequent 复杂的地方不是在于找
: 出那些 substring 是有共同的，而是串那些 substring
: 加起来最长。你取其中一个substring, 就有可能要放弃
: 里面开始的另外一个 substring。
: 这个是要根据要比较的两个 string 来做的，不太觉得你
: O（n）可以搞定一个 NP 问题。
|
z****e
发帖数: 54598 | 53 你的不也是几十分钟吗？
【在 t***q 的大作中提到】
: 嗨，后来，我一同学，用R 写了一个程序。那样的数据量，30多分钟就运行完了。
: 看来，我真是应该好好检讨一下，自己的CODE 不EFFICIENT. 多谢诸位。
|
t***q
发帖数: 418 | 54 问题是我的不是跑了几十分钟，是几百分钟，现在想想自己的代码肯定有问题。想问一
下zhaoce，你估计要你自己用python写程序，这样的复杂度，程序大概要跑多长时间？
多谢！
【在 z****e 的大作中提到】
: 你的不也是几十分钟吗？
|
z****e
发帖数: 54598 | 55 硬件不一样，估计时间没有太大意义
我还可以用hpc去跑呢，就会快很多
你这个作业原题是什么？
计算string的相似度吗？
然后输入一个关键词，返回相似度最大的string，根据相似度做排序对不？
【在 t***q 的大作中提到】
: 问题是我的不是跑了几十分钟，是几百分钟，现在想想自己的代码肯定有问题。想问一
: 下zhaoce，你估计要你自己用python写程序，这样的复杂度，程序大概要跑多长时间？
: 多谢！
|
S*A
发帖数: 7142 | 56
你看到原文里面那个代码：
difflib.SequenceMatcher(None,k,k2).ratio()
这个是找 longest common subsequence.
不是 longest common substring.
【在 z****e 的大作中提到】
: 楼主不是说了么？
: 找的是相似的string
: 你说的这个不是相似
: 是字面上的意思，就是最长的子串
:
: subsequence
|
t***q
发帖数: 418 | 57 是计算string的相似度，其实就两个files,一个4000行，每行一个string，一个100，
000行，每行一个string,然后，输出是4000行，每一行两个string,4000行里原始的
string和100，000行里和它有最大相似度的string，就想问一下，如果是在laptop上跑
，这样的电脑：
http://www.amazon.com/HP-EliteBook-F2P21UT-Processor-Windows/dp
就用windows的python gui，2.7.8,写一个程序，运算这样一个程序，估计得多久？
多谢！
【在 z****e 的大作中提到】
: 硬件不一样，估计时间没有太大意义
: 我还可以用hpc去跑呢，就会快很多
: 你这个作业原题是什么？
: 计算string的相似度吗？
: 然后输入一个关键词，返回相似度最大的string，根据相似度做排序对不？
|
t***q
发帖数: 418 | 58 hpc是什么？多谢！
【在 z****e 的大作中提到】
: 硬件不一样，估计时间没有太大意义
: 我还可以用hpc去跑呢，就会快很多
: 你这个作业原题是什么？
: 计算string的相似度吗？
: 然后输入一个关键词，返回相似度最大的string，根据相似度做排序对不？
|
S*A
发帖数: 7142 | 59
你先搞清楚 LZ 的用的 difflib.SequenceMatcher（）是做什么的吧。
我非常肯定那个 SequenceMatch() 是 LCS。
这个和你建议的找最长的一个子串不是一个问题，也不是一个难度。
所以 LZ 需要的是苹果，你建议给了个橘子，和苹果都差不多，将就
了就可以了，是这个意思吧。
【在 z****e 的大作中提到】
: 相似跟最长子串又不是一回事
: 你为啥那么热衷于本科生学的那些？
|
S*A
发帖数: 7142 | 60 你的一行的 string 大概是多少 byte 的，有区间吗？
你的相似度最大需要精确吗？还是接近最大的差不多就行？
【在 t***q 的大作中提到】
: 是计算string的相似度，其实就两个files,一个4000行，每行一个string，一个100，
: 000行，每行一个string,然后，输出是4000行，每一行两个string,4000行里原始的
: string和100，000行里和它有最大相似度的string，就想问一下，如果是在laptop上跑
: ，这样的电脑：
: http://www.amazon.com/HP-EliteBook-F2P21UT-Processor-Windows/dp
: 就用windows的python gui，2.7.8,写一个程序，运算这样一个程序，估计得多久？
: 多谢！
|
|
|
t***q
发帖数: 418 | 61 一个string顶多30个character,相似度就按照difflib.SequenceMatcher(None,k,k2).
ratio()算，算出什么，就按什么来。像0.8866
【在 S*A 的大作中提到】
: 你的一行的 string 大概是多少 byte 的，有区间吗？
: 你的相似度最大需要精确吗？还是接近最大的差不多就行？
|
z****e
发帖数: 54598 | 62 string的相似度有定义没？
自己决定还是说最大子串/字符串长？
【在 t***q 的大作中提到】
: 是计算string的相似度，其实就两个files,一个4000行，每行一个string，一个100，
: 000行，每行一个string,然后，输出是4000行，每一行两个string,4000行里原始的
: string和100，000行里和它有最大相似度的string，就想问一下，如果是在laptop上跑
: ，这样的电脑：
: http://www.amazon.com/HP-EliteBook-F2P21UT-Processor-Windows/dp
: 就用windows的python gui，2.7.8,写一个程序，运算这样一个程序，估计得多久？
: 多谢！
|
z****e
发帖数: 54598 | 63 相似度如果用这种方式设计算法的话
那自然束手束脚，我想的是，这可能只是楼主自己的定义
text的similarity的判断不是用这种方式来做的
【在 S*A 的大作中提到】
: 你的一行的 string 大概是多少 byte 的，有区间吗？
: 你的相似度最大需要精确吗？还是接近最大的差不多就行？
|
t***q
发帖数: 418 | 64 相似度没有定义，就按照 difflib.sequencemacther.ratio()的算法来
Return a measure of the sequences' similarity (float in [0,1]).
Where T is the total number of elements in both sequences, and M is the
number of matches, this is 2.0*M / T. Note that this is 1 if the sequences
are identical, and 0 if they have nothing in common.
找number of intersected elements.
【在 z****e 的大作中提到】
: string的相似度有定义没？
: 自己决定还是说最大子串/字符串长？
|
t***q
发帖数: 418 | 65 对，是我自己的定义。就先算个数出来。科学不科学，另说吧。多谢！
【在 z****e 的大作中提到】
: 相似度如果用这种方式设计算法的话
: 那自然束手束脚，我想的是，这可能只是楼主自己的定义
: text的similarity的判断不是用这种方式来做的
|
z****e
发帖数: 54598 | 66 没有定义就好
你就可以用倒排表来优化效率
先通过倒排表建索引
然后把这个中间值存起来
normalize成decimal
下次计算时候，直接计算点乘
然后按照点乘的结果排序
这样就快很多
完全可以做到o(n)复杂度
如果有必要，你再通过map reduce去取top k
只不过这点数据量，不会有多大，可能毫无必要了
【在 t***q 的大作中提到】
: 相似度没有定义，就按照 difflib.sequencemacther.ratio()的算法来
: Return a measure of the sequences' similarity (float in [0,1]).
: Where T is the total number of elements in both sequences, and M is the
: number of matches, this is 2.0*M / T. Note that this is 1 if the sequences
: are identical, and 0 if they have nothing in common.
: 找number of intersected elements.
|
z****e
发帖数: 54598 | 67 但是如果你坚持要用这个算法的话
那你每次都得取这个最大子串，然后计算ratio
那这个复杂度就高了，比较合理的方法就是其他人说的map reduce了
把这个list切割成5个2k的小lists，然后并行就是了
这属于可以parallel的computing，最后做个归并
或者你换掉工具，jvm或者pypy，都能提升效率，但是并不改变复杂度
你同学用r的话，估计不太可能是parallel的方式
因为r本身是单线程的
有没有可能是你的python程序频繁地io？
你先把整个list读入内存后，再做计算，这样有可能会快
【在 t***q 的大作中提到】
: 相似度没有定义，就按照 difflib.sequencemacther.ratio()的算法来
: Return a measure of the sequences' similarity (float in [0,1]).
: Where T is the total number of elements in both sequences, and M is the
: number of matches, this is 2.0*M / T. Note that this is 1 if the sequences
: are identical, and 0 if they have nothing in common.
: 找number of intersected elements.
|
t***q
发帖数: 418 | 68 多谢，请问倒序表这些知识去哪里找？为什么要点乘？map reduce 在这里，你说的是
map reduce 的算法思想吧，而不是hadoop map reduce cluster 这些东西， 对吗？还
有，就是像这些编程的知识，技巧去哪本书里能学来？多谢！
【在 z****e 的大作中提到】
: 没有定义就好
: 你就可以用倒排表来优化效率
: 先通过倒排表建索引
: 然后把这个中间值存起来
: normalize成decimal
: 下次计算时候，直接计算点乘
: 然后按照点乘的结果排序
: 这样就快很多
: 完全可以做到o(n)复杂度
: 如果有必要，你再通过map reduce去取top k
|
t***q
发帖数: 418 | 69 多谢，听起来好高深。
说起list读入内存，以前处理过1亿行那么多的数据，我用list读入，结果python out
of memory 了，老板说那样的数据量要建hash table.
【在 z****e 的大作中提到】
: 但是如果你坚持要用这个算法的话
: 那你每次都得取这个最大子串，然后计算ratio
: 那这个复杂度就高了，比较合理的方法就是其他人说的map reduce了
: 把这个list切割成5个2k的小lists，然后并行就是了
: 这属于可以parallel的computing，最后做个归并
: 或者你换掉工具，jvm或者pypy，都能提升效率，但是并不改变复杂度
: 你同学用r的话，估计不太可能是parallel的方式
: 因为r本身是单线程的
: 有没有可能是你的python程序频繁地io？
: 你先把整个list读入内存后，再做计算，这样有可能会快
|
z****e
发帖数: 54598 | 70 spark里面就有
ml的课上也会教
点乘说起来就麻烦了
找个text analysis或者ml的教材之类的看看
不过这个开始进入数学理论了
如果你只是追求效率快的话
上多线程，把这一个list切割成5个小lists
然后每一个用线程并行，这样基本上快4－5倍应该问题不大
这也是最简单的优化手段
【在 t***q 的大作中提到】
: 多谢，请问倒序表这些知识去哪里找？为什么要点乘？map reduce 在这里，你说的是
: map reduce 的算法思想吧，而不是hadoop map reduce cluster 这些东西， 对吗？还
: 有，就是像这些编程的知识，技巧去哪本书里能学来？多谢！
|
|
|
z****e
发帖数: 54598 | 71 一亿行肯定不行
如果那么多的话
你找个db来存
然后在db里面建index
然后通过db的index来找
这样就快点
全部读入内存，数据量一大，肯定会出问题
out
【在 t***q 的大作中提到】
: 多谢，听起来好高深。
: 说起list读入内存，以前处理过1亿行那么多的数据，我用list读入，结果python out
: of memory 了，老板说那样的数据量要建hash table.
|
S*A
发帖数: 7142 | 72 LZ 这个定义用LCS是精确的。你那个找最大子串的定义是不够好的。
我举例说名一下:下一句和第一句比较：
"LZ 这个_定义是精确_的。你_那个找最_大子串的_定义是不_够好的。"
说明一下，我就是每几个字符插一个下划线。
你用最大字符串找出来是 5个汉字。相似度小于 1/5。
你用LCS找出来是全部第一句。相似度很高。
明显最大子串是不合理的。
不能为了方便计算而选择明显不合理的定义啊。
【在 z****e 的大作中提到】
: 相似度如果用这种方式设计算法的话
: 那自然束手束脚，我想的是，这可能只是楼主自己的定义
: text的similarity的判断不是用这种方式来做的
|
t***q
发帖数: 418 | 73 上司的意思是那么多数据，用python hash table好像能解决。我不太懂。
【在 z****e 的大作中提到】
: 一亿行肯定不行
: 如果那么多的话
: 你找个db来存
: 然后在db里面建index
: 然后通过db的index来找
: 这样就快点
: 全部读入内存，数据量一大，肯定会出问题
:
: out
|
z****e
发帖数: 54598 | 74 是，内存不够用了，需要用db等持久化的工具了
光靠内存不能解决所有问题
【在 t***q 的大作中提到】
: 上司的意思是那么多数据，用python hash table好像能解决。我不太懂。
|
d******e
发帖数: 2265 | 75 sequencemacther的时间复杂度是O(n^2) n=30 的话，一个操作算是常数c.
你6m个计算 26分钟，4分钟1M,一分钟250k.一秒大概5k.1ms大概5个计算，还算
make sense.python的话你提高不了多少了。
简单的，多进程,多基奇。说实话，问题再大10倍也是toy problem
真想提高，看看信息检索的教科书。考虑一下怎么用cosine来聚类
在复杂的，上矩阵分解。
【在 t***q 的大作中提到】
: 相似度没有定义，就按照 difflib.sequencemacther.ratio()的算法来
: Return a measure of the sequences' similarity (float in [0,1]).
: Where T is the total number of elements in both sequences, and M is the
: number of matches, this is 2.0*M / T. Note that this is 1 if the sequences
: are identical, and 0 if they have nothing in common.
: 找number of intersected elements.
|
S*A
发帖数: 7142 | 76
LCS 时间复杂度看了一下真实 O（nm），
wiki上说是指数是错误的。当然 n=30 也就是常数了。
对，而且两个输入文件完全可以读入内存的，非常小。
完全可以用数组访问，连hash都不需要。
这个要是用 C 做估计很快就出来了。
【在 d******e 的大作中提到】
: sequencemacther的时间复杂度是O(n^2) n=30 的话，一个操作算是常数c.
: 你6m个计算 26分钟，4分钟1M,一分钟250k.一秒大概5k.1ms大概5个计算，还算
: make sense.python的话你提高不了多少了。
: 简单的，多进程,多基奇。说实话，问题再大10倍也是toy problem
: 真想提高，看看信息检索的教科书。考虑一下怎么用cosine来聚类
: 在复杂的，上矩阵分解。
|
t***q
发帖数: 418 | 77 为什么说python我提高不了多少了？
但是，我真的想提高。
你算数算得还挺快。
我很不解，为什么我的python code算几百分钟，其他人的r code 算 几十分钟。
【在 d******e 的大作中提到】
: sequencemacther的时间复杂度是O(n^2) n=30 的话，一个操作算是常数c.
: 你6m个计算 26分钟，4分钟1M,一分钟250k.一秒大概5k.1ms大概5个计算，还算
: make sense.python的话你提高不了多少了。
: 简单的，多进程,多基奇。说实话，问题再大10倍也是toy problem
: 真想提高，看看信息检索的教科书。考虑一下怎么用cosine来聚类
: 在复杂的，上矩阵分解。
|
t***q
发帖数: 418 | 78 C is faster than Python?
【在 S*A 的大作中提到】
:
: LCS 时间复杂度看了一下真实 O（nm），
: wiki上说是指数是错误的。当然 n=30 也就是常数了。
: 对，而且两个输入文件完全可以读入内存的，非常小。
: 完全可以用数组访问，连hash都不需要。
: 这个要是用 C 做估计很快就出来了。
|
S*A
发帖数: 7142 | 79 C is way faster.
【在 t***q 的大作中提到】
: C is faster than Python?
|
S*A
发帖数: 7142 | 80 哈，我就是好奇，C 可以多快。
这里用一个 python script 生成用来测试的数据
a.txt 4000行。
b.txt 100000行。
每行都是 30 byte 的随即大写 A-Z。
import difflib
import random
import string
def gen_table(fname, size):
f = open(fname, 'w')
for j in range(size):
print >>f, ''.join(random.choice(string.ascii_uppercase) for i in
range(30))
gen_table('a.txt', 4000)
gen_table('b.txt', 100000) |
|
|
s***o
发帖数: 175 | 81 昨天手头刚好有几万个URL， 试了一下：
list1: 2000 URLs
list2: 3000 URLs
从list1取的每一个URL， 去和list2的3000个URL比较，找出最相似的，用时约1秒，
全部用时不到40分钟。
没做任何优化，只是把所有需要计算的URL放入两个generator:
generator1 = (url for url in list1)
generator2 = (url for url in list2)
每个URL平均50个字符，不懂有没有可比性。 |
z****e
发帖数: 54598 | 82 r用的pkg跟python用的pkg理论上不应该差太多
这两个都是c或者fortran写的
我觉得有可能是pkg内部实现的差异
你可以问问你同学/同事，r用的是什么pkg
【在 t***q 的大作中提到】
: 为什么说python我提高不了多少了？
: 但是，我真的想提高。
: 你算数算得还挺快。
: 我很不解，为什么我的python code算几百分钟，其他人的r code 算 几十分钟。
|
S*A
发帖数: 7142 | 83 real 19m21.306s
user 19m19.382s
sys 0m1.902s
这个是单线程做4000x100000， 每行30 random ASCII string。
配额合前面的 python 生成的数据文件使用。
这个 diff 的强度比较高了，我的破笔记本是老版MBA。
才19 分钟。如果加多线程，快点的 CPU， 例如 4 thread 个
就可以 5 分钟左右了。
我想要拼过这个速度恐怕很难了。
BTW, lcs code 是网上的改的。
发包子吧。
/* Dynamic Programming implementation of LCS problem */
#include
#include
#include
#include
#include
#include
/* Utility function to get max of 2 integers */
static inline int max(int a, int b)
{
return (a > b)? a : b;
}
unsigned char L[32][32];
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
static int lcs( char *X, char *Y, int m, int n )
{
int i, j;
/* Following steps build L[m+1][n+1] in bottom up fashion. Note
that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
for (i=0; i<=m; i++)
{
for (j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
/* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
return L[m][n];
}
/* Driver program to test above function */
int main()
{
char *A = malloc(31*4000);
char *B = malloc(31*100000);
int fa = open("a.txt", O_RDONLY);
int fb = open("b.txt", O_RDONLY);
int x, y;
char *la, *lb;
read(fa, A, 31*4000);
read(fb, B, 31*100000);
for (x = 0, la = A; x < 4000; x++, la+=31) {
int maxlen = 0;
char *mline;
for (y = 0, lb = B; y < 100000; y++, lb+=31) {
int l = lcs(la,lb,30,30);
if (l > maxlen) {
maxlen = l;
mline = lb;
}
}
printf("%.*s, %.*s, %d\n", 30, la, 30, mline, maxlen);
}
} |
S*A
发帖数: 7142 | 84 改了个多thread 的版本，我的笔记本只有两个 core，
缩短到 11 分钟啦。
3995 SKHJRJMOFCBCWQQWMRWQRVRYSKVMJZ, FSNDHCWYHQHWOARZSQMRVXRYSVRJSY, 15
1999 ROFOJBHHAXSDXIOMKKXIQSFSWCTCCN, YSLATSRFNOXOBHPSWXIXIYUAJQFCCI, 14
thread 140673519871744 end
3996 EGRBBDMMCTPHATHKKOZLYKILMJRRGK, LPGBBFMUCVPATROUYWAILJIWERFWIN, 14
3997 AAJOQYFTETTDDQSYNTPLCLLLQLIGYE, ZECJAQFTEYNXPKCELBABLLAMROHLEY, 14
3998 XBRUDOZWOTZFRDJZAOVWGMVZXYIECT, MBOQZYFQOLMZYVDZEVRGWTMVGXYYEJ, 14
3999 EFMVIENYDEMQEUUOTWHGBDYOOJERAP, YESVNTDQUUVFXTXRWJAWBYQOAUJCEK, 14
thread 140673511479040 end
real 11m13.356s
user 22m24.209s |
S*A
发帖数: 7142 | 85 这个是按照每行都是 30 个字符来算的，
如果平均字符长度只有 15，时间就要短很多：
1999 ROFOJBHHAXSDXIO, RSOJZBHYCOXUFDO, 8
thread 140559127881472 end
real 2m33.294s
user 5m4.036s
sys 0m0.283s |
t***q
发帖数: 418 | 86 Later on I found out, in my script, I used difflib.SequenceMatcher to do the
calculations. My friend used Levenshtein that algorithm which is faster.
I used Levenshtein in my script too, later, it runs faster too.
So maybe, two algorithms , one single calculation maybe 0.01 ms difference,
but times 400M, the time difference will be big.
The code:
import csv
import re
import difflib
import operator
import Levenshtein
a=[]
with open("/Users/file1.csv","rb") as f:
reader=csv.reader(f)
for row in reader:
a.append(row)
f.close()
b=[]
with open("/Users/file2.csv","rb") as g:
reader=csv.reader(g)
for row in reader:
b.append(row)
g.close()
for i in range(len(a)):
ff={}
for j in range(len(b)):
d=Levenshtein.ratio(a[i][0],b[j][0])
ff[b[j][0]]=d
print "%st%s" % (a[i][0],max(ff.iteritems(),key=operator.
itemgetter(1))[0]) |
t***q
发帖数: 418 | 87 My friend's code in R:
da1=read.csv(paste(filepath,"file1.csv",sep=""))
da2=read.csv(paste(filepath,"file2.csv",sep=""))
da1 <- t(da1)
da1 <- as.vector(da1)
da2 <- t(da2)
da2 <- as.vector(da2)
info <- matrix(NA,nrow=length(da1),ncol=40)
position <- 1:length(da2)
for(i in 1:length(da1))
{
a=levenshteinSim(da1[i],da2)
pos=position[a==max(a)]
temp=c(i,pos,max(a),da1[i],da2[pos])
info[i,1:length(temp)] <- temp
if(i %% 500 ==0)
cat("#")
} |
c****f
发帖数: 1102 | 88 楼主 我也无聊 写了一个go的
package main
import (
"fmt"
"io/ioutil"
"strings"
"sync"
"runtime"
"github.com/pmezard/go-difflib/difflib"
)
func worker(x string, y []string, wg *sync.WaitGroup) {
max, index := float64(0), 0
a := strings.Split(x, "")
for i, v := range y {
b := strings.Split(v, "")
sq := difflib.NewMatcher(a, b)
r := sq.Ratio()
if r > max {
max = r
index = i
}
}
fmt.Printf("%f similarity ratio, %s from a.txt, %s from b.txt\n", max, x
, y[index])
wg.Done()
}
func main() {
runtime.GOMAXPROCS(runtime.NumCPU())
a, _ := ioutil.ReadFile("a.txt")
b, _ := ioutil.ReadFile("b.txt")
al := strings.Split(string(a), "\n")
bl := strings.Split(string(b), "\n")
var wg sync.WaitGroup
for _, x := range al {
wg.Add(1)
go worker(x, bl, &wg)
}
wg.Wait()
}
output类似
0.400000 similarity ratio, WYZOZITKVXDQXMOJIEZNHHBZHOMNGC from a.txt,
YSREZZOWSVSYIYIQCZDIEOJEZJBIZG from b.txt
0.433333 similarity ratio, JCURHGKRLRZTNWOFRMKORDWNQLPLNT from a.txt,
JUPVHJDYRLZLQWOACRFNKOPOTBSIJP from b.txt
0.433333 similarity ratio, BHZHUVOMLGGXYUCPFYVDACQOEDPSRB from a.txt,
BZLCFYORYJVBBDKGUQAFCSDEIPDJYB from b.txt
0.400000 similarity ratio, AAVYDUPQNLNUOTNBWXHSXISOOSMGDM from a.txt,
SZRTTAAYTYDLCABAFEHRFIESMGMVTD from b.txt
0.400000 similarity ratio, YEVENHADQAMZKOHTYXTMZZAZNJKOUB from a.txt,
BEVGQGESNEZURGKOQMQGWPZDJNJWOT from b.txt
0.400000 similarity ratio, FNMWHWPGANKZPYWQCSPVRIYWHPRSPV from a.txt,
NMHAAABFWNKJIYVDJPQNCCSPSYFZXW from b.txt
0.400000 similarity ratio, RQBACRMORQXRVOXELCFSGAGNVEJAVQ from a.txt,
BCRJGTYGMNOUMPJMYXJOIEGAANRMPQ from b.txt
0.400000 similarity ratio, ISIJUCXQYHRCZIJQCUCZADMFAUKAGL from a.txt,
XSXHSODVVAZWEMRPCZZSJYOQXZAKGK from b.txt
0.400000 similarity ratio, BVFKWNLYSBGMRVCAUUNNLIMAMPMICY from a.txt,
NYSVUFMOMPERVJCVRIENZLFPYIPYEJ from b.txt
0.433333 similarity ratio, IXAJFXVGBHXGUVFJNCJWDMCOFHRQIZ from a.txt,
VGFJCJLVCHXYAVZKWJCRMZFHRGIZSV from b.txt
0.400000 similarity ratio, BKOOOIZRFHBFJJYQWWPEDGCEWQEOLJ from a.txt,
BHKIWBZMTFMJFSDGEFACEAQMXTBULI from b.txt
0.400000 similarity ratio, QHAIZOKUEVZPKBPEKOWEGMZSSCJPME from a.txt,
YOFKUMVSXPIKWJRHBPNEDMHZDPIDXX from b.txt
0.466667 similarity ratio, ULFDLMZWORXNLTMMLXHZENBBWMGCES from a.txt,
TDBLMYIWGMKTRPVXHNATRLXTHZNGEM from b.txt
0.433333 similarity ratio, QUYMDIRQVSIEXYXXCDFRQOWUEGPPNF from a.txt,
MUSDJQSOFMHKDZQVDESXDZROWGYZPJ from b.txt
我没分割b.txt 数据是由楼上某位同学的python脚本生成的 机器是maxbook air I5
2000 3000行 的结果是 4分03秒
./test 773.16s user 11.16s system 321% cpu 4:03.59 total
现在再跑4000 100000的数据 不知道要多久 |
S*A
发帖数: 7142 | 89 2kx3k vs 4k x 100k,
66 倍差别。
你的 go 要4个小时吧。
我的 C 代码比你的go快 12 倍。
假设机器是一样的 mba。
【在 c****f 的大作中提到】
: 楼主 我也无聊 写了一个go的
: package main
: import (
: "fmt"
: "io/ioutil"
: "strings"
: "sync"
: "runtime"
: "github.com/pmezard/go-difflib/difflib"
: )
|
S*A
发帖数: 7142 | 90 我还想到了一个更加优化的办法。
如果已经有很好的candidate，
那不够好的可以在lcs内部提前结束。
例如30 一个串，目前最好是20match
那么有10个不match就可以提前退出
lcs双循环了。不需要知道有多低，反正
用不上。
我断言那个C程序会远远超出其他语言
的实现。有java，scala同学要试验一吗？ |
|
|
c****f
发帖数: 1102 | 91 ./test 51217.24s user 246.40s system 360% cpu 3:58:09.98 total
的确跑了快4个小时...健身房回来刚跑完
但是这个是纯粹走concurrent的 没任何优化, 而且依赖那个difflib.SequenceMatcher
的算法的library,
我估计自己写可能会快很多
理论上compiled go不会比C慢那么多的
不过没这个时间去写那个算法了.
我是macbook air 13 i5的 4核心, 估计吧chrome都关掉会稍微快点 哈哈, |
z****e
发帖数: 54598 | 92 你这不是无聊么
基本上针对某个算法做的速度优化是毫无意义的
有这个功夫不如去写点app，没准还能撞个大运发笔财
【在 S*A 的大作中提到】
: 我还想到了一个更加优化的办法。
: 如果已经有很好的candidate，
: 那不够好的可以在lcs内部提前结束。
: 例如30 一个串，目前最好是20match
: 那么有10个不match就可以提前退出
: lcs双循环了。不需要知道有多低，反正
: 用不上。
: 我断言那个C程序会远远超出其他语言
: 的实现。有java，scala同学要试验一吗？
|
n*w
发帖数: 3393 | 93 如果无法做别的优化的话，我最近有个类似的微project。
用c# linq，逻辑写完后，加个".AsParallel()", 速度加快到大致原速度除以cpu core
数。
【在 p**r 的大作中提到】
: 上次用java大概是7年了，你问问其他人，我基本都用c#做事。
: 很多事情你还是多研究算法，逻辑吧，语言差别应该不大。
: 之前跑过类似数据量，改了逻辑之后，
: 从大概10几分钟降到几十ms，基本就是淘汰+预处理，
: 缺点就是不那么real time的
|
S*A
发帖数: 7142 | 94 有聊谁还来灌水啊。
你的倒序表不也是特定优化啊。
这个c程序不继续优化已经是目前
最好结果了。多线程版本我也有。
比点乘有意义多了。
【在 z****e 的大作中提到】
: 你这不是无聊么
: 基本上针对某个算法做的速度优化是毫无意义的
: 有这个功夫不如去写点app，没准还能撞个大运发笔财
|
z****e
发帖数: 54598 | 95 点乘应用范围广啊
写代码以解决问题为主要目标
别人做过的就不用再做了
尤其是开源的免费的已经有了的话
会抄就行了，做点有意义的
【在 S*A 的大作中提到】
: 有聊谁还来灌水啊。
: 你的倒序表不也是特定优化啊。
: 这个c程序不继续优化已经是目前
: 最好结果了。多线程版本我也有。
: 比点乘有意义多了。
|
S*A
发帖数: 7142 | 96 你可以试验一下嘛。我的c程序实现的
lcs源程序都在，你用go实现应该比c
代码还短。
我的基准是1个core的。如果那个go
是用了4个core那更慢。是 40倍不是
12倍。
SequenceMatcher
【在 c****f 的大作中提到】
: ./test 51217.24s user 246.40s system 360% cpu 3:58:09.98 total
: 的确跑了快4个小时...健身房回来刚跑完
: 但是这个是纯粹走concurrent的 没任何优化, 而且依赖那个difflib.SequenceMatcher
: 的算法的library,
: 我估计自己写可能会快很多
: 理论上compiled go不会比C慢那么多的
: 不过没这个时间去写那个算法了.
: 我是macbook air 13 i5的 4核心, 估计吧chrome都关掉会稍微快点 哈哈,
|
S*A
发帖数: 7142 | 97 都一样，那个lcs也是抄的。
要抄干嘛不抄个快的。
所以，解决这些首先应该看看问题
本质是不是用现有的问题可以解决
的。看看最优算法上限在哪里。
然后搞个差不多就完了。
c语言实现得当还是可以快很多的。
【在 z****e 的大作中提到】
: 点乘应用范围广啊
: 写代码以解决问题为主要目标
: 别人做过的就不用再做了
: 尤其是开源的免费的已经有了的话
: 会抄就行了，做点有意义的
|
S*A
发帖数: 7142 | 98
the
difflib.SequenceMatcher 是用 Python 实现的。
python-Levenshtein 那个使用 C 实现的。
最朴素的 levenshtein 的核心算法和 LCS 是一致的。
你把两个串的最长common sequence 挖掉，剩下的部分就是
最短 edit distance 的 edit script。这是同一个问题的
两个不同表述。
你公司的数据平均一行长度是多少？
那个 C 的程序应该是比你的 Python 版本快很多的。
【在 t***q 的大作中提到】
: Later on I found out, in my script, I used difflib.SequenceMatcher to do the
: calculations. My friend used Levenshtein that algorithm which is faster.
: I used Levenshtein in my script too, later, it runs faster too.
: So maybe, two algorithms , one single calculation maybe 0.01 ms difference,
: but times 400M, the time difference will be big.
: The code:
: import csv
: import re
: import difflib
: import operator
|
t***q
发帖数: 418 | 99 多谢你的回复，确实levenshtein 比diff.sequqncematcher要快不少。
我的数据主要是些电视剧，电影的titles,如 24 -01 - "2:00am-3:00am"
有一个netflix data,上面有一些titles,在一个master file 里， 也有些titles, 要
把netflix 的titles和master file里的titles 用algorithm match 起来。叫title
matching，主要是titles，在netflix里和master file里的形式可能不一样。如某个
title在netflix里是 the siege,在master file 里就是siege, the. 有时候，还有
typo之类的。
【在 S*A 的大作中提到】
:
: the
: difflib.SequenceMatcher 是用 Python 实现的。
: python-Levenshtein 那个使用 C 实现的。
: 最朴素的 levenshtein 的核心算法和 LCS 是一致的。
: 你把两个串的最长common sequence 挖掉，剩下的部分就是
: 最短 edit distance 的 edit script。这是同一个问题的
: 两个不同表述。
: 你公司的数据平均一行长度是多少？
: 那个 C 的程序应该是比你的 Python 版本快很多的。
|
Z**0
发帖数: 1119 | 100 How about the gist?
https://gist.github.com/ambv/1406554
using multiple threads & map-reduce idea? |
|
|
S*A
发帖数: 7142 | 101 这个不需要一下子上来就用 sequence matcher 的。
这个完全可以做 word based 的 title matching， 用很快的算法
把绝大多数没有共同单词的title先排除出去。剩下的一两个接近的再
用 sequence matcher. 尤其是有很多 title 是 exact match 的，这
时候根本不需要比较其他的 title。
我的感觉是针对你这个应用一定有可以快很多的办法。
【在 t***q 的大作中提到】
: 多谢你的回复，确实levenshtein 比diff.sequqncematcher要快不少。
: 我的数据主要是些电视剧，电影的titles,如 24 -01 - "2:00am-3:00am"
: 有一个netflix data,上面有一些titles,在一个master file 里， 也有些titles, 要
: 把netflix 的titles和master file里的titles 用algorithm match 起来。叫title
: matching，主要是titles，在netflix里和master file里的形式可能不一样。如某个
: title在netflix里是 the siege,在master file 里就是siege, the. 有时候，还有
: typo之类的。
|
z****e
发帖数: 54598 | 102 就是倒排表嘛
先根据context expand key terms
然后根据这个抓similarity
看来楼主做到了第一个大作业
【在 S*A 的大作中提到】
: 这个不需要一下子上来就用 sequence matcher 的。
: 这个完全可以做 word based 的 title matching， 用很快的算法
: 把绝大多数没有共同单词的title先排除出去。剩下的一两个接近的再
: 用 sequence matcher. 尤其是有很多 title 是 exact match 的，这
: 时候根本不需要比较其他的 title。
: 我的感觉是针对你这个应用一定有可以快很多的办法。
|
z****e
发帖数: 54598 | 103 找similarity最靠谱的算法就是倒排表
简单粗暴，而且效率很高，o(n)复杂度
预处理的话，老师应该上来就教这个才对
至于其他的，其实都是扯蛋
真正效率更高的，应该是bm25
那这个复杂得多，参数tune来tune去，麻烦
string那个东西可以不搞了，没啥意思，string都被搞烂了
text也都搞得差不多了，搞image和sound才有趣撒
sound好像难度也不太高，image比较有搞头
搞完这个，就去看wdong说的那些了 |
S*A
发帖数: 7142 | 104 你这个倒排表是如何处理 typo 的？
LZ这个我怀疑直接加个 exact match 的判断就
可以快很多。至于相似度， sequence match 是非常靠谱的。
复杂的情况，例如 DNA sequence matching， 这个是最靠谱
的。
【在 z****e 的大作中提到】
: 找similarity最靠谱的算法就是倒排表
: 简单粗暴，而且效率很高，o(n)复杂度
: 预处理的话，老师应该上来就教这个才对
: 至于其他的，其实都是扯蛋
: 真正效率更高的，应该是bm25
: 那这个复杂得多，参数tune来tune去，麻烦
: string那个东西可以不搞了，没啥意思，string都被搞烂了
: text也都搞得差不多了，搞image和sound才有趣撒
: sound好像难度也不太高，image比较有搞头
: 搞完这个，就去看wdong说的那些了
|
z****e
发帖数: 54598 | 105 不处理，管不了那么多
typo分两种
一种是写错了有意义，比如var给写成了val，那这个机器是没有办法的
另外一种是写错了无意义，那返回的结果相似度会很低，你可以判断
当相似度的值低于多少的时候，认定是typo，然后从字典中找到最类似的string
用tree结构可以比较快定位出来，这个其实是另外一个topic
【在 S*A 的大作中提到】
: 你这个倒排表是如何处理 typo 的？
: LZ这个我怀疑直接加个 exact match 的判断就
: 可以快很多。至于相似度， sequence match 是非常靠谱的。
: 复杂的情况，例如 DNA sequence matching， 这个是最靠谱
: 的。
|
S*A
发帖数: 7142 | 106 有 typo 也要能 match 上是原来 LZ 的要求。
用 sequence matcher 是可以允许 typo。
所以你不处理是不能满足要求的。
【在 z****e 的大作中提到】
: 不处理，管不了那么多
: typo分两种
: 一种是写错了有意义，比如var给写成了val，那这个机器是没有办法的
: 另外一种是写错了无意义，那返回的结果相似度会很低，你可以判断
: 当相似度的值低于多少的时候，认定是typo，然后从字典中找到最类似的string
: 用tree结构可以比较快定位出来，这个其实是另外一个topic
|
z****e
发帖数: 54598 | 107 单独做一个wrapper
当相似度低于多少时候再处理
把这个功能跟原功能分离
也便于维护
【在 S*A 的大作中提到】
: 有 typo 也要能 match 上是原来 LZ 的要求。
: 用 sequence matcher 是可以允许 typo。
: 所以你不处理是不能满足要求的。
|
b*******s
发帖数: 5216 | 108 Python 的GC设计得效率太低了
【在 z****e 的大作中提到】
: 不不
: python出了名的慢
: 解释器不行
: jvm明显快很多
|
