Решение упражнения 2.61 из SICP

12 February, 2008 (21:16) | Решения упражнений

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

Мы пойдем другим путем: объединим проверку нахождения элемента во множестве с добавлением элемента. Воспользуемся упорядоченностью списка. Если элемент x содержится во множестве, то он должен находиться в списке раньше, чем любой элемент, больший его. Таким образом мы просто будем идти по элементам списка, пока не встретим среди них либо x, либо какой-нибудь y больший x. Если мы встретили x, то просто вернем исходное множество без изменений. Если же нам встретился y, а x не встретился до него, то значит x в списке (и множестве, им представленном) отсутствует и должен быть добавлен непосредственно перед y.

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

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((= x (car set)) set)
        ((< x (car set)) (cons x set))
        (else (cons (car set) (adjoin-set x (cdr set))))))

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

Мы делаем число шагов, пропорциональное позиции наименьшего элемента, не меньшего x, в списке. В среднем оно будет равно половине длины списка.

Comments

Comment from anton0xf
Date: August 22, 2009, 3:56 am

есть вот такая попытка итеративного процесса, но выигрыша эта реализация не дает никакого)
есть идеи лучше?

(define (adjoin-set x set)
(define (iter set res)
(cond ((null? set) (cons x res))
((= x (car set)) (append (reverse set) res))
((< x (car set)) (append (reverse (cons x set)) res))
(else (iter (cdr set) (cons (car set) res)))))
(reverse (iter set ‘())))

Comment from Samolisov Pavel
Date: September 4, 2009, 6:06 am

Впринципе, если использовать append, то reverse не нужен. Я затрудняюсь оценить выигрыш, т.к. не знаю как работает append, по моему он один из объединяемых списков обходит полностью, так что выигрыша тоже не будет. Но не будет и проигрыша.

(define (adjoin-set x set)
  (define (iter pre post)
    (cond ((null? post) (append pre (list x)))
          ((= (car post) x) set)
          ((> (car post) x) (append pre (list x) post))
          (else (iter (append pre (list (car post))) (cdr post)))))
  (iter '() set))

Write a comment