为什么这个算法不符合它的规范？如何尝试证明其正确性？

Question

Write the method getLargeAndSmallLetters that returns a String that contains all upper- and lowercase ASCII letters in the following form (upper- and lowercase letters separated by white space, letter groups separated by comma, no comma at the end):

A a, B b, C c, D d, E e, ..., Z z

算法的规范不包含任何关于实现细节的细节，即 StringBuilder 构造的使用、算法必须满足的效率指南或关于实现可读性的任何最佳实践。

我的编译算法版本和returns所需的输出

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(", ");
}

为什么算法会 "academically" 这样更正确？这也可以通过简单的字符串连接来解决。

我首先想了解为什么我的解决方案不是最佳（但正确 IMO）。有 C# 背景，只能粗略猜测我的代码不是最优的原因：

for 循环迭代次数过多。我用 "ugly" 更正了这个，但用 if (Character.isLetter(i)).
可读性差
它将 ints 转换为 chars。是否发生了任何影响性能的 boxing/unboxing？
String 在 Java 中的实现方式，我是不是在字符串池中使用字符串连接和 + 运算符在字符串池中创建了更多不可变的 Strings我的 for 循环？使用 StringBuilder 是否会更有效，因为它在内部更有效地重用 " " 和 ", " String？

现在我还想做的是提供一个"academical argument"来证明我的答案是正确的。这里有一些想法：

编译器优化了我的 "mistakes"，实际上为 "wrong" 和 "correct" 答案
JIT 编译器对 "correct" 和 "wrong" 答案实现执行相同的机器码
提供算法的数学proof of correctness

选项 3 似乎是向我证明我的答案正确性的最直接方式。

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

任何对我想法的建议、补充和更正都将不胜感激。

Answer 1

The compiler optimizes my "mistakes" away and actually generates the same byte code for both the "wrong" and "correct" answer

不，编译器通过优化很少。它可能会将您的某些字符串连接更改为 StringBuilder appends，但仅此而已；否则它只是忠实地以字节码形式重现您在代码中编写的内容。基本上所有的聪明都发生在 JIT 中。

您可以很容易地看出它们不会产生相同的字节码：用 javap -c <YourClass>.

反编译它们

The JIT compiler executes the same machine code for both "correct" and "wrong" answer implementations

JIT 最终会执行代码。对于像这样的东西，它可能会执行一次，因此不值得 JIT。

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

Provide a mathematical proof of correctness of the algorithm

在 Java 中很难进行正式证明。在证明中必须考虑大量微妙的语义；或者，至少，证明这些语义不涉及您的代码的执行。

你真正能做的就是断言它在功能上是等价的。就像，不是证明它是正确的，而是证明它不是不正确的。

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

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

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

您的答案实际上与标准答案并不完全相同。你从最后砍掉 , ；模型答案没有。

Answer 2

你正在打一场必败仗。如果你的 "docent" 懒得检查你的代码是否产生了正确的输出，他就不会懒得阅读你的算法正确性的证明。如果你从中学到一件事，那就是你将经常遭受愚弄，所以要善于它。

就是说，可以通过以下方式证明您的代码的正确性：(a) 它不接受任何输入 (b) 它不受副作用的影响（更现实地说，不会受到那些不会影响您的副作用的影响）讲解员的解决方案），然后通过显示 (c) 得出结论，您的算法的真实执行跟踪会产生正确的输出（正确的原因在于它产生与您的讲解员相同的结果）。

鉴于此，没有充分的理由偏爱一种实现而不是另一种实现。如果您更喜欢性能、简洁或优雅的模型答案，那么这个问题有比您或您的讲解员找到的更好更简单的解决方案：

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-循环遍历 chars 很糟糕，您不应该这样做。我不能说我有一位同事在他的代码中尝试过，但如果那一天真的到来，我将感谢同行代码审查。

为什么这个算法不符合它的规范？如何尝试证明其正确性？

Why would this algorithm not adhere to its specification? How to attempt proving its correctness?

java

computer-science

correctness

proof-of-correctness