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

Answer 1

演算法白痴一個, 不過剛好手上有可以用的計算資源, 就按照原來的思路(暴力無腦並行計算流)做一下題主這個例子:

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

簡單先生成點數據

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

嗯, 造了10000行的candidates.txt和1000000行的bg_db.txt
運行看下時間:

$time python run.py

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

題主實際的資料是千萬行的candidates.txt和十億行的bg_db.txt, 簡單估算下時間candidates.txt和十亿行的bg_db.txt, 简单估算下时间
16*1000/(60*24) = 11.1116*1000/( 60*24) = 11.11
也就是11天, 這是我用的一個計算節點的設定

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.

時間確實好長, 急需神優化

Answer 2

基於@烏合之眾 的思路，多用一倍空間用4個位表示四種字符，可以簡化後面不一致字符個數的查找

Answer 3

坐等高手出現

Answer 4

想法如下:
第一:例如對比4個差異的資料
**TGACGGGTGACACCCA(刪除字串某4個位置的字元),將字元長度變為16,符合完全相同的字串
用map之類的保存TGACGGGTGACACCCA為key值,差異的四個作為values值

第二:對比3個差異的資料
在上述基礎的上,進行對比上述的values值為比較長度為3完全相同的字串

以此類推

Answer 5

可以了解CUDA等並行計算，你這種大量重複簡單的運算效能提升非常明顯

Answer 6

雷雷

Answer 7

提供一個思路，把四個字元簡化成 00, 01, 10, 11。
比較的時候先執行 XOR，這樣完全相同的就會變成 00；不完全相同的則是 01, 10或 11。
接著再對XOR的結果每相鄰的pair進行 OR，這樣 00 會變成0， 01，10或11就變成1。最後統計 1 的數量。由於都是位元運算，理論上應該很快。

不過我的C學得渣，程式碼就不能貼出來了。