哪個方法是更快的矢量（插入然後排序）或設置？

我有數字序列（未排序，無重複）與目標排序。哪個方法是更快的矢量（插入然後排序）或設置？

方法1：插入向量。 O（n），使用排序算法和排序。 O（nlogn）

方法2：插入到集合中。 o（nlogn）

哪種方法會更快？

我覺得設置會更快，因爲每個插入矢量必須分配完整的數組元素並複製它然後刪除它可能是昂貴的。但是我通過網絡閱讀了大部分的地方向量已經過去了。

任何人都可以建議我哪一個適當的邏輯更快？

編輯：如果我們不知道沒有元素的提前哪一個會更快設置或載體（適用於任何元素都是smaall和d沒有elementt的大注：如果沒有元素的大集是更好的選擇，它似乎，但它的好處是對於還少嗎？不知道）

來源

2014-07-26 Suri

在不同尺寸的元素上嘗試它們。繪製圖表。結果顯示了什麼？（爲了簡單地獲得排序結果，我期望矢量+排序更快，因爲所採用的排序可以減少簿記，這可能導致小C或掛鐘時間。） – user2864740

這取決於您閱讀的方式結果。如果你從頭到尾閱讀，設置會更快，而矢量支持隨機訪問。順便說一句，插入到集取O（logn）時間，從空集set = log1 + log2 + log3 + ... + logn = O（n）中插入1。 – tom87416

@ tom87416：爲什麼從開始到結束閱讀一個集合比從頭到尾閱讀一個矢量要快？遍歷一個集合需要在一棵樹上下一個節點指針，而遍歷一個矢量只是增加一個指針。另外，你的數學是錯誤的，蘇瑞是對的。 –

如果事先許多元素知道會，您可以在您的載體，以避免重新分配reserve()空間，使第一選擇非常有趣（快速插入，單一排序）。

如果您需要做一次，請參閱std::vector<>。如果其他插入將在後面的程序中發生，std::set<>可能更有趣。
如果你不事先知道預期的大小，然後再分配可以與載體發生，std::set<>是一個不錯的選擇（更好的理論平均複雜度）。

爲O（n）+ O（N *的log（n））的向量VS爲O（n *的log（n））對於該組
如果元件的數目是非常小的，你仍然可以保留一些空間（例如，如果你希望10個元素，你可能會預留100是安全的），並與std::vector

去反正，剖析這兩種解決方案始終是一個很好的做法，實際結果將取決於（除其他之外）輸入的初始排序狀態，a發現每個容器的實施質量。

注：

記住std::set擁有更大的內存足跡，如果重要的爲您服務。

來源

2014-07-26 06:41:21 quantdev

這取決於您的使用情況。

對於設置：

+高速數據接入O（LOGN）

+你並不需要關心排序

- 由於設置被實現爲一棵樹，每個元素都有內存開銷。

- 數據可以分佈在內存堆中，因此CPU緩存不能很好地工作。

對於矢量：

+的數據被包含在連續的存儲器塊。所以，你的CPU緩存更好。

+你的搜索都是相同的O（LOGN）

+您可以reserve記憶吧。

- 每次更改後都需要排序。

所以，如果你有很多元素，並做了「一次插入，許多搜索」，我寧願矢量。如果您製作了很多插入/搜索查詢，那麼最好堅持集合。

用O（）的術語思考我會說vector插入成本是O（nlogn），但它可以在插入後調用一次。集插入成本是O（logn）並調用每個插入。所以，如果你需要插入後載體是排序，你會支付num_insertions*O(nlogn)爲載體和O(log (n+num_insertions))爲集，這是真的更便宜。

來源

2014-07-26 06:44:49 PSIAlt

[「[std：set \] s是按照特定順序存儲唯一元素的容器。」]（http://www.cplusplus.com/reference/set/set/） - 即排序。問題是詢問*哪一種獲得排序結果的方法是「更快」，但是既沒有強加（也沒有詢問）其他訪問。 – user2864740

設置不是一個鏈接列表。 –

Set不是一個鏈表，而是一個基於節點的樹，但結論是一樣的。 –

我想我會用剖析器來研究這個。我的代碼：

//g++ -std=c++11 -Wall vectorvsset.cpp -g -pg -o vectorvsset 
#include <time.h> 
#include <iostream> 
#include <vector> 
#include <set> 
#include <algorithm> 
using namespace std; 

void GenRandom(vector<int32_t> &original) 
{ 
    original.clear(); 
    for(size_t i=0; i<10000; i++) 
     original.push_back(rand()); 
} 

void TestSet(const vector<int32_t> &original) 
{ 
    set<int32_t> testset; 
    testset.insert(original.begin(), original.end()); 
} 

void TestVector(const vector<int32_t> &original) 
{ 
    vector<int32_t> testvec; 
    testvec.insert(testvec.end(), original.begin(), original.end()); 
    sort(testvec.begin(), testvec.end()); 
} 

void TestVectorConvertToSet(const vector<int32_t> &original) 
{ 
    vector<int32_t> testvec; 
    testvec.insert(testvec.end(), original.begin(), original.end()); 
    sort(testvec.begin(), testvec.end()); 
    std::set<int32_t> testsec(testvec.begin(), testvec.end()); 
} 

int main() 
{ 
    srand(time(NULL)); 
    cout << "RAND_MAX " << RAND_MAX << endl; 
    vector<int32_t> original; 

    for(size_t i=0; i<100; i++) 
    { 
     GenRandom(original); 

     TestSet(original); 

     TestVector(original); 

     TestVectorConvertToSet(original); 
    } 

    return 0; 
}

使用對於g ++ gprof的（Ubuntu的5.4.0-6ubuntu1〜16.04.4）5.4.0 20160609我的（略）結果是：

Each sample counts as 0.01 seconds. 
    % cumulative self    self  total   
time seconds seconds calls ms/call ms/call name  
    0.00  1.42  0.00  100  0.00  3.36 TestVector(std::vector<int, std::allocator<int> > const&) 
    0.00  1.42  0.00  100  0.00  6.86 TestVectorConvertToSet(std::vector<int, std::allocator<int> > const&) 
    0.00  1.42  0.00  100  0.00  3.57 TestSet(std::vector<int, std::allocator<int> > const&)

因此，它是更快地使用一個矢量，但沒有太大的區別。

來源

2017-08-31 14:55:50 TimSC

哪個方法是更快的矢量（插入然後排序）或設置？

回答

相關問題