Schnellste Möglichkeit zu bestimmen, ob Zeichen zu einer Menge bekannter Zeichen gehören C++

Question

Wenn ich ein beliebiges Zeichen habe, kann ich am schnellsten feststellen, ob dieses Zeichen zu einer Menge (nicht dem Containertyp) bekannter Zeichen gehört.

Mit anderen Worten, was ist der schnellste elegante Weise die bedingte umzusetzen:
char c = 'a';
if(c == ch1 || c == ch2 || c == ch3 ...) // Do something...

Gibt es einen STL-Container (ich denke, es könnte unordered_set sein?), Dass ich nur das passieren kann Zeichen als Schlüssel zu und es gibt wahr zurück, wenn der Schlüssel existiert?

Alles mit einer O (1) Lookup-Zeit wird für mich arbeiten.

Answer 1

Ich ging ein wenig weiter und schrieb zwei Versionen, eine basierend auf einem Lookup-Array, die andere auf einem Set mit einem zugrunde liegenden Hash.

class CharLookup { 
public: 
    CharLookup(const std::string & set) : lookup(*std::max_element(set.begin(), set.end()) + 1) { 
    for (auto c : set) lookup[c] = true; 
    } 
    inline bool has(const unsigned char c) const { 
    return c > lookup.size() ? false : lookup[c]; 
    } 
private: 
    std::vector<bool> lookup; 
}; 

class CharSet { 
public: 
    CharSet(const std::string & cset) { 
    for (auto c : cset) set.insert(c); 
    } 
    inline bool has(const unsigned char c) const { 
    return set.contains(c); 
    } 
private: 
    QSet<unsigned char> set; 
}; 

Dann schrieb ein kleiner Benchmark, fügte ein paar weitere Container für den Vergleich hinzu.Lower besser ist, sind die Datenpunkte für „Zeichensatz Größe/Textgröße“:

Scheint wie für kurze Zeichensätze und Text, std::string::find_first_of ist am schnellsten, sogar schneller als eine Lookup-Array, aber schnell schwindet, wenn die Testgröße zunimmt. std::vector<bool> scheint wie das "goldene Mittel", QBitArray hat wahrscheinlich eine etwas andere Implementierung, weil es voranschreitet, wie die Testgröße zunimmt, beim größten Test QVector<bool> ist am schnellsten, vermutlich, weil es nicht den Overhead von Bit-Zugriff hat. Die beiden Hash-Sets sind nahe, Handelsplätze, zuletzt und am wenigsten gibt es die std::set.

Getestet auf einer i7-3770k Win7 x64 Box mit MinGW 4.9.1 x32 mit -O3.

Answer 2

Haben Sie versucht, Ihr einzelnes Zeichen gegen eine Zeichenfolge der Zeichen zu vergleichen, gegen die Sie vergleichen möchten?

std::string::find_first_of()

Answer 3

Sie könnten eine Reihe von booleans schaffen und den Wert true für jedes Zeichen zuweisen in festlegen wollte. Zum Beispiel, wenn Ihr gewünschtes Set besteht aus 'a', 'd', 'e':

bool array[256] = {false}; 
array['a'] = true; 
array['d'] = true; 
array['e'] = true; 

und dann können Sie ein Zeichen überprüfen c:

std::bitset<256> b; 
b.set('a'); 
b.set('d'); 
b.set('e'); 

:

if (array[c]) ... 

Wir haben auch eine bitset für diesen Zweck verwenden könnte und Überprüfung als:

if (b.test(c)) ... 

Answer 4

Normalerweise diese Art von Test ist nicht isoliert, dh Sie nur

if(c==ch1 || c==ch2 || c=ch3) {... } 

Habe ich nicht aber

if(c==ch1 || c==ch2 || c=ch3) {... } 
else if(c==ch4 || c==ch5 || c=ch6) {... }  
else if(c==ch7 || c==ch8 || c=ch9) {... } 

if(c==ch4 || c==ch6 || c=ch7) {... } 

In diesem Fall würde ich ein Charaktereigenschaften Array aufzubauen, die die Informationen enthält, Sie wollen.

// First 2 bits contains the "type" of the character 
static const unsigned char CHAR_TYPE_BITS = 3; 
static const unsigned char CHAR_TYPE_A = 0; 
static const unsigned char CHAR_TYPE_B = 1; 
static const unsigned char CHAR_TYPE_C = 2; 
// Bit 3 contains whether the character is magic 
static const unsigned char CHAR_IS_MAGIC = 4; 

static const unsigned char[256] char_traits = { 
    ..., 
    CHAR_TYPE_A, CHAR_TYPE_B | CHAR_IS_MAGIC ... 
    ... 
} 

static inline unsigned char get_character_type(char c) { 
    return char_traits[(unsigned char)c] & CHAR_TYPE_BITS; 
} 

static inline boolean is_character_magic(char c) { 
return (char_traits[(unsigned char)c] & CHAR_IS_MAGIC) == CHAR_IS_MAGIC; 
} 

Jetzt werden Ihre Bedingungen

switch(get_character_type(c)) { 
case CHAR_TYPE_A: 
    ... 
    break; 
case CHAR_TYPE_B: 
    ... 
    break; 
case CHAR_TYPE_C: 
    ... 
    break; 
} 

if(is_character_magic(c)) { 
    ... 
} 

ich in der Regel die char_traits Variable in seine eigenen extrahieren würde beinhalten, und erzeugen, die enthalten auch ein einfaches Programm. Dies hält die Dinge leicht vorwärts zu ändern.

Answer 5

Halten Sie es einfach.

Die Suche ist linear, aber das sagt nicht die ganze Geschichte. Andere Datenstrukturen können eine konstante Suche ermöglichen, aber die Konstante kann höher als der maximale "lineare" Wert sein! Wenn Suchzeiten mit steigendem n O (1) = (100, 100, 100) und O (n) = (10, 20, 30) sind, dann können Sie sehen, dass O (n) schneller ist als O (1) für diese kleinen n.

Da es nur eine kleine Anzahl von Zeichen gibt, würde ich sehr überrascht sein, wenn die einfache lineare Suche langsamer als die Alternativen in einigen echten Code misst.

Wenn Sie sicherstellen, dass das Array sortiert ist, können Sie auch versuchen std::binary_search. Ich weiß nicht, ob es für eine kleine Anzahl von Werten schneller oder langsamer wird.

Wie immer, um sicher zu sein.