Изменение структуры может ускорить вычисления

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

 

_(setq начало ’(a b))

(А В)

_(setq конец ’(c d))

(C D)

_(setq результат (append начало конец))

(A B C D)

Может показаться, что приведенный выше вызов APPEND, как бы изменяет указатели так, как это показано штриховыми стрелками на рис.9.

 

 

РЕЗУЛЬТАТ

НАЧАЛО КОНЕЦ

 

 

 

A B C D

 

 

Рис.9

 

 

Однако это не верно, так как значение списка НАЧАЛО не может измениться, поскольку APPEND не является структуро-разрушающей функцией. Вычисляется и присваивается лишь новое значение переменной РЕЗУЛЬТАТ. Мы получим структуры, изображенные на рис.10.

 

 

НАЧАЛО КОНЕЦ

 

А B C D

 

 

РЕЗУЛЬТАТ

 

Рис.10

 

 

Из рисунка 10 видно, что APPEND создает копию списка, являющегося первым аргументом. Если этот список очень длинный, то долгими будут и вычисления. Создание списочных ячеек с помощью функции CONS требует времени и в будущем добавляет работы мусорщику. Если, например, список НАЧАЛО содержит 1000 элементов, а КОНЕЦ – один элемент, то во время вычисления будет создано 1000 новых ячеек, хотя вопрос состоит лишь в добавлении одного элемента к списку. Если бы последовательность аргументов была другой, то создалась бы одна ячейка, и списки были бы объединены приблизительно в 1000 раз быстрее.

Если для нас не существенно, что значение переменной НАЧАЛО изменится, то мы можем вместо функции APPEND использовать более быструю функцию NCONC (concatenate). Функция NCONC делает то же самое, что и APPEND, с той лишь разницей, что она просто объединяет списки, изменяя указатель в поле CDR последней ячейки списка, являющегося первым аргументом, на начало списка, являющегося вторым аргументом, как это показано на рис.9.

 

_начало

(А В)

_конец

(C D)

_(setq изменится (append конец начало))

(C D A B); это значение изменится

_(setq результат1 (nconc начало конец))

(A B C D); разрушающее объединение,

; смотри рис.9

_начало; побочный эффект

(A B C D); смотри рис.9

_конец

(C D)

_изменится

(C D A B C D); наблюдается побочный

; эффект

Использовав функцию NCONC, мы избежали копирования списка НАЧАЛО, однако в качестве побочного эффекта изменилось значение переменной НАЧАЛО. Так же изменятся и все другие структуры (например, значение символа ИЗМЕНИТСЯ), использовавшие ячейки первоначального значения переменной НАЧАЛО.

Псевдофункции, подобные RPLACA, RPLACD и NCONC, изменяющие внутреннюю структуру списков, используются в том случае, если нужно сделать небольшие изменения в большой структуре данных. С помощью структуро-разрушающих функций можно эффективно менять за один раз сразу несколько структур, если у этих структур есть совмещенные в памяти подструктуры.

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

 

 

ЛАБОРАТОРНАЯ РАБОТА №8

 

1. Нарисуйте следующие списки при помощи списочных ячеек и стрелок:

a) (а)

b) (a (b (c) d))

c) (nil (b. c). d)

 

 

2. Почему значением (eq ’(a b) ’(a b)) будет NIL?

 

 

3. Каковы будут значения выражений (RPLACA x x) и (PRLACD x x), если

a) x =’(a b)

b) x =’(a)

и оба аргумента состоят из различных ячеек? Как изменятся значения, если аргументы будут физически идентичны?

 

 

4. Вычислите значения следующих выражений:

a) (rplacd ’(a) ’b)

b) (rplaca ’(a) ’b)

c) (rplacd (cddr ’(a b x)) ’c)

d) (rplacd ’(nil) nil)

e) (rplacd ’(nil) ’(nil))

 

 

5. Что делает следующая псевдофункция:

(defun бесполезная (х)

(cond ((null x) x)

(t (rplacd x (бесполезная (cdr x))))))

 

 

СВОЙСТВА СИМВОЛА