低消費電力プロセッサ用の高速検索 - 挿入 - 削除アルゴリズム

Question

受信データへの高速応答が必要な低消費電力プロセッサで動作するアプリケーションがあります。データには、関連するキーが付属しています。各キーの範囲は0〜0xFE（最大0xFF）です。データ自体のサイズは1kBから4kBです。システムは次のようなデータを処理します。

data in 
key lookup -> insert key & data if not found 
buffer data in existing key 

何らかのイベントが発生した後、キーと関連するデータは破棄されます。

私たちは、ソリューションのカップル試用されています

1. 事前に割り当てられたstd::vector<std::pair<int,unsigned char *>>、インデックス位置に基づいて、キー値を検索します。バイナリ・ソートとのバイナリ検索と

2. std::map<int, unsigned char *>

3. 赤黒木

4. std::vector<...>キーの

インサートで速い可能性があり、他のアルゴリズムがあります検索 - 削除？

ありがとうございました。

Answer 1

キーが範囲[0, 0xFF)である場合は、この使用することができます：私はデータが存在しないことを示すために、空の文字列を使用

std::vector<std::string> lut(0xFF); //lookup table 

//insert 
lut[key] = data; //insert data at position 'key' 

//delete 
lut[key].clear(); //clear - it means data empty 

//search 
if(lut[key].empty())  //empty string means no key, no data! 
{ 
    //key not found 
} 
else 
{ 
    std::string & data = lut[key]; //found 
} 

注意を。

Answer 2

std::mapは、バランスのとれたツリー（赤黒の木のような）自体を使用しているため、再実装する必要はありません。

バイナリ検索でソートされたstd::vectorは、バランスのとれたバイナリツリーと同じパフォーマンスを持ちます。違いは、キーの中央にキーを配置するのはコストがかかることです。

あなたの鍵は非常に限られた範囲を持っているので、あなたの最良の選択は、あなたの最初の提案のようになります。

std::vector<unsigned char *> data(0xFF); // no need to have a pair 

この方法で、data[key] == NULLの簡単なチェックは、このキーのデータが存在するかどうかを示します。それが私の場合は、さらにシンプルにすることもできます：

unsigned char *data[0xFF];