Почему этот алгоритм не соответствует своей спецификации? Как попытаться доказать его правильность?

Question

Напишите метод getLargeAndSmallLetters, который возвращает строку, содержащую все прописные и строчные буквы ASCII в следующей форме (заглавные и строчные буквы, разделенные пробелом, группы букв, разделенные запятой, без запятой в конце):

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

Почему алгоритм был бы "академически" более правильным таким образом? Эту проблему также можно решить с помощью простой конкатенации строк.

Сначала я хочу понять, почему мое решение не является оптимальным (но правильное ИМО). Наличие C# фона и может только приблизительно угадывать причины, почему мой код не оптимален:

• for цикл проходит слишком много итераций. Я исправляю это "некрасиво", но правильно if (Character.isLetter(i)),
• это не так читабельно
• это бросает int с char s. Происходит ли какой-либо вид упаковки / распаковки, который влияет на производительность?
• путь String реализован в Java, я создаю более неизменным String s внутри пула строк с помощью конкатенации строк с + Оператор внутри моего for цикл? Будет использовать StringBuilder быть более эффективным, потому что он внутренне использует " " а также ", "String более эффективно?

Теперь я также хотел бы привести "академический аргумент", который доказывает правильность моего ответа. Вот несколько идей:

1. Компилятор оптимизирует мои "ошибки" и фактически генерирует один и тот же байт-код как для "неправильного", так и для "правильного" ответа
2. JIT-компилятор выполняет один и тот же машинный код как для "правильных", так и для "неправильных" реализаций ответов
3. Предоставить математическое доказательство правильности алгоритма

Вариант 3 кажется наиболее прямым способом доказательства правильности моих ответов.

Для вариантов 1 и 2, я думаю, мне нужно исправить цикл for, чтобы for (int i = 65; i < 91; ++i) и удалите if (Character.isLetter(i)) заявление.

Любые предложения, дополнения, исправления моих мыслей будут с благодарностью.

Answer 1

Компилятор оптимизирует мои "ошибки" и фактически генерирует один и тот же байт-код как для "неправильного", так и для "правильного" ответа

Нет, компилятор делает очень мало для оптимизации. Это может изменить некоторые ваши конкатенации строк в StringBuilderappends, но это об этом; в противном случае он просто точно воспроизводит то, что вы написали в своем коде, в форме байт-кода. В основном все умность происходит в JIT.

Вы можете очень легко увидеть, что они не производят один и тот же байт-код: декомпилируйте их с помощью javap -c <YourClass>,

JIT-компилятор выполняет один и тот же машинный код как для "правильных", так и для "неправильных" реализаций ответов

JIT выполняет код, в конце концов. Для чего-то подобного это, вероятно, будет выполнено один раз, и поэтому не стоит JIT'ing.

Но я сильно сомневаюсь, что JIT создаст один и тот же код для обоих подходов, потому что оба подхода совершенно разные.

Предоставить математическое доказательство правильности алгоритма

Формальное доказательство трудно в Java. Есть очень много тонкой семантики, которую вы должны принять во внимание в доказательстве; или, по крайней мере, докажите, что эта семантика не участвует в выполнении вашего кода.

Все, что вы действительно можете сделать, это утверждать, что это функционально эквивалентно. Например, не докажите, что это правильно, но продемонстрируйте, что это не так.

Довольно просто написать тест для этого, поскольку вы знаете правильный вывод:

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

Так что просто проверьте, что ваш код производит это, и все готово. Или, конечно, проверьте, что ваш код выдает тот же результат, что и ответ модели.

Ваш ответ на самом деле не совсем совпадает с ответом модели. Вы отрубаете , с конца; модель ответа нет.

Answer 2

Вы ведете проигрышную битву. Если ваш "доцент" не может быть обеспокоен проверкой правильности вывода вашего кода, он не потрудится прочитать доказательство правильности вашего алгоритма. Если вы чему-то научитесь из этого, так это тому, что вам часто придется страдать от дураков, так что преуспейте в этом.

Тем не менее, доказательство правильности вашего кода можно получить, показав (а) он не принимает никаких входных данных (б) на него не влияют побочные эффекты (более реалистично, а не те, которые не влияют также на решение вашего доцента), а затем В заключение, покажите (с), что реальная трассировка выполнения вашего алгоритма приводит к правильному выводу (правильному в том смысле, что он производит то же самое, что и ваш доцент).

Учитывая это, нет веской причины предпочитать одну реализацию другой. Если вы предпочитаете модель ответа за производительность, краткость или элегантность, есть лучшее и более простое решение этой проблемы, чем вы или ваш доцент нашли:

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Это ужасно, и ты не должен этого делать. Я не могу сказать, что у меня был коллега, попробовавший это в своем коде, но если этот день настанет, я буду благодарен за рецензирование кода.