排序列表上的线性搜索与未排序列表相比——为什么排序较慢

Question

所以我创建了一些随机int，并将它们放入列表中。我把它复印了一份，然后对原始列表进行了排序。当我在排序列表中搜索特定项目时，它比在未排序的副本中搜索慢得多。为什么会发生这种情况？下面是我使用的代码和最后的一些运行时。

int main(){
   const int SIZE = 100000, MAX_ELM = 10000000;
   list<int> sortedList;
   list<int> unsortedList;
   int indexToFind, itemToFind;
   srand(time_seed());
   indexToFind = SIZE/2;
   //initialize list
   for (int i = 0; i < SIZE; i++){      
      if (i == indexToFind){
         itemToFind = randomNum(0, MAX_ELM);
         sortedList.push_back(itemToFind);
      }
      else
         sortedList.push_back(randomNum(0, MAX_ELM));
   }
   unsortedList = sortedList; //copy ctr
   sortedList.sort();
   clock_t start, end;
   int sortedItemIndex = 0;
   //search for item in sorted list
   start = clock();
   list<int>::iterator it;
   for (it = sortedList.begin(); it != sortedList.end(); ++it){
      if ((*it) == itemToFind){
         break;
      }
      sortedItemIndex++;
   }
   end = clock();
   cout << "index: " << sortedItemIndex << "  item: " << itemToFind << endl; 
   cout << (double)(end - start) / (double)CLOCKS_PER_SEC << endl << endl;
   //unsorted
   start = clock();
   for (it = unsortedList.begin(); it != unsortedList.end(); ++it){
      if ((*it) == itemToFind)
         break;
   }
   end = clock();
   cout << "index: " << indexToFind << "  item: " << itemToFind << endl;
   cout << (double)(end - start) / (double)CLOCKS_PER_SEC << endl;
}

以下是我的rand（）种子函数，尽管我认为它们对不重要

int randomNum(int min, int max){
   return rand() * (1.0 / (RAND_MAX + 1.0)) * (max - min);
}
unsigned time_seed(){ // implementation from online
   time_t now = time(NULL);
   unsigned char *p = (unsigned char *)&now;
   unsigned seed = 0;
   size_t i;
   for (i = 0; i < sizeof now; i++)
      seed = seed * (UCHAR_MAX + 2U) + p[i];
   return seed;
}

我的运行时间是：

sortedList-索引：44315项目：4433932时间：0.047秒

未排序-索引：50000项目：44339392时间：0.028秒

Answer 1

我对这里的主题有点生疏，但据我所知，c++列表是双链表，这意味着不能保证您的数据在内存中是连续的。很可能，分配给这两个列表的内存最初是相当连续的（如果不是完全连续的话），这意味着CPU不必在RAM中寻找太多。由于列表的性质，排序并不会在物理上移动数据，而是更新每个元素所指向的内容。因此，当你对列表进行排序时，元素会指向内存中的所有位置，这意味着CPU几乎每次操作都必须获取新的RAM。

通常这不是什么大不了的事，但当你平均重复50000次时，仅仅等待RAM响应等就浪费了大量的CPU周期。

Answer 2

我确实没有发现您的代码有任何问题，但测试的顺序可能很重要。尤其是在运行时间如此之短的情况下，尤其是当您的计算机运行的处理器能够动态更改其性能状态时。

许多英特尔处理器都配备了名为turbo boost的技术，这基本上使处理器在有性能需求时更强大，而在不再需要时，为了节省能源，它会回到较低的性能状态。有关详细信息，请参阅此wiki网站。

因此，结论-尝试更改测试顺序或/和将处理器调控器设置为性能，同时增加测试集的大小。0.0…运行时间真的很低，许多奇怪的现象可能会发生。

还可以考虑将整数存储在更方便的东西中，例如向量。在列表中存储整数似乎相当浪费空间，除非您有充分的理由这样做。