确定字符是否属于一组已知字符的最快方法 C++

问题描述 投票:0回答:7

给定任何字符,确定该字符是否属于已知字符集(而不是容器类型)的最快方法是什么。

换句话说,实现条件的最快优雅的方式是什么:

char c = 'a';

if(c == ch1 || c == ch2 || c == ch3 ...) // Do something...

是否有一个STL容器(我想它可能是unordered_set?),我可以将字符作为键传递给它,如果键存在,它会返回true?

任何查找时间为 O(1) 的东西都适合我。

c++ c++11 stl containers unordered-set
7个回答
15
投票

我更进一步,编写了两个版本,一个基于查找数组,另一个基于使用底层哈希的集合。

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;
};

然后写了一些基准测试,添加了一些容器以便进行比较。越低越好,数据点是“字符集大小/文本大小”:

enter image description here

似乎对于短字符集和文本,

std::string::find_first_of
是最快的,甚至比使用查找数组还要快,但随着测试大小的增加,它会迅速缩小。
std::vector<bool>
似乎是“黄金分割”,
QBitArray
可能有一点不同的实现,因为它随着测试规模的增加而提前,在最大的测试中
QVector<bool>
是最快的,大概是因为它没有以下开销位访问。两个哈希集很接近,交换位置,最后也是最不重要的是
std::set

在 i7-3770k Win7 x64 机器上进行测试,使用 MinGW 4.9.1 x32 和 -O3。


9
投票

您可以创建一个布尔数组,并为所需集中的每个字符分配值

true
。例如,如果您想要的集合包含
'a', 'd', 'e'

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

然后你可以检查一个字符

c
:

if (array[c]) ... 

我们还可以使用位集来实现此目的:

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

并检查为:

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

5
投票

保持简单。

static const char my_chars[] = { 'a', 'b', 'c' };
if (std::find(std::begin(my_chars), std::end(my_chars), char_to_test))

查找是线性的,但这并不能说明全部情况。其他数据结构可能会提供常量查找,但该常量可能高于最大“线性”值!如果随着 n 的增加,搜索时间为 O(1) = (100, 100, 100) 且 O(n) = (10, 20, 30),那么您可以看到 O(n) 比 O(1) 更快这些小n。

由于字符数量很少,如果简单的线性搜索比某些“真实”代码中的替代方案慢,我会感到非常惊讶。 如果您确保数组已排序,您也可以尝试

std::binary_search

。我不知道对于少量的值来说会更快还是更慢。


一如既往,测量以确定。


2
投票

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

但是

if(c==ch1 || c==ch2 || c=ch3 ) { handle_type_a(c); } else if(c==ch4 || c==ch5 || c=ch6 ) { handle_type_b(c); } else if(c==ch7 || c==ch8 || c=ch9 ) { handle_type_c(c); } if(c==ch4 || c==ch6 || c=ch7 ) { handle_magic(c); }

优化每个 
if

语句的效率可能低于立即考虑所有这些部分。这种结构通常意味着字符组在某些方面被认为是等效的 - 这就是我们可能想要在代码中表达的内容。

在这种情况下,我将构建一个包含字符类型信息的字符特征数组。

// 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; }

现在你的条件变成了

switch(get_character_type(c)) { case CHAR_TYPE_A: handle_type_a(c); break; case CHAR_TYPE_B: handle_type_b(c); break; case CHAR_TYPE_C: handle_type_c(c); break; } if(is_character_magic(c)) { handle_magic(c); }

我通常会将 
char_traits

变量提取到其自己的包含中,并使用简单的程序生成该包含。这使得事情很容易改变。

    


1
投票

#include <cstring> bool is_separator(char c) { return std::strchr(" \f\t\v\r\n\\+-=()", c); // this includes \0! }



0
投票

std::string::find_first_of()


0
投票

#define IS_DIGIT(x) \ (static_cast<unsigned int>((x) - '0') < static_cast<unsigned int>(10)) #define IS_LOWER_LETTER(x) \ (static_cast<unsigned int>((x) - 'a') < static_cast<unsigned int>(26)) #define IS_UPPER_LETTER(x) \ (static_cast<unsigned int>((x) - 'A') < static_cast<unsigned int>(26)) #define IS_LETTER(x) \ (IS_LOWER_LETTER(x) || IS_UPPER_LETTER(x))

	
最新问题
© www.soinside.com 2019 - 2025. All rights reserved.