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

Answer 1

Saya seorang yang bodoh algoritma, tetapi saya kebetulan mempunyai sumber pengkomputeran yang tersedia, jadi saya akan mengikuti idea asal (aliran pengkomputeran selari tanpa otak yang ganas) dan melakukan contoh soalan:

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()

Hanya jana data mata

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")))

Nah, saya mencipta 10000 yang berfungsi candidates.txt dan 1000000 yang berfungsi bg_db.txt
dan menjalankannya untuk melihat masa:

$time python run.py

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

Data sebenar subjek ialah berpuluh juta baris candidates.txt dan berbilion baris bg_db.txt Anggaran mudah masa
16*1000/(60*24) = 11.11
ialah 11 hari menggunakan konfigurasi Nod

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.

Ia benar-benar mengambil masa yang lama dan memerlukan pengoptimuman segera

Answer 2

Berdasarkan idea @武合之zon, menggunakan dua kali ganda ruang dan menggunakan 4 bit untuk mewakili empat jenis aksara boleh memudahkan carian seterusnya untuk nombor aksara yang tidak konsisten

Answer 3

Duduk dan tunggu tuannya muncul

Answer 4

Ideanya adalah seperti berikut:
Pertama: Contohnya, bandingkan 4 data berbeza
**TGACGGGTGACACCCA (padam aksara pada 4 kedudukan tertentu rentetan), tukar panjang aksara kepada 16, Padankan rentetan yang sama
Gunakan peta atau seumpamanya untuk menyimpan TGACGGGTGACACCCA sebagai nilai utama dan empat perbezaan sebagai nilai

Kedua: Bandingkan 3 data berbeza
Berdasarkan perkara di atas, bandingkan nilai di atas untuk membandingkan rentetan yang sama dengan panjang 3

Dan seterusnya

Answer 5

Anda boleh belajar tentang pengkomputeran selari seperti CUDA Peningkatan prestasi bilangan besar operasi mudah berulang anda sangat jelas

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

Berikan idea untuk memudahkan empat aksara kepada 00, 01, 10, 11.
Apabila membandingkan, lakukan XOR terlebih dahulu, supaya jika sama, ia akan menjadi 00; jika tidak sama, ia akan menjadi 01, 10 atau 11.
Kemudian lakukan OR pada setiap pasangan bersebelahan hasil XOR, supaya 00 akan menjadi 0, dan 01, 10 atau 11 akan menjadi 1. Akhir sekali kira nombor 1. Memandangkan kesemuanya adalah operasi kecil, ia sepatutnya pantas secara teori.

Tetapi saya sangat mahir dalam mempelajari C, jadi saya tidak dapat menghantar kod tersebut.