計算機プログラムの構造と解釈 第二版 P90 問題2.61

そんなに難しい問題ではない。
ほとんどの答えが、既にこの問題の前に書いてある。

教科書P90に書いてる説明が、順序の利点の答え

最悪の場合、探している者は集合の最大の要素かもしれず、ステップ数は順序づけられていない表現と同じである。ところが、異なる大きさのものを探す場合は、ある時はリストの先頭に近い場所で探索を止める事が出来、またある時はリストの大部分を調べなければならないと考えられる。平均すると集合の半分のものを調べなければならないと考えられる。平均すると集合の半分のものを調べなければならないと考えられる。従って必要なステップ数の平均は、約n/2である。これはやはりθ(n)の増加だが、前の表現に比べ、ステップ数は平均で2倍の改善になっている。

実装

#!/usr/local/bin/gosh
;; -*- coding: utf-8 -*-

(define nil '())

;;ソートなし
;(define (element-of-set? x set)
;  (cond ((null? set) #f)
;        ((equal? x (car set)) #t)
;        (else (element-of-set? x (cdr set)))))


;;ソートあり
(define (element-of-set? x set)
  (cond ((null? set) #f) 
        ((= x (car set)) #t) 
        ((< x (car set)) #f) 
        (else (element-of-set? x (cdr set)))))


;;ソートなし
;(define (adjoin-set x set)
;  (if (element-of-set? x set)
;    set
;    (cons x set)))


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


(define set1 '(1 2 3 4 5))
(define set2 '(2 3 4 6 7))

;; main
(define (main args)

  (display "set1: ")
  (display set1)
  (newline)
  (display "set2: ")
  (display set2)
  (newline)

  (display "(adjoin-set 5 set1): ")
  (display (adjoin-set 5 set1))
  (newline)

  (display "(adjoin-set 6 set1): ")
  (display (adjoin-set 6 set1))
  (newline)

  (display "(adjoin-set 1 set2): ")
  (display (adjoin-set 1 set1))
  (newline)

  (display "(adjoin-set 5 set2): ")
  (display (adjoin-set 5 set2))
  (newline)

  (display "(adjoin-set 7 set2): ")
  (display (adjoin-set 7 set2))
  (newline)

  0)

実行

set1: (1 2 3 4 5)
set2: (2 3 4 6 7)
(adjoin-set 5 set1): (1 2 3 4 5)
(adjoin-set 6 set1): (1 2 3 4 5 6)
(adjoin-set 1 set2): (1 2 3 4 5)
(adjoin-set 5 set2): (2 3 4 5 6 7)
(adjoin-set 7 set2): (2 3 4 6 7)