4

ファイルからメモリにロードした大きな文字列を解析しようとしています。可変長のスライディング ウィンドウで DNA シーケンス (文字列として保存) を解析しています。問題は、文字列が非常に大きいため、反復処理に非常に長い時間がかかることです。それが可能かどうかはわかりませんが、どうにかしてこれをスピードアップすることは可能ですか?

つまり、I/O がアプリケーションを支配すると予想していたので、1 行ずつ読み取りをファイル全体を一度にメモリに読み込むようにシフトしましたが、コードをテストした後、ほとんどの時間を次のようなループで費やしていることがわかりました。

size_t currentCharNumber = 0;
int16_t windowSize = 50;
//seq is a string of length 249250621
while(seq.length() - currentLinePos < windowSize)
{
   string temp = seq.substr(currentLinePos, windowSize);
   //do stuff to temp
   ++currentLinePos;
}

シーケンスをファイルからメモリにロードするのに数秒しかかかりませんが、シーケンスを解析するのに約 30 分かかります (substr() 呼び出しの下の処理をコメントアウトした後でも)。多くのオーバーヘッドを追加している何かが欠けているのでしょうか、それともおそらくデータのサイズが原因でしょうか?

ATCG 以外の文字を含む部分文字列を無視できることを述べておくと役に立ちますか? コードでこのフィルタリングを行うのは、substr から文字列を取得した後であるということです。

これは私の初めての投稿で、私の C++ は少し錆びています。どんなフィードバックでも大歓迎です。

4

3 に答える 3

4

stringスライディング ウィンドウを保持するために を使用する方法から、 を使用する方法に切り替えることを検討してくださいstd::deque<char>。このdeque型は、両端で値を挿入および削除するように最適化されているため、ここでは適切な候補です。最初の 50 文字を にロードすることから始めて、次のdequeようにループを調整できます。

/* Initialize the window to the first windowSize characters. */
std::deque<char> window(seq.begin(), seq.begin() + windowSize);

/* Repeatedly process each window. */
for (size_t i = windowSize; i < seq.length(); ++i) {
    /* Do something to window */

    /* Drop the first character from the window, then add the next character
     * of the sequence.
     */
    window.pop_front();
    window.push_back(seq[i]);     
}

これにより、各ウィンドウを作成する時間が O(k) ではなく O(1) になります。ここkで、 はウィンドウ内の文字数です。ウィンドウ内の文字数が非常に多いため、実行時間が大幅に短縮される可能性があります。

お役に立てれば！

于 2012-08-27T19:30:02.250 に答える
3

範囲全体を別の文字列にコピーする代わりに、スライディング ウィンドウを 2 つのポインターで元の文字列に区切り、それを操作することができます。建設がオーバーヘッドになる場合std::stringは、それを避けてください。

std::string毎回まったく同じインスタンスを再利用することもできますが(ウィンドウ サイズが一定であると仮定)、それでもコピー操作のコストがかかります (ただし、ウィンドウ/長さの比率が小さい場合は無視できる場合があります)。

于 2012-08-27T19:29:58.897 に答える
3

を呼び出すとstd::string::substr、過剰な動的メモリ割り当てが発生し、少なくともバッファがコピーされる可能性があります。substr多くの場合、代わりに文字列区切りイテレータを使用するようにアルゴリズムを変更することで、必要性を減らすことができます。

于 2012-08-27T19:31:19.423 に答える