Как не надо писать программы

Усердие всё превозмогает
     Козьма Прутков, Мысли и афоризмы, Мысль № 84

Бывает, что усердие превозмогает и рассудок.
     Козьма Прутков, Неопубликованные мысли и афоризмы, Мысль № 27

На одном из собеседований мне задали вопрос: есть ли некий криминал в приведённом ниже коде?

. . .
for (i = 0; i<MAGIC_VALUE; i++) {
  int k;
  . . .
}
. . .

Правильный ответ очевиден любому программисту: самая большая неприятность, которая может произойти, заключается в выделении в стеке памяти под переменную k при каждой итерации цикла. Но во-первых, скорее всего, компилятор это соптимизирует, а во-вторых, даже если произойдёт худшее, вряд ли это сильно скажется на производительности. Следовательно, писать так можно и нужно, потому что выигрыш от понятности исходного кода во много раз перевешивает гипотетический проигрыш от лишней операции.

Однако, всё сказанное выше верно лишь для промышленного программирования, когда важно решить конкретную задачу, затратив при этом минимум времени и усилий. Но случается, что программа — не прикладной инструмент, а произведение искусства. И вот тогда...

Однажды, будучи студентами, мы с одним товарищем вели «священную войну» на тему «C vs. Pascal». В качестве одного из доказательств было сказано, что одна и та же программа на C записывается значительно короче, чем на Pascal’е. Мы тогда ничего не знали про IOCCC, а потому постановили написать одну и ту же программу на двух языках и сравнить исходные тексты.

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

Итак, нормальный программист написал бы так:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef struct _node {
  struct _node *left, *right;
  char character;
  int count;
} NODE;

void write (NODE *n)
{
  if (n->left!=NULL) write(n->left);
  printf("%c%9d\n",n->character,n->count);
  if (n->right!=NULL) write(n->right);
}

int main()
{
  NODE *root = NULL, **h;
  char t;
  while ((t = getch())>31) {
    h = &root;
    while (*h) {
      if ((*h)->character!=t) 
        h = (t>(*h)->character) ? &(*h)->right : &(*h)->left;
      else {
        (*h)->count++;
        break;
      }
    }
    if (*h==NULL) {
      *h = malloc(sizeof(NODE));
      (*h)->character = t;
      (*h)->left = (*h)->right = NULL;
      (*h)->count = 1;
    }
  }
  write(root);
  return 0;
}

Разумеется, тут не хватает кода для освобождения памяти, но всё равно при первой же «оптимизации» он был бы выкинут.

Если ставить задачу «написать программу, которая бы...», то на этом можно успокоиться. Однако мы-то ставили перед собой совсем другую цель! Итак, начинаем изобретать.

Первое, что приходит в голову, выкинуть все хидры с прототипами функций и типы функций — C++ такого не позволит, а вот C — запросто. Ну, и заодно сократить все имена переменных до одного символа и заменить все сравнения с NULL простой проверкой «ненулёвости»:

typedef struct _n {
  struct _n *l, *r;
  char c;
  int n;
} N;

w (N *n)
{
  if (n->l) w(n->l);
  printf("%c%9d\n",n->c,n->n);
  if (n->r) w(n->r);
}

main()
{
  N *r = 0, **h;
  char t;
  while ((t = getch())>31) {
    h = &r;
    while (*h) {
      if ((*h)->c!=t) 
        h = (t>(*h)->c) ? &(*h)->r : &(*h)->l;
      else {
        (*h)->n++;
        break;
      }
    }
    if (!*h) {
      *h = malloc(sizeof(N));
      (*h)->c = t;
      (*h)->l = (*h)->r = 0;
      (*h)->n = 1;
    }
  }
  w(r);
}

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

Очевидно, что char поместится в int. Во многих моделях памяти (например, tiny в компиляторе Turbo C для DOS или flat — единственной в Visual C/C++ 6.0) размер указателя также равен размеру int. Следовательно, структуру можно заменить массивом, в нулевом элементе которого лежит символ, в первом — счётчик, во втором и третьем — указатели на левое и правое поддеревья. Заодно оптимизируем функцию w() — пусть она проверяет на NULL не поддеревья, а сам узел. Не забудем при этом, что calloc(), в отличие от malloc(), обнуляет выделенную память, и получим гораздо более компактный код:

w (int *q)
{
  if (q) {
    w(q[2]);
    printf("%c%9d\n",q[0],q[1]);
    w(q[3]);
  }
}

main()
{
  int t, *r = 0, **h;
  while ((t = getch())>31) {
    h = &r;
    while (*h) {
      if ((*h)[0]!=t) 
        h = &((*h)[2+((*h)[0]<t)]);
      else {
        (*h)[1]++;
        break;
      }
    }
    if (!*h) {
      *h = calloc(sizeof(int),4);
      (*h)[0] = t;
      (*h)[1] = 1;
    }
  }
  w(r);
}

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

1. Заменяем нулевой элемент массива разыменованным указателем.
2. Вместо sizeof(int) вписываем некое заведомо достаточное число.
3. Не записываем 1 в первый элемент массива, а вместо этого увеличиваем его на 1 непосредственно при выводе.
4. Замечаем, что конструкция (*h) встречается слишком часто, и заменим её при помощи директивы #define.
5. Заменим != на - (минус).

И — вот она, изуродованная до неузнаваемости, но всё же работоспособная программа!

#define H (*h)

w (int *q)
{
  if (q) {
    w(q[2]);
    printf("%c%9d\n",*q,q[1]+1);
    w(q[3]);
  }
}

main()
{
  int t, *r = 0, *H;
  while ((t = getch())>31) {
    h = &r;
    while H
      if (*H-t) 
        h = &(H[2+(*H<t)]);
      else {
        H[1]++;
        break;
      }
    if (!H) *(H = calloc(4,4)) = t;
  }
  w(r);
}

Финальный штрих перед отправкой кода заказчику — удаление лишних пробелов:

#define H (*h)
w(int*q){if(q){w(q[2]);printf("%c%9d\n",*q,q[1]+1);w(q[3]);}}
main(){int t,*r=0,*H;while((t=getch())>31){h=&r;while H
if(*H-t)h=&(H[2+(*H<t)]);else{H[1]++;break;}}if(!H)*(H=calloc(4,4))=t;}w(r);}

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

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

И это правильно.

23.09.2003