4

我正在尝试解析从文件加载到内存中的大字符串。我正在使用可变长度的滑动窗口解析 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++ 有点生疏。任何反馈将不胜感激。

4

3 回答 3

4

您可能需要考虑从使用 astring来保持滑动窗口切换到使用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(1) 而不是 O(k)，其中k是窗口中的字符数。这可能会大大减少运行时间，因为窗口中的字符数非常大。

希望这可以帮助！

于 2012-08-27T19:30:02.250 回答
3

您可以通过两个指向原始字符串的指针来分隔滑动窗口并使用它，而不是将整个范围复制到单独的字符串中。如果std::string施工是开销，请避免。

std::string您也可以每次都重复使用相同的实例（假设窗口大小是恒定的），但它仍然会花费您一次复制操作（尽管对于小窗口/长度比而言，这可能可以忽略不计）。

于 2012-08-27T19:29:58.897 回答
3

调用std::string::substr可能会导致过多的动态内存分配，并且至少会复制缓冲区。通常，您可以substr通过更改算法以使用字符串分隔迭代器来减少对的需求。

于 2012-08-27T19:31:19.423 回答