检查char数组中前导字符的最快方法是什么？ [英] What is the fastest way to check the leading characters in a char array?

问题描述

我在代码中遇到了瓶颈，所以这个问题的主要问题是性能。

我有一个十六进制校验和，我想检查一个char数组的前导零。 。这就是我在做什么：

  bool starts_with（char * cksum_hex，int n_zero）{
 bool flag {true}; 
 for（int i = 0; i< n_zero; ++ i）
标志& =（cksum_hex [i] =='0'）; 
返回标志； 
} 
  

如果 cksum_hex 的 n_zero 前导零。但是，对于我的应用程序，此功能非常昂贵（占总时间的60％）。换句话说，这是我的代码的瓶颈。因此，我需要改进它。

我还检查了 std :: string :: starts_with 在C ++ 20和我观察到性能没有差异：

  //我必须将cksum转换为字符串
 std :: string cksum_hex_s（cksum_hex）; 
 cksum_hex_s.starts_with（ 000）; //检查3个前导零
  

有关更多信息，我在使用 g ++ -O3 -std = c ++ 2a ，我的gcc版本是9.3.1。

问题

• 检查char数组中前导字符的更快方法是什么？


• 使用 std :: string :: starts_with <有没有更有效的方法？ / code>？


• 按位运算在这里有帮助吗？

解决方案

如果您修改了函数以尽早返回

  bool starts_with（char * cksum_hex， int n_zero）{
 for（int i = 0; i  {
 if（cksum_hex [i]！='0'）返回false; 
} 
返回true； 
} 
  

在 n_zero 和 false 结果。否则，也许您可​​以尝试分配全局字符数组'0'并使用 std :: memcmp ：

  //使其与您所需的一样大
 constexpr char cmp_array [4] = {'0' ，'0'，'0'，'0'}; 
 bool starts_with（char * cksum_hex，int n_zero）{
 return std :: memcmp（cksum_hex，cmp_array，n_zero）== 0; 
} 
  

这里的问题是，您需要假设最大可能值 n_zero 。

I reached a bottleneck in my code, so the main issue of this question is performance.

I have a hexadecimal checksum and I want to check the leading zeros of an array of chars. This is what I am doing:

bool starts_with (char* cksum_hex, int n_zero) {
  bool flag {true};
  for (int i=0; i<n_zero; ++i)
    flag &= (cksum_hex[i]=='0');
  return flag;
}

The above function returns true if the cksum_hex has n_zero leading zeros. However, for my application, this function is very expensive (60% of total time). In other words, it is the bottleneck of my code. So I need to improve it.

I also checked std::string::starts_with which is available in C++20 and I observed no difference in performance:

// I have to convert cksum to string
std::string cksum_hex_s (cksum_hex);
cksum_hex_s.starts_with("000");     // checking for 3 leading zeros

For more information I am using g++ -O3 -std=c++2a and my gcc version is 9.3.1.

Questions

• What is the faster way of checking the leading characters in a char array?
• Is there a more efficient way of doing it with std::string::starts_with?
• Does the bitwise operations help here?

解决方案

If you modify your function to return early

bool starts_with (char* cksum_hex, int n_zero) {
  for (int i=0; i<n_zero; ++i)
  {
    if (cksum_hex[i] != '0') return false;
  }
  return true;
}

It will be faster in case of big n_zero and false result. Otherwise, maybe you can try to allocate a global array of characters '0' and use std::memcmp:

// make it as big as you need
constexpr char cmp_array[4] = {'0', '0', '0', '0'};
bool starts_with (char* cksum_hex, int n_zero) {
    return std::memcmp(cksum_hex, cmp_array, n_zero) == 0;
}

The problem here is that you need to assume some max possible value of n_zero.

Live example

=== EDIT ===

Considering the complains about no profiling data to justify the suggested approaches, here you go:

• Benchmark results comparing early return implementation with memcmp implementation
• Benchmark results comparing memcmp implementation with OP original implementation

Data used:

const char* cs1 = "00000hsfhjshjshgj";
const char* cs2 = "20000hsfhjshjshgj";
const char* cs3 = "0000000000hsfhjshjshgj";
const char* cs4 = "0000100000hsfhjshjshgj";

memcmp is fastest in all cases but cs2 with early return impl.

这篇关于检查char数组中前导字符的最快方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！