0
Ich versuche, mein Programm effizienter laufen zu lassen, und ich glaube, dass die Behebung dieser linearen Suche eine große Hilfe in Bezug auf die Geschwindigkeit leisten würde, aber ich bin neugierig, wie ich das ändern würde Suche, da ich glaube, dass die Liste nicht unbedingt geordnet ist. Gibt es eine Möglichkeit, die Liste basierend auf dem ersten Argument key zu sortieren?Schnellere Suche in der Liste?
Was mit zur Zeit arbeite ich:
int* key_sequences::data(int key){
for(it=myList.begin(); it!=myList.end(); ++it){
if(it->first==key){
return &(it->second[0]);
}
}
return nullptr;
};
Binäre Suche ist ohne eine sortierte Sequenz nicht möglich. –
Die offensichtliche Antwort wäre, die Verwendung einer Liste zu beenden und sie durch eine geeignetere Datenstruktur zu ersetzen (möglicherweise eine "Map" oder "ungeordnete_map", aus der Sicht der Dinge). Abhängig davon, wann/wie oft eingefügt/gelöscht wird, können Sie auch eine "FlatMap" - binäre Suche in einem sortierten Array in Betracht ziehen. –
Oft wird eine Sequenz wiederholt nach aufeinander folgenden Schlüsseln durchsucht. Das Cachen des letzten Suchergebnisses kann dann die Gesamtzeit von O (n²) auf O (n) reduzieren. Aber ich würde die Datenstruktur in etwas geeigneteres, wie eine "Karte" ändern. –