Самая длинная общая оптимизация SUBSTRING

Question

Может ли кто-нибудь помочь мне с оптимизацией моей задачи LONGEST COMMON SUBSTRING? Я должен читать действительно большие файлы (до 2 Гб), но я не могу определить, какую структуру использовать ... В C++ нет хэш-карт. В TBB существует параллельная хэш-карта, но с этим очень сложно использовать алгоритм. У меня эта проблема решена с помощью матрицы ** L, но она жадная и не может использоваться для больших входов. Матрица полна нулей, и это можно устранить, например, используя map> и хранить только не-нули, но это очень медленно и практически непригодно. Скорость очень важна. Вот код:

// L[i][j] will contain length of the longest substring 
    // ending by positions i in refSeq and j in otherSeq 
    size_t **L = new size_t*[refSeq.length()]; 
    for(size_t i=0; i<refSeq.length();++i) 
     L[i] = new size_t[otherSeq.length()]; 

    // iteration over the characters of the reference sequence 
    for(size_t i=0; i<refSeq.length();i++){ 
     // iteration over the characters of the sequence to compare 
     for(size_t j=0; j<otherSeq.length();j++){ 
      // if the characters are the same, 
      // increase the consecutive matching score from the previous cell 
      if(refSeq[i]==otherSeq[j]){ 
       if(i==0 || j==0) 
        L[i][j]=1; 
       else 
        L[i][j] = L[i-1][j-1] + 1; 
      } 
      // or reset the matching score to 0 
      else 
       L[i][j]=0; 
     } 
    } 

    // output the matches for this sequence 
    // length must be at least minMatchLength 
    // and the longest possible. 
    for(size_t i=0; i<refSeq.length();i++){ 
     for(size_t j=0; j<otherSeq.length();j++){ 

      if(L[i][j]>=minMatchLength) { 
       //this sequence is part of a longer one 
       if(i+1<refSeq.length() && j+1<otherSeq.length() && L[i][j]<=L[i+1][j+1]) 
        continue; 
       //this sequence is part of a longer one 
       if(i<refSeq.length() && j+1<otherSeq.length() && L[i][j]<=L[i][j+1]) 
        continue; 
       //this sequence is part of a longer one 
       if(i+1<refSeq.length() && j<otherSeq.length() && L[i][j]<=L[i+1][j]) 
        continue; 
       cout << i-L[i][j]+2 << " " << i+1 << " " << j-L[i][j]+2 << " " << j+1 << "\n"; 

       // output the matching sequences for debugging : 
       //cout << refSeq.substr(i-L[i][j]+1,L[i][j]) << "\n"; 
       //cout << otherSeq.substr(j-L[i][j]+1,L[i][j]) << "\n"; 
      } 
     } 
    } 

Answer 1

Существует такая же проблема, как Intel.

Может быть, они будут размещать некоторые solutinons, когда это более

http://software.intel.com/fr-fr/articles/AYC-early2012_home/