TEL:400-8793-956
当前位置:程序、服务器

如何提高比较大量字符串的速度

提问者:互联网网民 近期获赞:662 浏览人数:7776 发布时间:2020-12-09 11:27:41

问:补充数据链接:

候选:https:
//pan.baidu.com/s/1nvGWbrV bg_db:https : //pan.baidu.com/s/1sllFLAd
每个字符串的长度为23,只要该行的前20个字符,因为数据太大,我只传递了五分之一,众神可以挑战,有一个快速的代码可以粘贴,让小弟读一下,谢谢!
以下是形式问题:
我现在有两个字符串数组,分别称为候选人和bg_db,所有字符串长度均为20,每个字符串的每个字符只有四个可能的ATCG(是的!这是基因组序列!:
 
candidates = [
    'GGGAGCAGGCAAGGACTCTG',
    'GCTCGGGCTTGTCCACAGGA',
    '...',
    65
]
 
bg_db = [
    'CTGCTGACGGGTGACACCCA',
    'AGGAACTGGTGCTTGATGGC',
    '...',
    More, about a billion.
]
我的任务是在bg_db中查找所有小于或等于四个候选候选人差异的记录。
例如:
 
# The top one is candidate, which is a record of candidates
# 中间|代表相同,*代表不相同
The following record represents bg_db
 
A T C G A T C G A T C G A T C G A T C G
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | The difference is 0
A T C G A T C G A T C G A T C G A T C G
 
A T C G A T C G A T C G A T C G A T C G
* | | | | | | | | | | | | | | | | | | | | | | | | | | | | The difference is 1
T T C G A T C G A T C G A T C G A T C G
 
A T C G A T C G A T C G A T C G A T C G
* | | * | | | | | | | | | | | | | | | | | | | | | | | | | | The difference is 2
T T C G T T C G A T C G A T C G A T C G
 
A T C G A T C G A T C G A T C G A T C G
* | | * | | | | | | | | | | | | | * | | | | | | | | | | | The difference is 3
T T C G T T C G A T C C A T C G A T C G
 
A T C G A T C G A T C G A T C G A T C G
* | | * | | | | | | | | | | | | | * | | | * | | * | | | # The difference is 4
T T C G T T C G A T C C A T C A A T C G
我的问题是,如果我可以快速找到bg_db中每个候选项的差异小于4的所有记录。
如果使用暴力,请以Python为例:
 
def align(candidate, record_from_bg_db):
    mismatches = 0
    for i in range(20):
        if candidate[i] != record_from_bg_db[i]:
            mismatches += 1
            if mismatches >= 4:
                return False
    return True
 
candidate = 'GGGAGCAGGCAAGGACTCTG'
record_from_bg_db = 'CTGCTGACGGGTGACACCCA'
 
Align (candidate, record_from_bg_db) # about 1.24 microseconds
 
Total time:
 
10000000 * 1000000000 * 1.24 / 1000 / 1000 / 60 / 60 / 24 / 365
# = 393
10 million candidates and 1 billion bg_db records
It takes about 393 years.
6550
我的想法是bg_db是一个高度有序的字符串(具有固定的长度,每个字符四个可能的字符)。有什么算法可以使求职者快速比较所有bg_db,诸神,以寻求建议?
 
 
答:写思路
 
candidates = [
    'GGGAGCAGGCAAGGACTCTG',
    'GCTCGGGCTTGTCCACAGGA',
    '...',
    65
]
 
bg_db = [
    'CTGCTGACGGGTGACACCCA',
    'AGGAACTGGTGCTTGATGGC',
    '...',
    More, about a billion.
]
由于您的数据实际上很有特色,因此可以简化。
因为所有字符串的长度均为20个字符,并且全部由ATCG四个字符组成。然后可以将它们转换为整数以进行比较。
二进制表示如下
 
A  ==>  00
T  ==>  01
C  ==>  10
G  ==>  11
因为字符串的长度是固定的,所以每个字符可以用两位表示,因此每个字符串可以表示为一个。40位的整数。它可以表示为32+8也可以直接使用。64位整形。建议用C语言来做。
让我们谈论比较。
因为我想找到它。All records with a difference of less than or equal to 4 for each candidate in bg_db因此,一次只能做两个整数。^xor运算,结果There are no more than eight binaries with no more than eight binaries, which can only be divided into four groups at most.为可以满足要求(00 ^ 11 = 11,10 ^ 01 = 11)。
结果40每位分为20组,即最多只有一组。4每组是b01 b10 b11这三个值,其余全部是b00。
然后比较算法写得很好。
可以检索每个字节(四个组),其中几个用于三个非零值,以简要介绍整体比较结果。
因为每个字节只有一个256可能的值限定值是3^4=81种类,所以您可以存储结果并获取它们。
在这里,我们给出一个函数来获取结果中的几个非零组。
 
Generation of table median under *******************
  int i;
  for( i=0;i<256;++i){
    int t =0;
    t += (i&0x01 || i&0x02)?1:0;
    t += (i&0x04 || i&0x08)?1:0;
    t += (i&0x10 || i&0x20)?1:0;
    t += (i&0x40 || i&0x80)?1:0;
    printf("%d,",t);
    if(i%10 ==9){putchar('\n');}
  }
********************************************//
 
int table[] = {
0,1,1,1,1,2,2,2,1,2,
2,2,1,2,2,2,1,2,2,2,
2,3,3,3,2,3,3,3,2,3,
3,3,1,2,2,2,2,3,3,3,
2,3,3,3,2,3,3,3,1,2,
2,2,2,3,3,3,2,3,3,3,
2,3,3,3,1,2,2,2,2,3,
3,3,2,3,3,3,2,3,3,3,
2,3,3,3,3,4,4,4,3,4,
4,4,3,4,4,4,2,3,3,3,
3,4,4,4,3,4,4,4,3,4,
4,4,2,3,3,3,3,4,4,4,
3,4,4,4,3,4,4,4,1,2,
2,2,2,3,3,3,2,3,3,3,
2,3,3,3,2,3,3,3,3,4,
4,4,3,4,4,4,3,4,4,4,
2,3,3,3,3,4,4,4,3,4,
4,4,3,4,4,4,2,3,3,3,
3,4,4,4,3,4,4,4,3,4,
4,4,1,2,2,2,2,3,3,3,
2,3,3,3,2,3,3,3,2,3,
3,3,3,4,4,4,3,4,4,4,
3,4,4,4,2,3,3,3,3,4,
4,4,3,4,4,4,3,4,4,4,
2,3,3,3,3,4,4,4,3,4,
4,4,3,4,4,4
};
 
int getCount(uint64_t cmpresult)
{
    Uint8_t* Pb = & & cmpresult; // Here we assume that it is a small segment mode, and the previous comparison results are low by 40 bits.
    return table[pb[0]]+table[pb[1]]+table[pb[2]]+table[pb[3]]+table[pb[4]];
 
答:提供一种将四个字符简化为00、01、10、11的方法。
比较时,首先执行XOR,因此完全相同的字符变为00;不完全相同的是01、10或11。
那么每个相邻对的XOR结果为OR,因此00变为0、01、10或11变为1。最后,计算1的数目。因为它们是按位运算,所以它们理论上应该很快。
但是,如果我的C学会了炉渣,则无法发布代码。
 
答:思路如下:
首先:比较四个不同的数据,例如
* * TGACGGGTGACACCCA(删除字符串的四个位置中的字符),将字符的长度更改为16,与完全相同的字符串匹配,
将TGACGGGTGACACCCA保存为键值以及四个差异作为值,例如map。
第二:比较三个差异的数据
在上述基础上,将上述值与比较长度与3完全相同的字符串进行比较
上一篇: 为什么在Python判断变量类型时不推荐type方法
下一篇: 延迟和异步之间的区别