求教字符串快速比较问题

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
    

复制代码

HyryStudio

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

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

HyryStudio

回复 23# hulnglei

用树写其实也不难，不过最好还是用C语言写，才能够达到飞快，不过这个比较费时间了。我想了一个很好的办法，你看是否可行：

假设A,B两个组，每个180万个长度为31的每位有ATCG等四种可能的字符串。
把B组做成一个集合set，或者字典，关键字是字符串，值是它们的名字。

对于A组中的每一个字符串，在B中找是否有和它相差一个元素的。
由于字典只能找完全一样的，因此具体这样做：

因为你只找相差一个字符的，因此对于字符串中的每个字符，都修改为其它三个，这样31*3 = 93，也就是每个字符串搜索93次。也就是穷举和此字符串相差一个的所有可能情况，然后都到字典中去找：
例如对于

AC....
搜索
TC...., CC..., GC..., AA..., AT..., AG...,


这样搜索空间从180万*180万降低到180万*93，应该能在有限的时间之内完成。

另外，先用2个32位的整数对数据进行编码再做成字典的话，能够节省不少内存。不过这一步不做也可，只要你内存足够大。

HyryStudio

回复 24# HyryStudio

用Python写了一个用搜索树实现的，结果发现当树很平衡很大时，每个字符串的搜索量基本上和93差不了多少。穷举法对于Python来说还是最快的，因为dict是C语言级别实现的。