C++ 加速多个 substr() 或等效函数调用以解析大字符串

Question

我正在尝试解析从文件加载到内存中的大字符串。我正在使用可变长度的滑动窗口解析 DNA 序列(存储为字符串)。问题是字符串太大，遍历它们需要很长时间。我不知道这是否可能，但是否有可能以某种方式加快速度？

我的意思是我希望 I/O 主导我的应用程序，所以我将逐行读取改为一次将整个文件读入内存，但在测试我的代码后我发现它大部分时间都在这样的循环中:

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++ 有点生疏。任何反馈将不胜感激。

Answer 1

您可能需要考虑从使用 string 切换到使用 std::deque<char> 来保持你的滑动窗口. deque type 针对在两端插入和删除值进行了优化，因此在这里是一个很好的候选者。您可以先将前 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(1) 而不是 O(k)，其中 k是窗口中的字符数。这可能会显着减少运行时间，因为窗口中的字符数非常大。

希望这对您有所帮助!