最快的方法來創建基準的隨機向量

所以，我只是在C++中實現一些排序算法，但我發現它在此刻進行基準測試令人氣憤，因爲它花費的時間太長運行算法，但創建輸入數據。我目前測試每個輸入的長度（1000，2000，...）10次，以獲得平均的時間。對於這些10倍，我創建了正確長度的新的隨機vector，這樣做：最快的方法來創建基準的隨機向量

// Each of the 10 times. 
    for(int j = 0; j < 10; j++) { 

     A.clear(); 

     // 'i' is the current input size. 
     for(int k = 0; k < i; k++) { 
      A.push_back(rand() % 10000); 
     } 

     // Other stuff 
    }

有沒有更好的方式來做到這一點？我是否應該打算在10000上限rand（），還是隻是我的OCD腦袋喜歡數字？（也就是說，當你認爲它的執行達到 - 目前爲止，這個模操作實際上會佔用大量的時間 - 每10次循環10,000次）。或者，我應該每次運行時都創建一個新的向量分類？我一直這樣做是因爲我覺得有可能創建的向量可能有偏差，所以如果生成這個向量並且使用了10次，答案可能會完全失敗......

來源

2010-07-24 Stephen

我無法想象相比，隨機數生成的模數是相關的。但是，測試很容易：只需將其刪除並測量即可。（你做測試版本，不是嗎？） – sbi 2010-07-24 16:05:54

Sorting algorithms * really * like random data。你不是創建一個準確的基準，使用*真實*數據。 – 2010-07-24 16:10:18

@Hans Passant你能舉出我能在哪裏找到一些不錯的預製真實數據的例子嗎？因爲恐怕在考慮如何生成*真實*數據時我不知道從哪裏開始......特別是當我嘗試甚至想象有多少種不同類型（非常預先排序，非常混亂等），以及哪些會更普遍... – Stephen 2010-07-24 16:17:05

有沒有更好的方法來做到這一點？

是的，有一些事情你可能想在這裏做，以幫助加快速度。如前所述，預留std :: vector中的空間然後將值分配給已知元素會更快。另外，使用非優化編譯器時，預先遞增（++ var而不是var ++）會更快。只是爲了保持代碼的快速性，無論是誰構建它，您都可能想從現在開始考慮這樣做。就內存而言，你可能會發現它是微不足道的，但是當我使用未經簽名的已知大小而不是不合理的大小時，我使用unsigned short來代替for循環。

然而，關於模數。如果你不需要它，你可能不想使用它。根據向量中保存的數據類型，如果結果高於類型的最大存儲容量，則結果應該包裝。

我不知道如果它吃了更多的處理能力有變量包裝，如果它的確如此，我仍然不確定它是否是一個較便宜的操作，然後執行模數。在使用rand之前，可能想運行一些已知尺寸的速度測試。

A.reserve(i * i); 
    for(unsigned short j = 0; j < 10; ++j) {    
     for(unsigned short k = 0; k < i; ++k) 
      A[k + (i*10)] = rand();     
     // Other stuff 
    }

編輯

非常小的變化要注意：該循環會只有10倍，所以你還不如用一個無符號的字符，而不是短期。至少在Win32上，它佔用了一半的內存。

A.reserve(i * i); 
    for(unsigned char j = 0; j < 10; ++j) {    
     for(unsigned char k = 0; k < i; ++k) 
      A[k + (i*10)] = rand();     
     // Other stuff 
    }

來源

2010-07-24 17:09:27 Xoorath

可讀性比「無論誰構建它」更重要。後增加速度與20年前的增量一樣快！ – 2013-06-29 20:59:41

哈哈，是的，你當然是對的。當我寫這篇文章的時候，我在讀大學時，事後看起來很愚蠢，我試圖在我沒有的編譯器上經歷幾分鐘的精神錯亂，甚至不知道如何進行剖析。我更喜歡前增量式，這就是我的同事所做的。但是，是的，絕對關注可讀性/可調試性和所有這些好東西。如果您正在編寫新代碼，對於樣式首選項，只需遵守原作者使用的內容或項目標準文檔。如果今天有人問我，那我就會告訴新手。 – Xoorath 2013-07-15 23:51:28

來自cplusplus的報價。（http://www.cplusplus.com/reference/stl/vector/），它提供了一個非常有用的提示：

「重新分配在性能方面可能是一個代價高昂的操作，因爲它們通常會將向量使用的整個存儲空間複製到新位置，只要規劃了一個向量大小的增加，建議使用成員函數vector::reserve明確指示向量的容量。「

使用vector::reserve幾乎可以肯定會提高性能。

編輯：你可以嘗試使用random_shuffle（http://www.cplusplus.com/reference/algorithm/random_shuffle/）來洗牌你的載體一旦創建（顯然，random_shuffle是線性的元素數量）。

來源

2010-07-24 15:59:51

它幾乎肯定會這樣做的第一次運行。我不認爲實現方式真的會忽略'clear（）'的能力。如果他們願意，我們不需要交換技巧。 – sbi 2010-07-24 16:02:22

@sbi：謝謝你指出，你是絕對正確的，'清除（）'不會縮小向量，顯然，甚至不'shrink_to_fit（）'肯定會（http://stackoverflow.com/questions/） 2664051 /爲什麼-被收縮到嵌合非結合）。 – 2010-07-24 16:13:56

我創建一個，我們來看一看：

#include <iostream> 
#include <cstdlib> 
#include <stdio.h> 
#include <time.h> 
#include <unistd.h> 
#include <sstream> 

int main(int argc, char* argv[]){ 
    if (argc < 2){ 
     printf("No arguments found\n"); 
     exit(1); 
    } 
    int maxi; 
    maxi = atoi(argv[1]); 
    int * a; 
    a = new int [5]; 

    std::stringstream ss; 
    ss << maxi; 
    printf(ss.str()); 
    printf("\n"); 
}

來源

2011-12-28 18:53:07

最快的方法來創建基準的隨機向量

回答

相關問題