求教字符串快速比较问题

HyryStudio

回复 1# hulnglei

这种运算应该用C语言写一个扩展然后用Python调用。

如果非要用Python写，可以如下优化：

如果大多数比较都不成功，即大多数都相差不止一个或者相同的话，可以先比较，只有成功之后再找出那个不同的元素：

下面的compare函数当找到两个不同时立即返回，可以提高比较速度。

1. from itertools import izip
   
2. def compare(a, b):
   
3.     count = 0
   
4.     for x,y in izip(a,b):
   
5.         if x!=y:
   
6.             count += 1
   
7.             if count > 1: return False
   
8.     if count == 1: return True
   
9.     return False
   

复制代码

另外可考虑用Psyco加速。

或者同时找到不同的元素，因为只有一个不同，因此不需要用列表保存：

1. def compare(a, b):
   
2.     count = 0
   
3.    
   
4.     for x,y in izip(a,b):
   
5.         if x!=y:
   
6.             dif1 = x
   
7.             dif2 = y
   
8.             if count == 1: return None
   
9.             count += 1
   
10.     if count == 1: return dif1,dif2
    
11.     return None
    

复制代码

luffy.deng

回复  t6760915


我的重点还是在比较。两个文件其实是从一个文件里面分离的，每一个序列的名字都是不同的。序列也是要比较，只能有1个字符的不同 ...
hulnglei 发表于 2010-06-01 19:03

两个文件如果需要按字符串名称对应的话，生成两个字典就可以了，
逐个比较很慢么？比如这样

1. def cmp(ss,ds):
   
2.     n= 31
   
3.     res=0
   
4.     while n>0 :
   
5.         if ss[n-1:n] != ds[n-1:n]:
   
6.             res+=1
   
7.         if res>1:
   
8.             return False            
   
9.         n-=1
   
10.      if res == 0:
    
11.         return False
    
12.      return True

复制代码

luffy.deng

我用两个完全一样的字符串测试了一下（这应该是最差的情况），循环一百万次 需要3分钟。你为何非得纠结于如何字符串如何比较？瓶颈根本就不在这里。

1. 
   
2. s1 ='AATTCTAACATGAAAGTAGGAAAGATGTCAC'
   
3. s2 ='AATTCTAACATGAAAGTAGGAAAGATGTCAC'
   
4. def cmp(ss,ds):
   
5.     n= 31
   
6.     res=0
   
7.     while n>0 :
   
8.         if ss[n-1:n] != ds[n-1:n]:
   
9.             res+=1
   
10.         if res>1:
    
11.             return False            
    
12.         n-=1
    
13.     if res ==0:
    
14.         return False
    
15.     return True
    
16. 
    
17. count =1000000
    
18. while count:
    
19.     print cmp(s1,s2)
    
20.     count-=1

复制代码

hulnglei

回复 11# HyryStudio


   对对对！多谢！没想到可以先比。至于C语言加速我不会啊！呵呵!我昨晚试了下5楼大虾的代码。11个小时就可以算1/4了 本来已经很惊讶，不过我的数据只有极少数的字符串的相同的。所以。。。。。

hulnglei

回复 13# luffy.deng


  多谢luffy.deng 这就可以更加加速了。呵呵！主要我不知道该在哪方面修改脚本?而且计较次数比较多，两个文件都有1,800,000个项。这样比较的次数就太多了。以后可能还要修改下计算更多！

luffy.deng

回复 15# hulnglei
即使是180万次  我在一台奔4单核3GHz上也不过跑了6分20秒。所以字符串比较不是瓶颈 ，逐个比较完全就可以。

hulnglei

回复  hulnglei
即使是180万次  我在一台奔4单核3GHz上也不过跑了6分20秒。所以字符串比较不是瓶颈 ，逐个 ...
luffy.deng 发表于 2010-06-02 10:54

   我的意思的1,800,000*1,800,000次比较。 不过有你的那种方法就不存在这个问题了。现在运算速度已经很满意了。谢谢你和上面的各位大虾！特别是t6760915 那么长的代码。学到了不少。

t6760915

哈，不客气

HyryStudio

回复 10# hulnglei
如果你希望在100万个和100万个之间任何一对进行比较的话，需要考虑一下算法。例如可以将其中的一组建立一棵树，字符串的每个字符是一个节点，它的子节点是下一个字符，因此树的深度是字符串的长度。然后在此树中对另外一组的每个字符串进行搜索，当发现有两个节点不同时就可以停止搜索。这时可以省略后续所有节点的搜索，应该可以成数量级的加快计算速度。

如果你的字符串中的字符只有ATCG四个字符的话，并且长度是31的话，可以考虑使用两个32bit的长整型数保存其状态。这样可以通过异或位操作快速比较，当然还需要一个数比特1个数的函数，这些在C语言级别做的话应该是非常快的。

Kabie

呃……要n^2的比较啊。。。怪不得

这个可能还是写个hash好点。。。

另外我看你那个数据怎么有个是30的。。。。