cari

Rumah  >  Soal Jawab  >  teks badan

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

PHP中文网PHP中文网2806 hari yang lalu1436

membalas semua(17)saya akan balas

  • PHPz

    PHPz2017-04-18 10:01:45

    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]];
}

    balas
    0
  • 阿神

    阿神2017-04-18 10:01:45

    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

    balas
    0
  • 巴扎黑

    巴扎黑2017-04-18 10:01:45

    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

    balas
    0
  • 伊谢尔伦

    伊谢尔伦2017-04-18 10:01:45

    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

    balas
    0
  • 巴扎黑

    巴扎黑2017-04-18 10:01:45

    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)

    balas
    0
  • 天蓬老师

    天蓬老师2017-04-18 10:01:45

    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

    balas
    0
  • 黄舟

    黄舟2017-04-18 10:01:45

    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. ,

    balas
    0
  • PHP中文网

    PHP中文网2017-04-18 10:01:45

    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.

    balas
    0
  • PHP中文网

    PHP中文网2017-04-18 10:01:45

    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.

    balas
    0
  • 巴扎黑

    巴扎黑2017-04-18 10:01:45

    Saya menggunakan blast blastn-short

    :)

    balas
    0
  • Batalbalas