使用迭代器时的性能问题？ [英] Performance issues when using iterators?
问题描述
我有一个函数接受字符列表并生成下一个词典排列。为了有趣，我尝试泛化代码使用迭代器，以及能够生成更多不同类型的排列。
template< ;类型ITER>
bool nextPermutation（ITER start，ITER end，std :: random_access_iterator_tag）
{
for（ITER i = end-1; i！= start; --i）
{
if（*（i-1）<* i）
{
//找到可以交换的地方
for（ITER j = end-1; j！= i-1）; - j）
{
if（*（i-1）<* j）
{
//找到要与$ b交换的内容b auto temp = * j;
* j = *（i-1）;
*（i-1）= temp;
//通过反转
（ITER k = end-1; k> i; --k，++ i）
{
temp = * k;
* k = * i;
* i = temp;
}
return true;
}
}
}
}
return false;
}
但是，我遇到了问题，当我不使用raw指针的性能的代码明显更慢。这是我的测试平台：
template< typename ITER>
bool nextPermutation（ITER start，ITER end，std :: random_access_iterator_tag）;
template< typename ITER>
bool nextPermutation（ITER start，ITER end）
{
return nextPermutation（start，end，std :: iterator_traits< ITER> :: iterator_category（））;
}
#define USE_VECTOR
int main（void）
{
bool hasNext = true;
#ifdef USE_VECTOR
std :: vector< char> C;
for（char i ='0'; i <='9'; ++ i）
{
c.push_back（i）;
}
for（size_t i = 0; i <999999&& hasNext; ++ i）
{
hasNext = nextPermutation（c.begin（），c 。结束（））;
}
#else
char c [] =0123456789;
size_t LENGTH = 10;
for（size_t i = 0; i <999999&& hasNext; ++ i）
{
hasNext = nextPermutation（c，c + LENGTH）;
}
#endif
std :: cout< done<< std :: endl;
std :: cin.ignore（）;
return 0;
}
当 USE_VECTOR 定义，运行这个测试台需要〜20秒。当我不确定它，代码运行不到一秒钟（我没有写任何时间码，但足以说，有一个非常显着的性能差异）。
现在我的问题是，我采取如此巨大的性能命中，这将影响使用迭代器（std :: string迭代器，std :: vector迭代器等）与原始指针？
$ b $在没有优化的情况下，由于迭代器调试（ _ITERATOR_DEBUG_LEVEL 在调试模式下默认为2，因此aka 完全调试），代码在我的机器上也很慢。使用
/ 02 但是，迭代器调试完全禁用，代码完全之前的控制台窗口甚至出现。这里你有一个很好的例子，调试使事情更慢，但更安全。 ：）
I have a function which takes in a list of characters and generates the next lexicographic permutation. For fun, I tried generalizing the code to use iterators, as well as being able to generate permutations of more different types.
template<typename ITER>
bool nextPermutation(ITER start, ITER end, std::random_access_iterator_tag)
{
for(ITER i = end-1; i != start; --i)
{
if(*(i-1) < *i)
{
// found where can be swapped
for(ITER j = end-1; j != (i-1); --j)
{
if(*(i-1) < *j)
{
// found what to swap with
auto temp = *j;
*j = *(i-1);
*(i-1) = temp;
// put everything from i on into "sorted" order by reversing
for(ITER k = end-1; k > i; --k,++i)
{
temp = *k;
*k = *i;
*i = temp;
}
return true;
}
}
}
}
return false;
}
However, I'm running into issues where when I don't use raw pointers the performance of the code is significantly slower. Here's my test rig:
template<typename ITER>
bool nextPermutation(ITER start, ITER end, std::random_access_iterator_tag);
template<typename ITER>
bool nextPermutation(ITER start, ITER end)
{
return nextPermutation(start, end, std::iterator_traits<ITER>::iterator_category());
}
#define USE_VECTOR
int main(void)
{
bool hasNext = true;
#ifdef USE_VECTOR
std::vector<char> c;
for(char i = '0'; i <= '9'; ++i)
{
c.push_back(i);
}
for(size_t i = 0; i < 999999 && hasNext; ++i)
{
hasNext = nextPermutation(c.begin(), c.end());
}
#else
char c[] = "0123456789";
size_t LENGTH = 10;
for(size_t i = 0; i < 999999 && hasNext; ++i)
{
hasNext = nextPermutation(c, c+LENGTH);
}
#endif
std::cout << "done" << std::endl;
std::cin.ignore();
return 0;
}
When USE_VECTOR is defined, it takes ~20 seconds to run this test rig. When I undefine it, the codes runs in less than a second (I didn't write any timing code, but it's sufficient to say there's a very significant difference in performance).
Now my question is where am I taking such a huge performance hit which would affect using an iterator (std::string iterator, std::vector iterator, etc.) vs. a raw pointer?
Without optimizations, due to heavy iterator debugging (_ITERATOR_DEBUG_LEVEL is defaulted to 2 in debug mode, aka full debugging), the code is also slow on my machine.
With /02 however, the iterator debugging is disabled completely and the code executes in full before the console window even shows up.
Here you got a nice example of debugging making things slower but safer. :)
这篇关于使用迭代器时的性能问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
