Schneller Such-Einfüge-Lösch-Algorithmus für Low-Power-Prozessor

Question

Wir haben eine Anwendung, die auf einem Low-Power-Prozessor ausgeführt wird, der schnelle Antwort auf eingehende Daten haben muss. Die Daten kommen mit einem zugehörigen Schlüssel. Jede Taste reicht von 0 - 0xFE (max 0xFF). Die Daten selbst reichen von 1kB bis 4kB. Das System verarbeitet Daten wie:

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

Nach einem Ereignis werden ein Schlüssel und zugehörige Daten zerstört.

Wir sind ein paar Lösungen trialing:

1. Pre-zugewiesen std::vector<std::pair<int,unsigned char *>>, die einen Schlüsselwert auf der Grundlage der Indexposition nachschlägt.

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

3. Rot-Schwarz-Baum

4. std::vector<...> mit einer binären Art und binärer Suche nach dem Schlüssel des

Gibt es andere Algorithmen, die schnell auf Einfügen- sein könnte Suchen-Löschen?

Danke.

Answer 1

Wenn der Schlüssel im Bereich [0, 0xFF), dann könnten Sie verwenden:

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 
} 

Bitte beachte, dass ich leere Zeichenfolge verwendet, um diese Daten anzuzeigen, ist nicht vorhanden.

Answer 2

std::map verwendet einen ausgewogenen Baum (wie Rot-Schwarz-Baum) selbst, es hat also keinen Sinn, ihn erneut zu implementieren.

Ein sortierter std::vector mit binärer Suche hat die gleiche Leistung eines ausgeglichenen Binärbaums. Der Unterschied besteht darin, dass das Platzieren eines Schlüssels in der Mitte des Vektors teuer ist.

Da Ihre Schlüssel eine sehr begrenzte Reichweite haben, die beste Wahl ist ähnlich wie die erste Vorschlag:

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

diese Weise eine einfache Überprüfung von data[key] == NULL zeigt Ihnen, ob Daten für diesen Schlüssel vorhanden ist oder nicht. Wenn ich es wäre, würde ich es sogar einfacher machen:

unsigned char *data[0xFF];