Введение в аглоритмы

Хороший код

Хочется: чтобы программный код был хорошим.

Критерии хорошего кода:

  1. Понятность (Не очень измеримый критерий)

    Если код понятен, то легче добавить новые возможности, найти и исправить ошибки.

  2. Правильность (Опять неясно, насколько реально измерить для сложных программ)

  3. Эффективность (Наконец-то можно померить!)

    Эффективность бывает по времени и по памяти: насколько долго программа работает и сколько места она при этом занимает. При этом эффективность по памяти можно различать по размеру кода и по размеру данных. Эффективность обычно меряется в среднем и в худшем случаях. Время исполнения и размер занимаемой памяти в этих случаях могут быть различны, а размер кода не меняется. Поэтому, эффективность определяется минимум 5 числами. (На самом деле количество чисел больше: ведь нам не всегда ясно, как часто и какой встречается худший случай.)

  4. Универсальность

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

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

Задача

Написать код, который по данной строчке проверяет, является ли она идентификатором или нет.

Идентификатор — строчка, состоящая только из латинских букв и цифр, причем первый символ в ней обязательно буква.

Функция, отвечающая на вопрос задачи:

boolean isIdentifier(String s) {
    if (s.length() == 0) return false;
    if (!isLetter(s[0])) return false;
    for (i = 1; i < s.length(); i++) {
        if (!isLetter(s[i] && !isDigital(s[i])) {
            return false;
        }
    }
    return true;
}

Наблюдения по поводу написанного кода (что хорошо)

  1. isLetter и isDigit — отдельные функции.

    Плюсы:

    • универсальность;
    • понятность.

    Минус:

    • эффективность (время уходит на вызов функции).

    Ответ на вопрос, почему теряется эффективность при вызове функции:

    Случай 1
    if (a == b) {
    ...
}
    Случай 2
    boolean equals(a, b) {
    return a == b;
}
    . . .
    if (equals(a, b)) {
    ...
}

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

    На самом деле эту проблему за нас решит компилятор. В С для этого нужно написать макрос вместо функции. В С++ можно объявить функцию подставляемой (с ключевым словом inline). В Java JIT-компилятор может оптимизировать функцию в процессе исполнения (правда, это верно не для всех функций).

  2. В функции производится проверка не всех букв в строчке, а проверка до 1й ошибки.

    Плюс этого:

    • эффективность.

    Функция, которая проверяет, является символ буквой или нет:

    boolean isLetter (char ch) {
    return ((ch >= ’a’) && (ch <= ’z’)) || 
        ((ch >= ’A’) && (ch <= ’Z’));
}

    Считаем количество операций, которые делает написанная функция:

    • в худшем случае
      4 сравнения + 3 логических операции

    • в лучшем случае
      2 сравнения + 2 логических операции

    Попробуем уменьшить количество операций.

    Другая ("улучшенная") версия функции:

    boolean isLetter2 (char ch) {
    if (ch > ’Z’) return false;
    if (ch < ’a’) return false;
    if (ch >= ’A’) return true;
    if (ch <= ’z’) return true;
    return false;
}

    Минус:

    • в Java char занимает 2 байта и поэтому отрезков, на которых раскиданы буквы довольно много (в них нужно не запутаться).

    Пишем тоже самое в другом порядке:

    boolean isLetter3 (char ch) {
    if (ch < ’a’) return false;
        if (ch <= ’z’) return true;
    if (ch < 'A') return false;
        if (ch <= ’Z’) return true;
    return false;
}

    Понятность увеличилась. Из последних двух примеров заключаем:

  3. От порядка сравнений зависит понятность и эффективность.

    Вопрос: можно ли еще увеличить эффективность по времени(уменьшить количество операций)?

    Рассмотрим следующий вариант:

    boolean table[256] {
    //table[i] — true	если i — буква
    //table[i] — false	в противном случае
}

    Тогда требуемая функция принимает вид:

    boolean isLetter4 (char ch) {
    return table[ch];
}

    Предложенный вариант работает гораздо быстрее.

    Оценим подход с таблицей.

    Плюс:

    • эффективность (время).

    Минус:

    • эффективность (память).

    Правда, этот код особенно хорош не для Java. В Java есть автоматическая проверка выхода за границы массива.

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

    Можно воспользоваться идеей хранения нужной информации отдельно, но при этом не тратить столько памяти. А именно: 256 байт для хранения 256 нулей и единиц — ненужное расточительство. Будем хранить биты.

    byte table[32] {
    байт — 8 нулей и единиц
    значения битов: 
    1 — если соответствующий символ буква
    0 — в противном случае
}

    Функция, которая "добывает" бит с нужным номером:

    boolean isLetter5 (char ch) {
    return (table[ch / 8] & (1 << (7  - ch % 8))) != 0;
}

    Посмотрим, как работает эта функция:

    ch = 0:      table[0] & (1 << 7) = table[0] & 100000002
ср = 19:     table[19/8] & (1 << (7 - 3)) = table[2] & 000100002

    Выполняем побитовое &:

    x16 x17 x18 x19 x20 x21 x22 x23
    0 0 0 1 0 0 0 0
    0 0 0 x19 0 0 0 0

    Получаем, что ответ ненулевой, если нужный нам бит равен единице и ответ — ноль, если бит равен нулю.

    Оценим данное решение:

    Плюс:

    • эффективность по памяти;

    Минусы:

    • понятность;
    • эффективность по времени (в сравнении с предыдущим случаем).

    Тем не менее, хотя эта функция неудачна, идею хранения нужной информации в битах (а не в байтах) удобно использовать, если нам хочется написать несколько функций о типе возвращаемого значения. Создадим таблицу, где в table[t] будет храниться информация про байт t: является ли он буквой, цифрой, шестнадцатеричной цифрой и т.д. Каждый бит будет давать ответ на какой-то вопрос.

    byte table[256] {
    * * * * * x y z 
        z — isLetter
    y — isDigit
    x — isHexDigit
     ...
}

    С использованием такой таблицы легко написать функцию, отвечающую на вопрос является ли байт либо буквой, либо цифрой. Нужно просто проверить, является ли единицей один из битов на соответствующих местах.

    Последний вариант функции (с использованием switch):

    boolean isLetter6 (char ch) {
    switch(ch) {
        case ’a’:
            return true;
        case ’b’:
            return true;
        ...
        case ’Z’:
            return true;
    }
    return false;
}

    Плюсы:

    • понятность;
    • универсальность (это единственный вариант функции, когда нам не важно, что коды латинских букв идут подряд);
    • эффективность (скорость) — switch работает за константное время.

    Минус:

    • эффективность (количество кода).

    На самом деле этот способ похож на способ с таблицей: она генерируется автоматически при компиляции кода.

Мораль

Вариантов написания функций много, и нет никакого способа выбрать наилучший. Что такое хороший код непонятно. С разных точек зрения это разное.