最有效的找出字符串是否为mixedCase的方法

Question

假设我有非常长的字符串，并且想要查看某列是否全部为小写、大写或混合大小写。例如，对于以下列：

text
"hello"
"New"
"items"
"iTem12"
"-3nXy"

文本应该是mixedCase。一个简单的算法来确定这一点可能是:

int is_mixed_case, is_all_lower, is_all_upper;
int has_lower = 0;
int has_upper = 0;
// for each row...for each column...
for (int i = 0; (c=s[i]) != '\0'; i++) {
    if (c >='a' && c <= 'z') {
        has_lower = 1;
        if (has_upper) break;
    }
    else if (c >='A' && c <= 'Z') {
        has_upper = 1;
        if (has_lower) break;
    }
}

is_all_lower = has_lower && !has_upper;
is_all_upper = has_upper && !has_lower;
is_mixed_case = has_lower && has_upper;

我相信有一种更高效的方法来完成这个任务，但是什么算法/计算方法最有效呢？

- user11954200

---

一旦你找到大小写字母各一个就属于混合大小写，这可能只需要总共两个字符。所以如果你遍历整个字符串，可能会浪费很多时间。 - jonrsharpe

@jonrsharpe -- 感谢您的建议，我已经加入了break。 - user11954200

获取第一个字符的大小写。然后使用 strspn() 在相反的情况下搜索一个字符。 - Barmar

(c >='a' && c <= 'z') 不具备可移植性。请使用 isupper() 和 islower()。 - Andrew Henle

还有...我们在谈论什么字符集？使用Unicode会变得非常复杂... ;) - Vilx-

Answer 1

如果你知道将要使用的字符编码（在代码示例中我使用了ISO/IEC 8859-15），查找表可能是最快的解决方案。这还允许你决定扩展字符集中哪些字符，例如µ或ß，你将认为是大写、小写或非字母。

char test_case(const char *s) {
    static const char alphabet[] = {
        0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
        0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,  //  ABCDEFGHIJKLMNO
        1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,  // PQRSTUVWXYZ
        0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,  //  abcdefghijklmno
        2,2,2,2,2,2,2,2,2,2,2,0,0,0,0,0,  // pqrstuvwxyz
        0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,1,0,2,0,2,0,0,0,0,  //        Š š ª
        0,0,0,0,0,1,2,0,0,2,0,2,0,1,2,1,  //      Žµ  ž º ŒœŸ
        1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,  // ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏ
        1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,  // ÐÑÒÓÔÕÖ ØÙÚÛÜÝÞß
        2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,  // àáâãäåæçèéêëìíîï
        2,2,2,2,2,2,2,0,2,2,2,2,2,2,2,2}; // ðñòóôõö øùúûüýþÿ
    char cases = 0;
    while (*s && cases != 3) {
        cases |= alphabet[(unsigned char) *s++];
    }
    return cases; // 0 = none, 1 = upper, 2 = lower, 3 = mixed
}

如chux评论所建议的，您可以将alphabet [0]的值设置为4，然后在while循环中只需要一个条件cases < 3。

- m69 ''snarky and unwelcoming''

---

能否请您解释一下上面的代码是在做什么？我不太明白它是如何工作的，等等。 - user11954200

@Shared 对于每个字符（这里假设为8位扩展ASCII），如果它是大写字母，则存储值为1，如果是小写字母，则存储值为2，如果不是字母字符，则存储值为0。然后，要检查一个字符串，您需要查找每个字符的值，并将其与变量cases进行OR运算，该变量在开始时设置为0。当您遇到第一个字母时，cases将被设置为1或2，具体取决于大小写。如果您稍后遇到另一种情况的字母，则cases将被设置为3，您就知道该字符串具有混合大小写。 - m69 ''snarky and unwelcoming''

@mr69 -- 哇，这是一个非常酷的方法。我很想看看这是否能够在大量文本输入中胜过使用标准的lower/upper。 - user11954200

@Shared 关注查找表的性能通常要考虑它们的大小。如果添加或删除一些元素，可能会出现奇怪的时间跳变。如果您不关心扩展字符并将表缩小为128个字符，或者跳过前32个控制字符并使用 *s++ -32，那么可以提高速度。这都是编译器可以进行的底层优化。 - m69 ''snarky and unwelcoming''

这个想法不错，但可以改进。将 alphabet[0] = 4; 和 (*s && cases != 3) 改为 (cases < 3)，这样可以避免重复的 *s 测试。然后将 return cases & 3;。 - chux - Reinstate Monica

@chux 好主意。当微调时，每一条指令都多余了 :-) - m69 ''snarky and unwelcoming''

Answer 2

这应该是相当高效的 - 它检查了必要的最小字符数。这假设对小写字符有偏见，因此首先检查小写字符应该稍微更有效率：

#include <ctype.h>

int ismixed( const unsigned char *str )
{
    int hasUpper = 0;
    int hasLower = 0;

    while ( *str )
    {
        // can't be both upper and lower case
        // but it can be neither
        if ( islower( *str ) )
        {
            hasLower = 1;
        }
        else if ( isupper( *str ) )
        {
            hasUpper = 1;
        }

        // return true as soon as we hit
        // both upper and lower case
        if ( hasLower && hasUpper )
        {
            return( 1 );
        }

        str++;
    }

    return( 0 );
}

根据您的输入是偏向小写还是大写，首先检查isupper()可能会更好。

- Andrew Henle

---

很遗憾没有类似fpclassify()的charclassify()函数，否则你就可以这样写：cc = charclassfy(*str); hasX |= (ISX & cc); hasY |= (ISY & cc);。 - EOF

@Andrew -- 感谢您的回答。从上面的评论中（如果您知道您只处理ASCII字母，则检查大小写的最快方法就是& 0x20），islower / isupper是否使用位运算？我猜我的问题是，islower比我在上面的问题中使用的天真实现更好在哪里？ - user11954200

@Shared C标准没有规定ASCII编码。ctypes.h定义的函数将适用于任何字符编码方式，因此具有良好的可移植性。 - Christian Gibbons

@Shared - 一般来说，你会发现大多数编译器对任何给定函数的实现都比你即兴编写的代码更优化，也更少出错（特别是对于长字符串，在这种情况下，许多库函数将解引用的字符串转换为无符号类型，以便能够每次迭代检查4个字节而不是一个）。一个好的测试方法是将代码转换为汇编语言，然后从指令角度进行比较。 - David C. Rankin

您可以通过在 if (islower((unsigned char)*str) 代码块中的赋值操作之前测试 if (hasUpper) return 1; 来提高混合字母和非字母字符串的微效率。这样可以避免在字符为非字母时进行不必要的测试。此外，该问题要求区分“全大写”、“全小写”、“混合大小写”（以及隐含的“无字母”）。 - Jonathan Leffler

Answer 3

如果我们假设使用的是ASCII编码

如果我们假设全部是字母

那么代码只需要计算“大小写”位。和字符串长度相同或者为0等于总和吗？

最初的回答：

void test_case(const char *s) {
  const char *start = s;
  size_t sum = 0;
  size_t mask = 'A' ^ 'a';
  while (*s) {
    sum += *s++ & mask;
  }
  ptrdiff_t len = s - start;
  sum /= mask;
  if (len == 0) puts("Empty string");
  else if (sum == 0) puts("All UC");   
  else if (sum == len) puts("All LC");
  else puts("Mixed");
}

注意：稍作修改，也可适用于EBCIDIC。"Original Answer"翻译成"最初的回答"。

- chux - Reinstate Monica

---

为什么不使用位运算而不是计数？ - m69 ''snarky and unwelcoming''

如果所有或几乎所有的使用情况都是大写或小写，那么最简单的方法就是添加。在审查后，我认为这个是最普遍有效的方法。 - chux - Reinstate Monica

Answer 4

这个字符串只包含字母吗？如果是，可以检查任意两个相邻字符是否大小写不同。

#include <ctype.h>
#include <errno.h>
int mixed_case(const char *str) {
   if(!str){
      // sanity check
      errno = EINVAL;
      return -1;
   }

   // can't be mixed-case without more than one letter
   if(str[0] == '\0' || str[1] == '\0'){
      return 0;
   }

   for(int i = 1; str[i] != '\0' ; ++i) {
      if (!islower(str[i]) ^ !islower(str[i-1])) {
         // if two letter next to each other are not the same case, it's mixed case
         return 1;
      }
   }
   // didn't find any mismatches, so not mixed case
   return 0;
}

采用类似的方法，但不是检查连续字符，而是找到第一个字母字符，并将其与任何其他字母字符进行比较。这应该能够处理包含非字母字符的字符串。

int mixed_case(const char *str) {
   if(!str){
      // sanity check
      errno = EINVAL;
      return -1;
   }

   // can't be mixed-case without more than one letter
   if(str[0] == '\0' || str[1] == '\0'){
      return 0;
   }

   // find the first alphabetical character and store its index at 'i'
   int i = 0;
   for(;!isalpha(str[i]) || str[i] == '\0'; ++i);

   if(str[i] == '\0') {
      // no alphabetical characters means you can't have mixed cases
      return 0;
   }

   // See if any of the other alphabetical characters differ from the case of the first one
   for(int j = i+1; str[j] != '\0' ; ++j) {
      if(isalpha(str[j]) && (!islower(str[i]) ^ !islower(str[j]))) {
         return 1;
      }
   }
   // didn't find any mismatches, so not mixed case
   return 0;
}

- Christian Gibbons

---

这是一个有趣的方法，但我想一个文件可以被命名为类似于FileVersion-1.txt这样的东西，因此它可以包含非字母字符（在问题中添加了一个示例）。 - user11954200

@Shared 已更新另一个版本，应该可以处理非字母字符串。不确定它在效率上与更传统的方法相比如何。 - Christian Gibbons

islower(str[i]) ^ islower(str[j]) 并不完全正确。islower() 返回一个 int 类型的值，当为小写字母时返回非零值。然而，即使两个字符都是小写字母，islower(str[i]) 和 islower(str[j]) 返回的值可能不同。^ 在这里执行的是按位异或操作，而需要的是逻辑异或操作。建议使用 !islower(str[i]) ^ !islower(str[j]) 来实现逻辑异或操作。 - chux - Reinstate Monica

@chux 很好的发现。已更新。 - Christian Gibbons

Answer 5

这是一个用于检测Unicode混合大小写单词的正则表达式。

"\s?(\p{Lu}[\p{Lu}+\p{Ll}]*\p{Lu}*)|(\p{Lu}*[\p{Lu}+\p{Ll}]*\p{Lu}+)\s?"

看看它的实际效果 https://regex101.com/r/ndLL9k/3

- Markus

Answer 6

另一种不假设ASCII或所有字母的方法。

评估第一个char，然后执行两个优化循环中的一个。

这将在第一个不匹配时退出循环。由于while()循环只进行单个测试，因此可以实现最佳性能。

#include <ctype.h>

void case_test(const char *s) {
  if (*s == '\0') {
    puts("Empty string");
    return;
  }

  unsigned char *us = (unsigned char *)s; // use unsigned char with is***() functions.
  if (islower(*us)) {
    while (islower(*us)) {
      us++;
    }
    if (*us) {
      puts("Mixed or not alpha");
    } else {
      puts("All lower");
    }
  } else if (isupper(*us)) {
    while (isupper(*us)) {
      us++;
    }
    if (*us) {
      puts("Mixed case or not alpha");
    } else {
      puts("All upper");
    }
  } else {
    puts("Not alpha");
  }
}

操作员添加了包括非字母的情况。下面的代码可以迅速处理这种情况。

void case_test_with_non_letters(const char *s) {
  unsigned char *us = (unsigned char *)s; // use unsigned char with is***() functions.

  //  Find first alpha or null character
  while (!isalpha(*us) && *us) {
    us++;
  }

  if (*us == '\0') {
    puts("Empty string");
    return;
  }

  if (islower(*us)) {
    while (!isupper(*us) && *us) {
      us++;
    }
    if (isupper(*us)) {
      puts("Mixed");
    } else {
      puts("All letters lower");
    }
  } else if (isupper(*us)) {
    while (!islower(*us) && *us) {
      us++;
    }
    if (*us) {
      puts("Mixed case");
    } else {
      puts("All letters upper");
    }
  } else {
    puts("Not alpha");
  }
}

- chux - Reinstate Monica

---

问题中的示例以非字母字符开头并包含非字母字符，但可以是混合大小写、大写或小写。 - Jonathan Leffler

@JonathanLeffler 指出了一个好观点 - 但这是由于 OP 的编辑。我会重新审查的。 - chux - Reinstate Monica

Answer 7

97 = a = 1100001

65 = A = 0100001

你只需要测试第6位的位数。

- user11978762