排序列表與未排序列表的線性搜索 - 爲什麼排序較慢？

所以我創建了一些隨機整數並將它們放入一個列表中。我做了一個副本，然後我排序了原始列表。當我通過排序列表搜索特定項目時，它比我在未排序副本中的速度慢得多。爲什麼會發生？這是我使用的代碼和最後的一些運行時。排序列表與未排序列表的線性搜索 - 爲什麼排序較慢？

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; 

}

這裏是我播種蘭特（）函數，但我不認爲他們是重要的

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; 
}

我的運行時間是：

排序列表 - 指數：44315項： 4439392時間：0.047秒

無序 - 指數：50000項：4439392時間：0.028秒

來源

2014-10-13 kamoussa

您是否在使用渦輪增壓的機器上進行測試？ – James

您是否正在測試版本配置？我[無法複製]（http://coliru.stacked-crooked.com/a/db28de3a8bd59904）你的問題。你也總是得到這樣的結果？ –

@詹姆斯號我正在使用2 GHz和6GB RAM的i7 – kamoussa

我這裏的主題有點生疏，但據我所知，C++列表是雙向鏈表，這意味着不能保證你的數據在內存中是連續的。這很可能是爲兩個列表分配的內存最初是公平的（如果不是完全）連續的，這意味着CPU不必非常尋找RAM。由於列表的性質，對它進行排序並不會實際移動數據，而只是更新每個元素指向的內容。因此，當對列表進行排序時，元素會遍佈在內存中，這意味着CPU將不得不爲每個操作抓取新的RAM。

按說這不是一個大問題，但是當你重複它在平均50000次，這是一個很大浪費CPU週期只是在等待RAM響應等

來源

2014-10-13 07:11:36 Berans

哦好吧，所以基本上從元素到下一個需要更長的時間，因爲它不是連續的？這種說法是有道理的，但我不明白爲什麼CPU需要爲每個操作獲取新的RAM。 – kamoussa

以元素隨機順序進行元素讀取幾乎每次都會讀取完整的緩存行;還會拋出一些其他緩存行，其中包含緩存中未訪問的元素。爲了演示這一點，可以將已排序數組重新線性化爲一個新數組，該數組很可能包含線性順序的元素。如果輸入沒有偏見，分類與未分類 - 非線性數組的基準時間應該匹配。 –

我真的沒有看到任何問題用你的代碼，但是測試的順序可能很重要。特別是在如此短的運行時間內，特別是如果您的計算機運行的處理器能夠動態改變其性能狀態。

許多英特爾處理器都配備了稱爲turbo boost的技術，這種技術基本上使處理器在性能需求方面更加強大，而且爲了節約能源，在無需任何設備時回到較低的性能狀態更多。欲瞭解更多信息，請參閱this wiki site。所以結論 - 嘗試改變測試順序或/和設置你的處理器管理器的性能，並增加測試集的大小。 0.0 ...運行時間真的非常低，許多奇怪的現象可能會生效。

還可以考慮將你的整數存儲在一些更方便的東西里，比如向量。將整數存儲在列表中似乎是相當浪費空間，除非你有充分的理由這樣做。

來源

2014-10-13 07:12:00 Jendas

感謝您的信息。我只是想用列表來測試它，因爲我在我的項目中使用的不是矢量列表。生病嘗試做一個新的實施。我應該保持指數不變，以便在這種情況下襬脫一個因變量？ – kamoussa

嗯，我會這樣做，但這真的取決於你想要測試什麼。 – Jendas

排序列表與未排序列表的線性搜索 - 爲什麼排序較慢？

回答

相關問題