Введение

Цель этого курса — в первую очередь научиться писать «хороший» код. Что такое «хороший»? Рассмотрим некоторые критерии «хорошести» кода:

1. Понятность
   необходима для:
   • добавления новых возможностей
   • нахождения и исправления ошибок
2. Правильность
3. Эффективность (бывает разной — в среднем и в худшем случае)
   • эффективность по времени
   • по памяти
   • по размеру кода
4. Универсальность
   • возможность применения к разным задачам
   • устойчивость к смене платформы

Заметим, что большинство этих критериев не поддаются какой-либо численной оценке.

Измерить из этих четырех критериев можно только один — эффективность. При этом если эффективность в среднем случае обычно можно вычислить, то все равно эффективность работы программы в каждый конкретный момент трудно оценить из-за «худших» случаев. Все зависит от того, насколько часто бывают такие случаи. Если один раз в жизни программа работает за время на порядок больше среднего, то скорее всего это нас устроит, но если «худший» случай случается каждый день, то уже нет.
Правильность — тоже часто неформальный критерий. Если программа небольшая, то конечно можно доказать ее правильность, но для больших программ в правильность можно только поверить; например, после прохождения программой большого количества тестов.

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

Пример:
Задача. Идентификатор — это строка, содержащая латинские буквы и цифры, первый символ которой буква. Напишите функцию, которая проверяет, является ли данная строка идентификатором.

Решение. Пока будем считать, что у нас есть написанная функция isLetter(), isDigit(). Тогда решение будет выглядеть примерно так:

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]) && !isDigit(s[i])) return false;
	}
	return true;
}

Итак, насколько хорошо написана функция isIdentifier?

1. isLetter, isDigit — отдельные функции: это дает увеличение понятности, универсальности кода, но эффективность по времени падает (уходит некоторое время на вызов функции). Правда надо отметить, что JIT–компилятор будет оптимизировать вызов этой функции, если к ней будет происходить много обращений.
2. В цикле мы проверяем не все буквы, а до первой ошибки, таким образом увеличивается эффективность по времени.
3. Мы вызываем каждый раз метод s.length() при проверке «i < s.length()»: это ухудшение эффективности по времени, при этом ничем не обусловленное — лучше написать «N = s.length()»перед циклом, а потом счетчик сравнивать с N.

Функции isLetter(char ch) и isDigit(char ch) схожи, напишем функцию isLetter(char ch):
Вариант 1.

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

Оказывается, эта функция написана не совсем оптимально: в лучшем случае здесь происходит 2 сравнения и 2 логических операции, в худшем — 4 сравнения и 3 логических операции.

Вариант 2. Более эффективен по времени работы.

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

Действительно, тут в лучшем случае происходит 1 сравнение, в худшем — 4, но эта функция менее понятна, чем предыдущая, потому что возможно, нам придется добавить промежутки символов, которые являются буквами. Например, на Java можно писать на разных языках, поэтому нужно включить в функцию проверку, не является ли символ русской буквой, китайским иероглифом и т. п. Эта функция менее понятна, потому что не очевидно, как добавить еще промежутки букв. Исправим это:

Вариант 3. Более понятный

boolean isLetter(char ch) {
	//промежуток a...z
	if (ch < 'a') return false;	if (ch <= 'z') return true;
	
	//промежуток A...Z
	if (ch < 'A') return false; 	if (ch <= 'Z') return true;
	
	//в случае если необходимо проверить еще один промежуток, 
	//добавляем аналогичную проверку
	
	return false;
}

Этот вариант более понятен, чем предыдущий, при этом настолько же эффективный по времени работы.

Вариант 4. Принципиально другой

Пусть у нас есть таблица:
boolean table[256] — table[i] = true, если символ с номером i — буква, и false — иначе.

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

В этом случае увеличивается эффективность по времени, зато теперь наша программа использует какое-то ощутимое количество памяти (а в случае с 2-х байтными char-ами тем более), но зато понятность — почти идеальная.

Вариант 5. Улучшим эффективность по памяти Пусть у нас есть таблица byte table[256 / 8 = 32] — представим наш массив как 8 * 32 = 256 бит, тогда бит с номером i равен 1, если символ с номером i — буква, и false — иначе.

boolean isLetter(char ch) {
	//нужный нам бит записан в элементе с номером ch / 8, 
	//а в этом байте у него номер ch % 8 с начала, т. е. 7 – ch % 8 с конца. 
	return (table[ch / 8] & (1 << (7 – ch % 8))) != 0;
}

Тут безусловно эффективность по памяти возросла в 8 раз по сравнению с предыдущим вариантом, но зато упала эффективность по времени и понятность упала настолько, что этот вариант приемлем только при наличии приведенного комментария перед return.

Вариант 6. Еще один

boolean isLetter(char ch) {
	switch (ch) {
		case 'a':
			return true;
		case 'b':
			return true;
		case 'c':
			return true;
		...
		//и так далее
	}
}

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

А теперь вспомним, что нам нужно написать не только функцию isLetter(char ch), но и isDigit(char ch) — для этого часто используется следующая конструкция: массив байтов для каждого массива, в котором каждый бит отвечает за некоторое свойство, в частности последний равен 1, если символ — буква, предпоследний равен 1, если символ — цифра, бит перед ним равен 1, например если символ — шестнадцатиричная цифра и т. п. Также такая конструкция позволяет эффективнее писать функции вида isLetterOrIsDigit(char ch) — функция, проверяющая является ли переданный символ буквой или цифрой.

Пример.

byte table[256] — в i-ом элементе записаны свойства i-ого символа: 0-й бит равен 1, если символ является буквой, 1-й бит равен 1, если символ является цифрой и т. д.

boolean вида isLetterOrIsDigit(char ch){
	//0x03 = 00000011, т. е. если в table[i] один из последних двух битов не равен 0, т. е. 
	//если символ — буква или цифра, выражение ниже не равно нулю.
	
	return (table[i] & 0x03) != 0;
}

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