为什么该算法不遵守其规范?如何尝试证明其正确性

Question

写方法 getlargeandsmallletters 返回字符串 在以下 形式（上层和小写字母，被空间隔开，字母 由逗号隔开，最后没有逗号）：

a a，b b，c c，d d，e e，... z z

该算法的规范不提供有关实施细节的任何详细信息，即使用StringBuilder构造，效率指南算法必须符合实现的可读性或任何最佳实践。

我的算法版本，该算法编译并返回所需的输出

public static String getLargeAndSmallLetters() {
    StringBuilder builder = new StringBuilder();
    for (int i = 64; i < 96; ++i) { // WRONG: hard coded
        if (Character.isLetter(i)) {
            String upper = Character.toString((char)i);
            String lower = Character.toString((char)(i+32));
            builder.append(upper + " " + lower + ", "); // WRONG: in loop
        }
    }
    String result = builder.toString();
    result = result.substring(0, result.length() - 2);
    return result;
 }

我的演出可能希望看到的是像这样的for循环

for (char lower = 'a'; lower <= 'z'; ++lower) {
    Character upper = Character.toUpperCase(lower);
    builder.append(upper)
           .append(" ")
           .append(lower)
           .append(", ");
}

为什么这种算法在学术上会更正确？这也可以通过简单的字符串串联解决。

我首先想了解为什么我的解决方案是不是最佳的（但是正确 imo）。具有C＃背景，只能大致猜测我的代码不是最佳的原因：

• for循环经过太多迭代。我以"丑陋"但使用if (Character.isLetter(i))正确的方式纠正了这一点。
• 它不那么可读
• 它将int s投入到char s。是否有任何影响性能的拳击/拆箱？
• 在Java中实现String的方式，我是通过使用for循环中的+操作员使用字符串串联在字符串池中创建更多不可变的String s？使用StringBuilder是否会更有效，因为它在内部重用" "和", " String S更有效地？

现在，我也想做的就是提供一个"学术论据"，证明了我的回答的正确性。这里有一些想法：

1. 编译器将我的"错误"优化，并实际生成"错误"one_answers"正确"答案的相同字节代码
2. JIT编译器执行"正确"one_answers"错误"答案实现的相同机器代码
3. 提供算法正确性的数学证明

选项3似乎是证明我对我的答案正确性的最直截了当的方式。

对于选项1和2，我想我需要将循环更正为for (int i = 65; i < 91; ++i)并删除if (Character.isLetter(i))语句。

任何建议，加法，对我的想法的更正都将不胜感激。

Answer 1

编译器优化我的"错误"，并实际生成"错误"one_answers"正确"答案的相同字节代码

否，编译器通过优化的方式很少。它可能会将您的某些字符串串联变成StringBuilder appends，仅此而已。否则，它只是忠实地复制了您在代码中以字节码形式编写的内容。基本上所有的智慧发生在JIT中。

您可以很容易地看到它们不会产生相同的字节码：用javap -c <YourClass>进行反复编译。

JIT编译器执行"正确"one_answers"错误"答案实现的相同机器代码

最终，JIT确实执行了代码。对于这样的事情，它可能会执行一次，因此不值得。

，但我强烈怀疑JIT是否会为这两种方法产生相同的代码，因为这两种方法都是完全不同的。

提供了算法正确性的数学证明

在Java中，正式证明很难。您必须在证明中考虑到很多微妙的语义。或者，至少证明这些语义不参与您的代码执行。

您真正能做的就是断言它在功能上是等效的。如所示，不是证明这是正确的，而是证明它不是不正确的。

为此编写测试非常容易，因为您知道正确的输出：

A a, B b, C c, ...

因此，只需检查您的代码就会产生它，然后您就完成了。或者，当然，检查您的代码是否产生与模型答案相同的输出。

您的答案实际上并没有与模型答案相同。您从末尾砍下,；模型答案没有。

Answer 2

您正在与一场失败的战斗作斗争。如果您的"讲者"不愿意检查您的代码是否产生正确的输出，那么他将不愿意阅读算法的正确性证明。如果您从中学到一件事，那就是您通常必须遭受愚蠢的痛苦，所以要善于善待。

也就）然后结论（c）表明您的算法的真实执行轨迹会导致正确的输出（正确的输出，因为它与您的doccent产生了相同的东西）。

考虑到这一点，没有一个充分的理由更喜欢一种实现。如果您更喜欢模型的答案，以表现出色，简洁或优雅，那么对于您或您的讲者而言，有更好，更简单的解决方案：

：

public static String getLargeAndSmallLetters() {
    return "A a, B b, C c, D d, E e, F f, G g, H h, I i, J j, K k, L l, M m, N n, O o, P p, Q q, R r, S s, T t, U u, V v, W w, X x, Y y, Z z";
}

您可以使其更具可读性：

public static String getLargeAndSmallLetters() {
    return String.format("%s%s",
        "A a, B b, C c, D d, E e, F f, G g, H h, I i, J j, K k, L l, M m, ",
        "N n, O o, P p, Q q, R r, S s, T t, U u, V v, W w, X x, Y y, Z z");
}

注意：for-通过char S循环可怕，您不应该这样做。我不能说我有一个同事在他的代码中尝试一下，但是如果那天到了，我将感谢同行代码评论。