查找速度快於std :: set

我需要更快的成員關係查找一些傳統的數據包處理代碼，它需要識別具有特定ID的數據包是否在特定列表中。查找速度快於std :: set

，而數據包匹配發生非常非常頻繁的列表只每隔幾秒鐘更新一次，所以查找性能比插入更重要/刪除等

一般流程：

forall(special_PacketIDs) 
{ 
    pktIdSet.insert(theSpecialPktId) 
} 

while (1) 
{ 
    pkt = readPkt(); 
    pktID = getPktIdOfPkt(pkt); 

    if (aSpecialPkt(pktID)) 
    doSomething(); 
}

而現在，aSpecialPkt(pktId)被定義爲：

bool PktProcessor::aSpecialPkt(unsigned short pid) 
{ 
    return pktPidSet.find(pid) != pktPidSet.end(); 
}

gprof的報告）大量的時間在STD花::設爲::發現（

pktId的範圍只有8192個可能的值。分配的線性陣列會快得多，在內存作爲代價，這樣的：

class LinearSet 
{ 
public: 
    void insert(pid) { mPktIdSet[pid] = true; } 
    bool elementExists(pid) { return mPktIdSet[pid]; } 
private: 
    bool mPktIdSet[8192]; 
}

我的問題是，是否有這樣做的同時保持頂級性能的更「C++」的方式？

來源

2016-02-26 Danny

你試過'std :: unordered_set'還是'std :: vector '？ – 5gon12eder

現在這個集合被定義爲std :: set 。但似乎unordered_set僅在C++ 11中可用，而這些舊代碼在沒有大量工作的情況下無法工作。 – Danny

@Danny：尋找std :: set的複雜度是對數的，而對於std :: unordered_set常量的平均值（最差的情況是線性的） –

如果您知道正好有8192種可能性，那麼您最好的選擇可能是std::bitset<8192>，它將使用一個千字節，並且對緩存非常友好。

來源

2016-02-26 14:47:24 rici

極好的選擇。爲了將來的參考，只需添加如果尺寸大得多，並且一些錯誤都可以，那麼[bloom filter]（https://github.com/mavam/libbf）可能是合適的。 –

這很完美。謝謝！ – Danny

@AmiTavory非常好的建議 - 難以捉摸的布隆過濾器的一個很好的用例。 :) – erip

std::bitset<8192>是一個不錯的選擇，但它確實取決於您的平臺以及特殊數據包ID的數量。看到這個問題：Choosing between set<int> vs. vector<bool> vs. vector<boolean_t> to use as a bitmap (bitset/bit array)

來源

2016-02-26 14:58:32 Daniel

這是完美的。謝謝！ – Danny

查找速度快於std :: set

回答

相關問題