Мысль про алгоритмы (как читать, как писать)

[bf_xor]

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

Цитата:
"Вот (слегка сокращенный) фрагмент кода, осуществляющего встав-
ку в двусвязный список в GNU Classpath. Он выглядит невинно, но можете ли вы в
уме убедиться в его корректности, не рисуя на бумаге диаграмм для трех возможных
случаев и не отслеживая последовательно влияние каждой строки кода на диаграмму?"

public void add(int index, Object o) {
    Entry e = new Entry(o);
    if (index < size) {
        Entry after = getEntry(index);
        e.next = after;
        e.previous = after.previous;
        if (after.previous == null)
            first = e;
        else
            after.previous.next = e;
        after.previous = e;
    } else if (size == 0) {
        first = last = e;
    } else {
        e.previous = last;
        last.next = e;
        last = e;
    }
    size++;
}

Что заметил: если читать этот алгоритм сверху-вниз, то он действительно сложен для понимания в уме. ИМХО это происходит из-за того, что приходится держать в голове не только текущие условия, но и то, что что-то будет потом (следующие группы else). Т.е. мы имеем дело с обычной ограниченностью "оперативной памяти" человеческого мозга.
Однако, если алгоритм рассматривать сниузу-вверх, то получим:
1) Счётчик у нас будет увеличен в любом случае (это правильно)
2) Если мы добавляем элемент в конец списка, то имеем дело с последним блоком else. Правильность проверяется на счёт раз.
3) Если длина списка нулевая, то имеем дело вообще с фактически одним присваиванием ( first = last = e;). Очевидно, что это верно.
4) Соответственно, нам надо абстрагироваться от всего, и смотреть на код добавления в середину списка. Фактически, речь идёт о декомпозиции кода на функции в уме:

Entry after = getEntry(index);
        e.next = after;
        e.previous = after.previous;
        if (after.previous == null)
            first = e;
        else
            after.previous.next = e;
        after.previous = e;

Разбираем:
а) Создали элемент для промежуточного хранения элемента по индексу вставки.
б) Для нового элемента устанавливаем следующим элемент к промежуточный.
в) Предыдущим для нового элемента устанавливаем предыдущий элемент временно.
г) Если новый элемент является первым - делаем его таковым, иначе приводим в соответствие индекс следующего элемента, для предыдущего элемента нашей новой записи (звучит стрёмно, но вполне очевидно)
д) Для промежуточного элемента устанавливаем предком нашу новую запись.

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

Ну или есть ещё вариант писать код в обратном порядке:

public void add(int index, Object o) {
    Entry e = new Entry(o);
    if (index == size){
        e.previous = last;
        last.next = e;
        last = e;
    } else if (size == 0) {
        first = last = e;
    } else
        Entry after = getEntry(index);
        e.next = after;
        e.previous = after.previous;
        if (after.previous == null)
            first = e;
        else
            after.previous.next = e;
        after.previous = e;
    }
    size++;
}

ИМХО это также несколько облегчает задачу по пониманию.