SICP по-русски

На самом деле построить процедуру successive-merge совсем не сложно. Алгоритм наших действий прост. Мы будем хранить все деревья и листья в упорядоченном по возрастанию веса списке. Раз так, два самых легких элемента всегда будут находиться на двух первых позициях в списке. Стало быть, нам достаточно на каждом этапе алгоритма последовательного слияния брать два первых элемента из списка, соединять их в один и возвращать полученное дерево обратно в список (при этом оно в нем займет место в соответствии со своим весом, то есть список сохранит свойство упорядоченности). На каждом шаге количество элементов в списке уменьшается на один. Заканчиваем слияния мы тогда, когда в списке остался ровно один элемент, который и является искомым деревом Хаффмана.

Процедура successive-merge, реализующая эту идею, представлена ниже:

(define (successive-merge trees)
  (if (null? (cdr trees))
      (car trees)
      (successive-merge (adjoin-set (make-code-tree (car trees)
                                                    (cadr trees))
                                    (cddr trees)))))

Определение не лишено некоторой элегантности.

Просмотрел сегодня первую лекцию (1-а) с полученных DVD. Сделал для себя следующие заметки.

1. Первую лекцию читал Хэл Абельсон. Оказывается, он левша.
2. Очень понравилось сравнение computer science и геометрии. Действительно, именно формализация способа мышления делает обе области знания тем, что они есть.
3. Очень хорошее объяснение отличий между декларативными и императивными знаниями. Просто, но важно.
4. Отличное описание абстракции черного ящика. Очень просто и понятно.
5. Разговор об объектно-ориентированном программировании. Напоминаю, на дворе середина 80-ых годов. Официально С++ еще не существует. ООП означает Smalltalk. То есть это еще не мейнстрим.
6. Отличный акцент на трех основных составляющих языка программирования: примитивах, средствах комбинирования и средствах абстракции.
7. Очень позабавило выделение соответствующих скобок в допотопном редакторе. К сожалению, инструменты, в отличие от концепций, быстро устаревают. Отличная иллюстрация этой важной для программистов мысли.
8. Отличное объяснение объявления процедуры через назначение имени процедуре, заданной через lambda.
9. Понятие синтаксический сахар вводится так рано, еще до написания хотя бы одной более-менее серьезной программы.
10. Отличное ударение на том, что в лиспе нет разницы между встроенными и пользовательскими процедурами.
11. Очень понравилось, как Харольд использует то доску, то экран со слайдами для демонстрации фрагментов кода. Совместное использование, думаю, эффективнее использования только одного из этих способов демонстрации.
12. Красивое дерево вызовов процедур для sqrt. Очень удобный способ для иллюстрации.
13. В лекции есть несущественная ошибка на слайде, демонстрируемом в 1:05:30. (average 1.5 (/ 2 1.5)) явно не равно 1.3333.
14. Блочная структура и фактически инкапсуляция введена очень просто и естественно. Мастерски. Просто аплодирую мысленно.
15. Красивая и полезная для понимания таблица примитивов, средств комбинирования и средств абстрагирования для данных и процедур.

Лекция очень понравилась. Она дает дополнительное по сравнению с книгой понимание.

Я предлагаю реализацию encode-symbol, приведенную ниже. Она заключается в том, что для символа мы начиная от корня просматриваем вершины дерева кодирования и ищем символ в левом и правом поддеревьях каждой вершины. Если символ найден в левом поддереве, мы дописываем в его код 0, если в правом - 1. Остальная часть кода возвращается вызовом той же процедуры encode-symbol для поддерева, в котором найден символ.

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

Если символ не найден в обоих поддеревьях, это ошибочная ситуация, о чем мы и сообщаем.

Определение процедуры ниже:

(define (encode-symbol symbol tree)
  (if (leaf? tree)
      null
      (cond ((element-of-set? symbol (symbols (left-branch tree)))
             (cons 0 (encode-symbol symbol (left-branch tree))))
            ((element-of-set? symbol (symbols (right-branch tree)))
             (cons 1 (encode-symbol symbol (right-branch tree))))
            (else (error "символ не найден в дереве -- ENCODE-SYMBOL" symbol)))))

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))

Процедура element-of-set? - это процедура проверки принадлежности элемента множеству, представленному неупорядоченным списком, данная в разделе 2.3.3.

Проверка также отрабатывает:

> (encode '(A D A B B C A) sample-tree)
(0 1 1 0 0 1 0 1 0 1 1 1 0)

Дерево кодирования из примера изображено на рисунке ниже:

При декодировании последовательности

0 1 1 0 0 1 0 1 0 1 1 1 0

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

Сначала, пройдем по левой ветке (0) и попадем в лист А:

0 1 1 0 0 1 0 1 0 1 1 1 0  

A

Теперь, двигаясь направо (1), опять направо (1) и налево (0), получим D:

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D

Дальше действуем аналогично (шаги показаны ниже, результат на каждом шаге выделен жирным шрифтом):

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B B

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B B C

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B B C A

И действительно:

> (decode sample-message sample-tree)  

(A D A B B C A)

Вчера этому ресурсу незаметно (я чуть было не пропустил такое знаменательное событие) стукнуло полгода. Первая заметка датирована 12 августа 2007 года.

На текущий момент статистика следующая:

• Написано 137 заметок (включая эту). К заметкам создано 57 комментариев.
• Решено 112 упражнений (это меньше упражнения в день в среднем, но в последний месяц я сильно улучшил статистику и буду стараться поддерживать высокий темп).
• Я на 163-ей странице книги.
• Посещаемость сайта пока невысока, обычно 15-20 уникальных посетителей в день, но это и не массовый ресурс.
• RSS-подписчиков пока целых 14 человек, причем один из них я сам

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

Просто возьмем процедуру element-of-set? для множеств, представленных бинарными деревьями, и модернизируем ее для работы с записями с числовым ключом. Также учтем, что lookup не только проверяет присутствие записи с заданным ключом, но и возвращает саму эту запись в случае успешного поиска.

Получим следующую процедуру:

(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) false)
        ((= given-key (key (entry set-of-records)))
         (entry set-of-records))
        ((< given-key (key (entry set-of-records)))
         (lookup given-key (left-branch set-of-records)))
        ((> given-key (key (entry set-of-records)))
         (lookup given-key (right-branch set-of-records)))))

Последнее условие в cond можно заменить на else.

Процедуры tree->list (я не буду использовать индексы 1 и 2) и list->tree дают нам возможность свободно преобразовывать множества, представленные упорядоченными списками и (сбалансированными) бинарными деревьями, из одного представления в другое за линейное (Θ(n)) число операций.

Это позволяет нам реализовать операции над множествами, представленными бинарными деревьями, через уже реализованные операции над множествами, представленными упорядоченными списками. Для этого просто переведем исходные множества в списочное представление, воспользуемся старыми операциями и переведем результат в “деревянное” представление.

Вот как можно записать реализации операций объединения и пересечения множеств, представленных бинарными деревьями, воспользовавшись этой идеей:

(define (union-set-tree set1 set2)
  (list->tree (union-set (tree->list set1)         
                         (tree->list set2))))

(define (intersection-set-tree set1 set2)
  (list->tree (intersection-set (tree->list set1)         
                                (tree->list set2))))

Я дал процедурам новые имена, чтобы не было путаницы со старыми процедурами, определенными для списочного представления. Поскольку все преобразования из одной форму в другую и обратно, а также старые операции над списочными представлениями имели порядок роста Θ(n), новые операции также имеют порядок роста Θ(n).

Алгоритм работы процедуры partial-tree может быть очень кратко описан следующим образом.

Мы выбираем в списке центральный элемент и разбиваем список на часть до него не включительно (левая часть), сам элемент и часть после него опять не включительно (правая часть). После этого мы строим дерево, корнем которого является выбранный центральный элемент, левое поддерево строится аналогичным образом по левой части списка, а правое - аналогично по правой части списка.

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

При построении дерева из списка (1 3 5 7 9 11) сначала центральным элементом выбирается 5. Левым подсписком становится (1 3), правым - (7 9 11). В (1 3) центральный элемент - 1, левый подсписок пуст, правый - 3. В (7 9 11) центральный элемент - 9, левый подсписок - 7, правый - 11. В результате строится дерево, изображенное на рисунке ниже:

Хочу отметить, что по построению дерево получается сбалансированным (так как поддеревья строятся из примерно равных половин списка).

Порядок роста - Θ(n), поскольку каждый элемент списка обрабатывается ровно по одному разу (назовем обработкой выбор элемента в качестве центрального и запись в узел дерева), а сама обработка элемента требует константного числа операций.

Процедуры tree->list-1 и tree->list-2 создают отсортированный список элементов в дереве (фактически, они производят обход дерева в глубину слева направо и собирают значения entry каждого узла дерева в список). Таким образом они делают одно и то же. Разница между ними в том, что tree->list-1 записана в форме, порождающей рекурсивный процесс, а tree->list-2 порождает итеративный процесс.

Поскольку все деревья на рисунке 2.16 содержат представление одного и того же множества, а стало быть содержат одни и те же элементы, обе процедура для каждого из этих деревьев будут выдавать список элементов множества в порядке возрастания: (1 3 5 7 9 11).

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

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

Первый же вариант на каждом шаге рекурсии (для каждого узла дерева) вызывает процедуру append, которая на самом деле не выполняется за константное время, а требует числа шагов порядка количества элементов в поддереве. Будем предполагать, что дерево сбалансировано, то есть в поддеревьях каждого узла примерно поровну элементов. Пусть некоторое дерево содержит n элементов. Тогда поддеревья его корневого элемента содержат по n/2 элементов. Процедура tree->list-1 на корневом элементе потребует n/2 шагов для append и запустится на каждом из поддеревьев. На каждом из них (их два) аналогичным образом потребуется по n/4 шагов для append, то есть суммарно опять n/2. И так далее. То есть, спускаясь на один уровень по дереву от корня к листовым элементам, мы выполняем для всех вершин на этом уровне в сумме около n/2 шагов. Уровней в сбалансированном бинароном дереве, с которым мы имеем дело, примерно двоичный логарифм от числа элементов. Таким образом нам потребуется примерно n/2 * log₂n, следовательно порядок роста - Θ(n log n).

Как вывод, есть смысл пользоваться вторым вариантом реализации, поскольку он порождает итеративный процесс и имеет меньший порядок роста.

Идея реализации union-set за линейный проход абсолютно аналогична идее, положенной в основу intersection-set из книги. Мы движемся параллельно по двум спискам и сравниваем их текущие первые элементы. Если они равны, мы решаем задачу для хвостов списков и приписываем любой из двух равных головных элементов в начало. Если же один из элементов меньше другого, то его гарантированно нет во втором списке, а значит мы решаем задачу для хвоста его списка и всего второго списка, а затем приписываем этот минимальный элемент в начало результата. Идею иллюстрирует следующее определение процедуры:

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else
         (let ((x1 (car set1)) (rest1 (cdr set1))
               (x2 (car set2)) (rest2 (cdr set2)))
           (cond ((= x1 x2) (cons x1 (union-set rest1 rest2)))
                 ((< x1 x2) (cons x1 (union-set rest1 set2)))
                 (else (cons x2 (union-set set1 rest2))))))))

Под головным элементом списка s я подразумеваю (car s), а хвостом обзываю (cdr s).