C++加快多SUBSTR（）或同等功能要求大串

我试图解析，我已经加载到存储器中的文件大串的解析。我用可变长度的滑动窗口解析DNA序列（以字符串形式存储）。问题是这些字符串非常大，需要很长时间才能遍历它们。我不知道这是否是可能的，但有可能以某种方式加速这个过程？C++加快多SUBSTR（）或同等功能要求大串

我的意思是我期望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++是有点生疏。任何反馈将不胜感激。

来源

2012-08-27 cjustin

'substr'与'std :: string :: substr'有关吗？也许你的意思是'seq.substr（...）'？ –

不应该'currentLinePos'增加'windowSize'而不是1？或者你的意思是'currentCharNumber'？ – sonicwave

也许你应该告诉我们更大的上下文，所以你可以改进算法，以避免使用'substr'。 – Nobody

您可能需要考虑从使用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），其中k每个窗口O（1）时间是窗口中的字符数。这可能会大大降低运行时间，因为窗口中的字符数量非常大。

希望这会有所帮助！

来源

2012-08-27 19:30:02 templatetypedef

我已经使用了它，并且速度更快，总体上可能提高了约60％。但下游的一切都期待一个字符串。我只需要改变下游的一切。我还没有尝试别人所说的两个方法。谢谢 – cjustin

您可以通过两个指针划定的滑动窗口到原始字符串，并与工作，而不是复制整个范围划分为一个单独的字符串。如果std::string建设是一个开销，避免它。你也可以每次重复使用同一个std::string实例（假设窗口大小不变），但它仍然需要复制操作（尽管对于小窗口/长度比率可能可以忽略不计）。

来源

2012-08-27 19:29:58

呼叫至std::string::substr可能导致过度的动态存储器分配，并在最起码，围绕复制缓冲器。通常，您可以通过改变算法来使用字符串分隔迭代器来减少对substr的需求。

来源

2012-08-27 19:31:19

C++加快多SUBSTR（）或同等功能要求大串

回答

相关问题