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

Answer 1

Tulis idea

candidates = [
    'GGGAGCAGGCAAGGACTCTG',
    'GCTCGGGCTTGTCCACAGGA',
    '...',
    # 被你看出来啦，这些其实人类基因的片段
]

bg_db = [
    'CTGCTGACGGGTGACACCCA',
    'AGGAACTGGTGCTTGATGGC',
    '...',
    # 这个更多，有十亿左右
]

Oleh kerana data anda sebenarnya sangat unik, ia boleh diselaraskan di sini.
Kerana semua rentetan panjangnya 20 aksara dan terdiri daripada ATCG empat aksara. Kemudian mereka boleh ditukar kepada integer untuk perbandingan.
Perwakilan binari adalah seperti berikut

A  ==>  00
T  ==>  01
C  ==>  10
G  ==>  11

Oleh kerana panjang rentetan adalah tetap dan setiap aksara boleh diwakili oleh 2 bit, setiap rentetan boleh diwakili sebagai 40 integer bit. Ia boleh dinyatakan dalam bentuk 32+8, atau anda boleh terus menggunakan 64 membentuk bit. Adalah disyorkan untuk menggunakan bahasa C untuk melakukan ini.

Mari kita bercakap tentang perbandingan.
Kerana kita perlu mencari 每一个candidate在bg_db中与之差异小于等于4的所有记录, jadi selagi kita melakukan operasi ^ XOR bitwise pada dua integer, hasil 二进制中1不超过8个,且这不超过8个1最多只能分为4个组 mungkin memenuhi keperluan (00^11 =11 ,10^01=11).
Bahagikan 40 bit hasil kepada 20 kumpulan, iaitu, terdapat paling banyak 4 kumpulan dengan tiga nilai b01 b10 b11 dan selebihnya semuanya b00 .
Kemudian algoritma perbandingan adalah mudah untuk ditulis.
Anda boleh mendapatkan beberapa kumpulan tiga nilai bukan sifar untuk setiap bait (empat kumpulan) untuk mendapatkan secara ringkas hasil perbandingan keseluruhan.
Oleh kerana hanya terdapat 256 nilai yang mungkin untuk setiap bait, dan hanya terdapat 3^4=81 jenis nilai yang layak ​​, hasilnya boleh disimpan dahulu dan kemudian diambil semula.
Berikut adalah fungsi untuk mendapatkan bilangan kumpulan bukan sifar yang terdapat dalam keputusan.

/*****************下面table中值的生成******//**
  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;    // 这里假设是小段模式，且之前比较结果是存在低40位
    return table[pb[0]]+table[pb[1]]+table[pb[2]]+table[pb[3]]+table[pb[4]];
}

Answer 2

Pertama sekali, anggaran masa anda adalah salah sama sekali Pemprosesan data berskala besar ini perlu menjalankan puluhan ribu item dan bertahan selama lebih daripada sepuluh saat sebelum ia boleh digunakan untuk pendaraban untuk mengira jumlah masa. Jika hanya satu item dikira, ini Masa adalah hampir semua overhed proses permulaan, bukannya overhed IO dan CPU kritikal

Teks berikut

Empat kemungkinan ACTG adalah bersamaan dengan 2 bit Terlalu membazir untuk menggunakan satu aksara untuk mewakili satu kedudukan gen dan boleh memegang 4 kedudukan gen

Walaupun anda tidak menggunakan sebarang algoritma dan hanya menulis 20 gen anda ke dalam bentuk binari, anda boleh menjimatkan masa 5 kali ganda

Selain itu, selepas gelung 20 kali, bilangan arahan CPU ialah 20*n, dan n dianggarkan sekurang-kurangnya 3. Tetapi untuk binari, operasi XOR untuk perbandingan adalah secara langsung arahan CPU, dan bilangan arahan ialah 1

Answer 3

Saya tidak tahu banyak tentang algoritma, tetapi berdasarkan pengalaman, algoritma yang kompleks mengambil masa yang lebih lama dan tidak secepat algoritma yang mudah dan kasar ini

Anda boleh mempertimbangkan berbilang benang dan pengelompokan untuk memproses data

Nampaknya jarak Hamming juga boleh dikira

Answer 4

Juga tiada algoritma digunakan, penyelesaian kekerasan, ditulis dalam C

Pada mesin saya (CPU: Core 2 Duo E7500, RAM: 4G, OS: Fedora 19), keputusan ujian

candidates    bg.db        cost
10000    1000000    318758165微秒
500      1000000    14950302微秒 

Jika anda beralih kepada CPU 24-teras subjek, prestasi akan dipertingkatkan sebanyak 20 kali, dan kemudian menambah 48 mesin untuk beroperasi bersama-sama akan mengambil masa 15 saat, dan masa akan menjadi
10000000. * 1000000000 / 500 / 1000000 * 15 / 20 / 48 / 3600 / 24 = 3.616898 hari

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <sys/time.h>

#define START_CC(flag)  \
    struct timeval st_##flag##_beg; \
    gettimeofday(&st_##flag##_beg, 0)

#define STOP_CC(flag)   \
    struct timeval st_##flag##_end; \
    gettimeofday(&st_##flag##_end, 0)

#define PRINT_CC(flag)  \
    double cost_##flag = 0.0L; \
    cost_##flag = (double)(st_##flag##_end.tv_sec - st_##flag##_beg.tv_sec); \
    cost_##flag = cost_##flag * 1000000L + (double)(st_##flag##_end.tv_usec - st_##flag##_beg.tv_usec);    \
    printf(#flag" cost time %.6lf microsecond.\n", cost_##flag);

#define GENEORDER_CODE_LENGTH 20 + 1

typedef struct GeneOrder
{
    char code[GENEORDER_CODE_LENGTH];
}GeneOrder, *GeneOrderPtr;

typedef struct GOArray
{
    size_t          capacity;
    size_t          length;
    GeneOrderPtr    data;
}GOArray;

GOArray createGOAarray(size_t capacity)
{
    GOArray goa;

    goa.capacity    = capacity;
    goa.length      = 0;
    goa.data        = (GeneOrderPtr)malloc(capacity * sizeof(GeneOrder));

    return goa;
}

void destroyGOArray(GOArray* goa)
{
    if (goa->capacity > 0) {
        free(goa->data);
    }
}

bool readGOFile(char const *file, GOArray *goarray)
{
    FILE* fp = NULL;

    if ((fp = fopen(file, "r+")) == NULL) {
        return false;
    }

    char buff[64];

    while (fgets(buff, 64, fp) != NULL) {
        if (goarray->length < goarray->capacity) {
            memcpy(goarray->data[goarray->length].code,
                buff,
                GENEORDER_CODE_LENGTH * sizeof(char)
            );
            goarray->data[goarray->length].code[GENEORDER_CODE_LENGTH - 1] = '
gcc -Wall -Wextra -o ccs main.c -std=c99 -Os && ./ccs candidate.list bg.db
';
            goarray->length ++;
        } else {
            fclose(fp);
            return true;
        }
    }

    fclose(fp);
    return true;
}

int main(int argc, char* argv[])
{
    (void)argc;

    GOArray condgo  = createGOAarray(10000);
    GOArray bggo    = createGOAarray(1000000);

    printf("loading ...\n");

    START_CC(loading);
    if (!readGOFile(argv[1], &condgo) || !readGOFile(argv[2], &bggo)) {
        destroyGOArray(&condgo);
        destroyGOArray(&bggo);
        return -1;
    }
    STOP_CC(loading);
    PRINT_CC(loading);


    int count = 0;

    START_CC(compare);
    for (size_t i = 0;i < 500;i ++) {
        const GeneOrderPtr gop = condgo.data + i;
        for (size_t j = 0;j < bggo.length;j ++) {
            const GeneOrderPtr inner_gop = bggo.data + j;
            int inner_count = 0;

            for (size_t k = 0;k < 20;k ++) {
                if (gop->code[k] != inner_gop->code[k]) {
                    if (++inner_count > 4) {
                        break;
                    }
                }
            }

            if (inner_count <= 4) {
            #ifdef DBGPRINT
                printf("%d %s - %s\n", i, gop->code, inner_gop->code);
            #endif
                count++;
            }
        }
    }
    STOP_CC(compare);
    PRINT_CC(compare);

    printf("result = %d\n", count);

    destroyGOArray(&condgo);
    destroyGOArray(&bggo);

    return 0;
}

Kompilasi parameter & jalankan

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <sys/time.h>
#include <pthread.h>

#define START_CC(flag)              \
    struct timeval st_##flag##_beg; \
    gettimeofday(&st_##flag##_beg, 0)

#define STOP_CC(flag)               \
    struct timeval st_##flag##_end; \
    gettimeofday(&st_##flag##_end, 0)

#define PRINT_CC(flag)                                                                                  \
    double cost_##flag = 0.0L;                                                                          \
    cost_##flag = (double)(st_##flag##_end.tv_sec - st_##flag##_beg.tv_sec);                            \
    cost_##flag = cost_##flag * 1000000L + (double)(st_##flag##_end.tv_usec - st_##flag##_beg.tv_usec); \
    printf(#flag " cost time %.6lf microsecond.\n", cost_##flag);

#define GENEORDER_CODE_LENGTH 20 + 1

typedef struct GeneOrder {
    char code[GENEORDER_CODE_LENGTH];
} GeneOrder, *GeneOrderPtr;

typedef struct GOArray {
    size_t capacity;
    size_t length;
    GeneOrderPtr data;
} GOArray;

GOArray createGOAarray(size_t capacity)
{
    GOArray goa;

    goa.capacity = capacity;
    goa.length = 0;
    goa.data = (GeneOrderPtr)malloc(capacity * sizeof(GeneOrder));

    return goa;
}

void destroyGOArray(GOArray* goa)
{
    if (goa->capacity > 0) {
        free(goa->data);
    }
}

bool readGOFile(char const* file, GOArray* goarray)
{
    FILE* fp = NULL;

    if ((fp = fopen(file, "r+")) == NULL) {
        return false;
    }

    char buff[64];

    while (fgets(buff, 64, fp) != NULL) {
        if (goarray->length < goarray->capacity) {
            memcpy(goarray->data[goarray->length].code, buff,
                GENEORDER_CODE_LENGTH * sizeof(char));
            goarray->data[goarray->length].code[GENEORDER_CODE_LENGTH - 1] = '
gcc -Wall -Wextra -o ccs main.c -std=c99 -O3 -lpthread && ./ccs candidate.list bg.db
';
            goarray->length++;
        }
        else {
            fclose(fp);
            return true;
        }
    }

    fclose(fp);
    return true;
}

typedef struct ProcessST {
    GOArray* pcond;
    GOArray* pbg;
    size_t beg;
    size_t end; // [beg, end)
} ProcessST;

void* processThread(void* parg)
{
    ProcessST* ppst = (ProcessST*)parg;
    GOArray* pcond = ppst->pcond;
    GOArray* pbg = ppst->pbg;
    int count = 0;

    for (size_t i = ppst->beg; i < ppst->end; i++) {
        const GeneOrderPtr gop = pcond->data + i;
        for (size_t j = 0; j < pbg->length; j++) {
            const GeneOrderPtr inner_gop = pbg->data + j;
            int inner_count = 0;

            for (size_t k = 0; k < 20; k++) {
                if (gop->code[k] != inner_gop->code[k]) {
                    if (++inner_count > 4) {
                        break;
                    }
                }
            }

            if (inner_count <= 4) {
#ifdef DBGPRINT
                printf("%d %s - %s\n", i, gop->code, inner_gop->code);
#endif
                count++;
            }
        }
    }

    return (void*)count;
}

int main(int argc, char* argv[])
{
    (void)argc;

    GOArray condgo = createGOAarray(10000);
    GOArray bggo = createGOAarray(1000000);

    printf("loading ...\n");

    START_CC(loading);
    if (!readGOFile(argv[1], &condgo) || !readGOFile(argv[2], &bggo)) {
        destroyGOArray(&condgo);
        destroyGOArray(&bggo);
        return -1;
    }
    STOP_CC(loading);
    PRINT_CC(loading);

    size_t range[] = { 0, 250, 500 };
    pthread_t thr[2] = { 0 };
    ProcessST pst[2];

    START_CC(compare);

    for (size_t i = 0; i < 2; i++) {
        pst[i].pcond = &condgo;
        pst[i].pbg = &bggo;
        pst[i].beg = range[i];
        pst[i].end = range[i + 1];
        pthread_create(&thr[i], NULL, processThread, &pst[i]);
    }

    int count = 0;
    int* ret = NULL;

    for (size_t i = 0; i < 2; i++) {
        pthread_join(thr[i], (void**)&ret);
        count += (int)ret;
    }

    STOP_CC(compare);
    PRINT_CC(compare);

    printf("result = %d\n", count);

    destroyGOArray(&condgo);
    destroyGOArray(&bggo);

    return 0;
}

Jika anda menukarnya kepada berbilang benang, kelajuannya akan menjadi lebih pantas Pada mesin saya, saya menukarnya kepada 2 benang dan hanya menggunakan 500条candidates untuk menguji kelajuannya bilangan utas ditingkatkan kepada 9040257微秒, prestasi akan bertambah baik. Ia tidak begitu besar, tetapi CPU yang lebih baharu mempunyai teknologi hyper-threading, dan kelajuan dijangka lebih baik. . . 4 rrreee

Kompil dan uji

rrreee

Answer 5

Maaf, saya nampak orang lain membalas hari ini.
Melihat soalan itu dengan teliti, saya menyedari bahawa saya fikir ia hanya perlawanan.
Jadi saya mencadangkan untuk menggunakan ac automaton.

Tetapi tujuan soalan adalah untuk mencari perbezaan dalam urutan.
Ini adalah untuk mencari jarak edit antara keduanya.
wiki: Edit Jarak
wiki: Jarak Ravenstein

Semasa saya menggunakan OJ, saya menggunakan DP (pengaturcaraan dinamik) untuk mencari bilangan pengeditan minimum untuk menukar rentetan kepada rentetan lain.

for(i:0->len)
    for(j:0->len)
        str1[i]==str2[j] ? cost=0 : cost=1
        dp[i,j]=min(
            dp[i-1, j  ] + 1,     // 刪除
            dp[i  , j-1] + 1,     // 插入
            dp[i-1, j-1] + cost   // 替換
        )

Contohnya:

str1    "abcdef"
str2    "acddff"

str2 ditukar kepada str1

Sisipkan b Kira sekali
Padam d Kira sekali
Ubah suai f Kira sekali

Untuk jujukan gen ATCG subjek, adakah anda hanya perlu mencari yang diubah suai?
Namun, bagaimanakah ia harus dikira seperti ini
ATCGATCG
TCGATCGA
?

Jika anda hanya menemui pengubahsuaian, cuma bandingkan str1[i] dan str2[i] secara terus.

for(i:0->len)
if(str1[i]!=str2[i] )++count;

Diinspirasikan oleh @rockford.
Kami boleh praproses data mentah.

Rentetan dalam calon
GGGAGCAGGCAAGGACTCTG
A5 T2 C4 G9

Data tambahan selepas memproses A5 T2 C4 G9

String dalam bg_db
CTGCTGACGGGTGACACCCA
A4 T3 C7 G6

Data tambahan selepas memproses A4 T3 C7 G6

A5 -> A4 direkodkan sebagai -1
T2 -> T3 direkodkan sebagai +1
C4 -> -3

Jelas sekali A hanya boleh menjadi TCG jika diubah suai.

Begitu juga, kita hanya perlu mengira semua + atau semua -
untuk mengetahui sekurang-kurangnya berapa banyak perbezaan yang mereka ada.
Sesuatu yang lebih besar daripada 4 tidak perlu dibandingkan.

Dengan terlebih dahulu membandingkan data tambahan yang dipraproses, dan kemudian melakukan perbandingan melalui algoritma perbandingan tunggal.

(Bekerja lebih masa pada hari Sabtu -ing, tulis selepas keluar kerja)

Answer 6

Tugas individu anda ditentukan untuk menghantar tugasan ini kepada pekerja.
Malah, ia adalah bersamaan dengan anda mempunyai [a, b] dan [c, d] untuk dibandingkan, tugas anda ialah

1. [a, c]

2. [a, d]

3. [b, c]

4. [b, d]

Jika anda membuat siri secara serentak, masa yang anda perlukan ialah 4 * masa tunggal
Jika anda mempunyai 4 CPU atau 4 mesin secara selari, masa anda akan menjadi hampir masa tunggal

Jadi pengiraan seperti genom pada asasnya dilakukan menggunakan tugas selari berbilang teras pada mesin berskala besar Pada asasnya, prinsip rujukan adalah prinsip kertas Google MapReduce

Answer 7

Saya tidak mahir dalam algoritma, tetapi dengan jumlah data yang besar seperti anda, pastinya tidak mungkin untuk membandingkannya dengan satu komputer Untuk tugasan data intensif CPU seperti anda, saya bersetuju dengan apa yang orang lain katakan tentang penggunaan kaedah kluster atau berbilang proses untuk mengira Iaitu, kami menggunakan model pengurangan peta untuk mengira
pemetaan anda mula-mula memetakan setiap calon anda kepada bg_db satu demi satu untuk membentuk struktur data seperti ini. >(candidates,bg_db) ke dalam baris gilir dan kemudian menyerahkannya kepada pelayan yang berbeza , setiap pelayan menggunakan berbilang proses untuk mengira, ini adalah satu-satunya cara, tetapi volum data anda terlalu besar, cari cara untuk memperuntukkan tugas anda dan mengira secara selari. ,

Answer 8

Anda boleh cuba menggunakan pokok kamus untuk menyimpan semua rentetan. Kemudian anda boleh menggunakan kaedah melintasi pokok kamus apabila membuat pertanyaan.
Apabila melintasi pokok, anda boleh mengekalkan jujukan nod semasa Jujukan ini menyimpan bilangan ketidakpadanan antara nod yang dilalui dan nod yang sepadan.
Apabila melintasi nod seterusnya, cuba turunkan semua nod dalam urutan semasa dan bentuk urutan nod baharu.
Kelebihannya ialah bit semasa banyak rentetan boleh dibandingkan bersama, yang boleh menjimatkan sedikit masa. Oleh kerana tidak banyak pilihan untuk setiap kedudukan dan ketidakpadanan tidak besar, tidak perlu ada pengembangan yang berlebihan bagi jujukan nod semasa. (Ini adalah tekaan... Saya belum mengesahkannya dengan teliti...)

def match(candidate, root):
  nset = [[],[]]
  currentId = 0
  nset[currentId].append((root, 0))
  for ch in candidate:
    nextId = 1 - currentId
    for item in nset[currentId]:
      node, mismatch = item
      for nx in node.child:
        if nx.key == ch:
          nset[nextId].append((nx, mismatch))
        else:
          if mismatch:
            nset[nextId].append((nx, mismatch - 1))
    nset[currentId].clear()
    currentId = 1 - currentId
  return nset[currentId]

Kod di atas adalah idea yang kasar. Ia akan menjadi lebih cepat jika ditulis dalam C++.
Seluruh proses boleh dilakukan menggunakan kluster untuk pengkomputeran teragih.

Answer 9

Secara visual penyoal tidak mempunyai berbilang mesin untuk dia mengira
Saya mempunyai idea mudah untuk mengira jumlah nombor abjad setiap rentetan (A:0,T:1,C:2,G: 3), Mula-mula hitung perbezaan antara jumlah ordinal dua rentetan Maksimum tidak boleh melebihi 12. Empat A menjadi empat G. Jika bezanya kurang daripada 12, maka prosesnya adalah idea kasar berat tertentu boleh Dengan tetapan tambahan, secara teorinya boleh menjadi lebih cepat.
Terdapat algoritma lain yang mengira jarak suntingan rentetan (bilangan minimum suntingan untuk menambah, memadam dan mengubah suai satu rentetan kepada rentetan lain, saya tidak dapat mengingatinya pada masa ini.

Answer 10

Saya menggunakan blast blastn-short

:)