为什么String.equalsIgnoreCase如此缓慢

Question

在面试中，我遇到了一个问题，需要写一个方法来检查相似单词而不考虑大小写。

我的回答是使用每对字符的ASCII值之差。但是回家后，当我查看String.class中的实际实现时，我感到困惑——为什么它要这样实现！

我尝试比较内置方法和我的自定义方法，如下所示-

public class EqualsIgnoreCase {

    public static void main(String[] args) {
        String str1 = "Srimant @$ Sahu 959s";
        String str2 = "sriMaNt @$ sAhu 959s";

        System.out.println("Avg millisecs with inbuilt () - " + averageOfTenForInbuilt(str1, str2));
        System.out.println("\nAvg millisecs with custom () - " + averageOfTenForCustom(str1, str2));
    }

    public static int averageOfTenForInbuilt(String str1, String str2) {
        int avg = 0;
        for (int itr = 0; itr < 10; itr++) {
            long start1 = System.currentTimeMillis();
            for (int i = 0; i < 100000; i++) {
                str1.equalsIgnoreCase(str2);
            }
            avg += System.currentTimeMillis() - start1;
        }
        return avg / 10;
    }

    public static int averageOfTenForCustom(String str1, String str2) {
        int avg = 0;
        for (int itr = 0; itr < 10; itr++) {
            long start2 = System.currentTimeMillis();
            for (int i = 0; i < 100000; i++) {
                isEqualsIgnoreCase(str1, str2);
            }
            avg += System.currentTimeMillis() - start2;
        }
        return avg / 10;
    }

    public static boolean isEqualsIgnoreCase(String str1, String str2) {
        int length = str1.length();
        if (str2.length() != length) {
            return false;
        }

        for (int i = 0; i < length; i++) {
            char ch1 = str1.charAt(i);
            char ch2 = str2.charAt(i);

            int val = Math.abs(ch1 - ch2);
            if (val != 0) {
                if (isInAlphabetsRange(ch1, ch2)) {
                    if (val != 32) {
                        return false;
                    }
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    public static boolean isInAlphabetsRange(char ch1, char ch2) {
        return (((ch1 <= 122 && ch1 >= 97) || (ch1 <= 90 && ch1 >= 65)) && ((ch2 <= 122 && ch2 >= 97) || (ch2 <= 90 && ch2 >= 65)));
    }

}

输出-

使用内置（）的平均毫秒数-14

使用自定义（）的平均毫秒数-5

我发现内置方法效率低下，因为有许多检查和方法调用。这样的实现是否有任何特定原因？或者我的逻辑有什么问题吗？

非常感谢您的任何建议！

- 53by97

---

先尝试调用 averageOfTenForCustom，然后再调用 averageOfTenForInbuilt：由于 JVM 启动的原因，你的实际结果可能会有所不同。 - sp00m

将小写字母转换成大写字母并不是一项简单的任务。当您仅使用基本ASCII拉丁字符（字符距离32）时，问题还算简单。然而，当您使用整个Unicode集时，问题就相当复杂。http://www.unicode.org/faq/casemap_charprop.html - Pavel Horal

@sp00m 在交替调用它们时没有显著的区别！我之前已经检查过了。 - 53by97

考虑将0和32的差异视为“匹配”，这意味着（42）和J（74）是相等的 :-) 因此，你会返回“Jump”和“ump”的匹配结果。 - Brian

即使在ASCII字符集中，你的代码对于不在拉丁字母表中的字符也会运行错误。例如，它将对“0”和“P”或“0”和“\x10”返回true。 - phuclv

Answer 1

您的例程仅处理ASCII字符。系统例程可以处理所有Unicode字符。

考虑以下示例：

public class Test {

    public static void main(String[] args) {
        System.out.println((int) 'ě'); // => 283
        System.out.println((int) 'Ě'); // => 282 
    }

}

- Paul LeBeau

---

谨防过早和幼稚的优化。我相信无论你的代码执行什么操作，试图对equalsIgnoreCase进行优化都不会带来任何显著的改进。 - Pavel Horal

“但几乎在所有情况下，我们并不经常遇到Unicode” - 你的看法太过狭隘了。这可能在美国某些地方是正确的，但在全球范围内完全不是如此。你的玩具实现可能适用于你需要的特定领域，但库设计者需要更加稳健地构建他们的代码。 - Jack Aidley

正如我的一位教授曾经说过：“如果不需要正确性，我可以任意快速地完成它。”而且，任何天真到认为英语只包含 ASCII 字符的人都会感到惊讶。 - Voo

即使是英语，也有许多带有变音符号的字符，比如上面的单词"naïve"、"résumé"、"exposé"等。 - phuclv

if (str2.length() != length) 也是一种错误的快捷方式。例如："weißbier".length() != "WEISSBIER".length()。 - Jon Hanna

Answer 2

你的方法在许多方面都是不正确的。例如，它认为 "!" 等于 "B"，"B" 等于 "1"，但 "!" 不等于 "1"（因此它不具有可传递性，正如我们期望 equals 方法一样）。

是的，编写一个既更快又更简单的错误实现对于该方法来说相当容易。一个公平的挑战应该是编写一个正确的实现，即正确处理 JDK 实现处理的所有参数。

您还可以查看如何在Java中编写正确的微基准测试？以获取更可靠的性能测量。

- meriton

---

+1 - 这让我想起了一次我读过的讨论：“A：啊，但是你的方法比我的慢两倍。”“B：如果我被允许返回错误的结果，我可以使我的方法在常数时间内运行。” - Lieven Keersmaekers

@LievenKeersmaekers 请检查已编辑的代码，该代码考虑了字母范围！ - 53by97

好的，现在你正在处理ASCII。那么其他字符集（如ISO-8869-1）的字符呢？更不用说Unicode了吧？ - meriton

Answer 3

这可能不是唯一的原因，但事实上你的解决方案并不能适用于所有可能的字符串，这绝对是一个因素。

有些（让人烦恼的）语言环境中，两个字符可能具有相同的大写字母，但没有相同的小写字母。因此，为了能够正常运行（大部分情况下，参见土耳其语），标准实现必须在它们的大小写两种形式下逐字符比较字符串。

你的实现可能在99%的情况下都是完美无瑕的，特别是如果你只需要处理英语语言环境，但核心库实现不幸的是不能做出这样的假设。

- Nicolas Rinaudo

---

“两个小写字母，一个大写字母”的问题在土耳其语中并不存在，但在希腊语中（sigma）存在。相比之下，土耳其语相对容易，因为它仅缺少大写字母 I。 - MSalters

抱歉，我的意思是equalsToIgnoreCase在某些特定的语言环境（比如土耳其语因为i的问题）下无法正常工作，而不是遇到大小写问题 - 尽管我可以理解我表达的方式并不清楚。不过，谢谢你提供了一个实际的问题示例：我在理论上知道这个问题，但之前从未真正“见识”过它。 - Nicolas Rinaudo

Answer 4

我认为提供的 String1.equalsIgnoreCase(String2) 检查方式更好，它具有更好的字符接受性，并接受包括在 Unicode 中的所有字符值；但是，你尝试通过自定义代码来比较的是只有英文字母字符。

所以，我认为像评论员 Pavel Horel 所说的那样，由于它提供了比较所有种类的Unicode字符的复杂性，因此可能需要更多的时间。

- Am_I_Helpful

---

我认为如果String类/方法的创建者创建了两个不同的、重载的方法来区分它们，这将不会影响性能，会更好。 - 53by97

我认为，当应用程序存在（可测量的）问题时，你需要学会仅在此时关注性能。如果高性能的ASCII字符串操作对于一个应用程序至关重要，一开始就不会选择使用java.lang.String。请了解过早优化。除此之外，除非有非常好的理由不这样做，否则始终较小的API设计是更好的。 - ignis

@ignis，这位OP来到这里是因为他经历了以下三个步骤：1）接受了一个面试问题，2）回答了它，3）回家后更加深入地研究了这个问题。他不是在试图过早地优化某些生产代码，而是想要了解为什么这个库是这样的。 - Brian S

@BrianS 这仍然是过早的优化，因为他还没有在实际应用程序中测量和验证equalsIgnoreCase的现有实现是否是重要的性能瓶颈。 - Evicatos

@53by97 是的，这是Java的String类经常受到的批评。String可能应该是一个抽象类，有两个子类（ASCII和UTF-8）。现在，它是一个final UTF-16类，无法被扩展。嗯，对于大多数应用程序来说，这并不重要。 - Navin

Answer 5

我认为String.java中的这个摘录是相关的：

if (ignoreCase) {
    // If characters don't match but case may be ignored,
    // try converting both characters to uppercase.
    // If the results match, then the comparison scan should
    // continue.
    char u1 = Character.toUpperCase(c1);
    char u2 = Character.toUpperCase(c2);
    if (u1 == u2) {
        continue;
    }
    // Unfortunately, conversion to uppercase does not work properly
    // for the Georgian alphabet, which has strange rules about case
    // conversion.  So we need to make one last check before
    // exiting.
    if (Character.toLowerCase(u1) == Character.toLowerCase(u2)) {
        continue;
    }
}

- zbstof