Chinaunix首页 | 论坛 | 博客
  • 博客访问: 348429
  • 博文数量: 42
  • 博客积分: 1896
  • 博客等级: 上尉
  • 技术积分: 615
  • 用 户 组: 普通用户
  • 注册时间: 2007-06-19 14:47
文章分类

全部博文(42)

文章存档

2012年(1)

2011年(21)

2010年(16)

2009年(4)

分类: C/C++

2011-04-07 16:19:05

测试环境:酷睿双核2.9G(E7500),4G内存
  listQStringList。
Solution1:效率非常低(数组长度1W以后就开始无响应需要循环10w次左右耗时2s)

  1.     int tempCount = 0;
  2.     QList<int> indexList;
  3.     int count = list.count();
  4.     while ( indexList.count() < count )
  5.     {
  6.         ++tempCount;
  7.         int i = qrand() % list.count() ;
  8.         if ( indexList.indexOf( i ) == -1 )
  9.         {
  10.             indexList.append( i );
  11.         }
  12.     }


Solution2:时间复杂度为O(n),但是增加空间复杂度和list的操作开销,100w元素需要9s

     QStringList tempList;
  1.     while ( list.count() > 0 )
  2.     {
  3.         int i = qrand() % list.count() ;
  4.         tempList.append( list.takeAt( i ) );
  5.     }

Solution3:效率理想,元素较多的时候耗时至少是solution2的100倍,1000W个元素的数组只要700多毫秒。

  1.     int count = list.count();
  2.     int times = count;

  3.     for ( int i = 0; i < times; ++i )
  4.     {
  5.         int randIndex = qrand() % count ;
  6.         int cIndex = i % count;

  7.         if ( cIndex != randIndex )
  8.         {
  9.             qSwap( list[cIndex], list[randIndex] );
  10.         }
  11.     }

阅读(2410) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~