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

Answer 1

Je suis un idiot d'algorithme, mais il se trouve que j'ai des ressources informatiques disponibles, donc je vais suivre l'idée originale (flux informatique parallèle violent et sans cervelle) et faire l'exemple de la question :

run.py

from multiprocessing import Pool, cpu_count


def do_align(item):
    with open("bg_db.txt") as fh, open("result.txt", "a") as rh:
        db_line = fh.readline().strip()
        while db_line:
            counts = 0
            for i in [(i, j) for (i, j) in zip(db_line, item)]:
                if i[0] != i[1]:
                    counts += 1
                if counts >= 4:
                    break
            if counts < 4:
                rh.write("{}\n".format(db_line))
            db_line = fh.readline().strip()


def main():
    pool = Pool(cpu_count())
    with open("candidates.txt") as fh:
        pool.map(do_align, map(str.strip, fh))
    pool.close()
    pool.join()


if __name__ == "__main__":
    main()

Générez simplement des données ponctuelles

import random
import string


def id_generator(size=8, chars=string.ascii_letters + string.digits):
    return ''.join(random.choice(chars) for _ in range(size))


with open("candidates.txt", "w") as fh:
    for i in range(10000):
        fh.write("{}\n".format(id_generator(20, "ATCG")))

with open("bg_db.txt", "w") as fh:
    for i in range(1000000):
        fh.write("{}\n".format(id_generator(20, "ATCG")))

Eh bien, j'ai créé 10000 qui fonctionne candidates.txt et 1000000 qui fonctionne bg_db.txt
et je l'ai exécuté pour voir l'heure :

$time python run.py

real    15m45.445s
user    1362m41.712s
sys     1m12.099s

Les données réelles du sujet sont des dizaines de millions de lignes candidates.txt et des milliards de lignes bg_db.txt Une simple estimation du temps
16*1000/(60*24) = 11.11
est de 11 jours. utilisé la configuration du nœud

CPU Utilization:    1.0    0.0    98.9
user    sys    idle
Hardware
CPUs: 96 x 2.10 GHz
Memory (RAM): 1009.68 GB
Local Disk: Using 351.623 of 941.596 GB
Most Full Disk Partition: 53.5% used.

Cela prend vraiment beaucoup de temps et doit être optimisé de toute urgence

Answer 2

Basé sur l'idée de @武合之zon, utiliser le double de l'espace et utiliser 4 bits pour représenter quatre types de caractères peut simplifier la recherche ultérieure de numéros de caractères incohérents

Answer 3

Asseyez-vous et attendez que le maître apparaisse

Answer 4

L'idée est la suivante :
Premier : Par exemple, comparer 4 données différentes
**TGACGGTGTGACACCCA (supprimer des caractères à certaines 4 positions de la chaîne), changer la longueur des caractères en 16, Faites correspondre exactement la même chaîne
Utilisez une carte ou similaire pour enregistrer TGACGGGTGACACCCA comme valeur clé et les quatre différences comme valeurs

Deuxième : Comparez 3 données différentes
Sur la base de ce qui précède, comparez les valeurs ci-dessus pour comparer la même chaîne d'une longueur de 3

Et ainsi de suite

Answer 5

Vous pouvez en apprendre davantage sur le calcul parallèle tel que CUDA. L'amélioration des performances de votre grand nombre d'opérations simples répétées est très évidente

.

Answer 6

基本算法的复杂度是 O(M*N*c)
M =candidates数量
N = bg_db 数量

比较操作看做常数时间


优化：
    1 把20个字符分为4组 每组5个 ，每组可能的类型有 4^5=1024种 。把bg_db 先按照 第一个组 聚合 ，再按照第二个组聚合...构成一个4层的树结构
    2 建立 1024*1024 的表 表示 两个5个字符的串的差异数 内存 1MB
    2 匹配的时候，如果第一个组差异已经超过4个了，就不需要看它的子节点了，可以立刻排除大量节点

每组的长度也可以不确定，最好第一组有足够的区分性，这样可以一下子排除大量数据

Answer 7

Donnez une idée pour simplifier les quatre caractères en 00, 01, 10, 11.
Lors de la comparaison, effectuez d'abord XOR, de sorte que s'ils sont identiques, ils deviendront 00 ; s'ils ne sont pas identiques, ils seront 01, 10 ou 11.
Ensuite, effectuez OR sur chaque paire adjacente du résultat XOR, de sorte que 00 devienne 0 et 01, 10 ou 11 devienne 1. Comptez enfin le nombre de 1. Puisqu’il s’agit toutes d’opérations binaires, elles devraient en théorie être très rapides.

Mais j'ai du mal à apprendre le C, donc je ne peux pas publier le code.