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

そんなに難しい問題ではない。
重複を考えないぶん、簡単だ。

実装

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

(use ggc.debug.trace)
(use math.mt-random)


(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 (adjoin-set x set)
;  (if (element-of-set? x set)
;    set
;    (cons x set)))


;;重複を認める
(define (adjoin-set x set)
  (cons x set))

(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) nil)
        ((element-of-set? (car set1) set2)
         (cons (car set1)
               (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))


;;重複を認めない。
;(define (union-set set1 set2)
;  (cond ((and (null? set1) (null? set2)) nil)
;        ((null? set1) set2)
;        ((null? set2) set1)
;        ((element-of-set? (car set1) set2)
;         (union-set (cdr set1) set2))
;        (else (cons (car set1)
;                    (union-set (cdr set1) set2)))))

;;重複を認める
(define (union-set set1 set2)
  (append set1 set2))



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

;; main
(define (main args)


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

  (display "(element-of-set? 5 set1): ")
  (display (element-of-set? 5 set1))
  (newline)

  (display "(element-of-set? 6 set1): ")
  (display (element-of-set? 6 set1))
  (newline)

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

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

  (display "(intersection-set set1 set2): ")
  (display (intersection-set set1 set2))
  (newline)

  (display "(union-set set1 set2): ")
  (display (union-set set1 set2))
  (newline)


  0)

実行

set1: (1 2 3 4 5)
set2: (2 3 4 5 6 7)
(element-of-set? 5 set1): #t
(element-of-set? 6 set1): #f
(adjoin-set 5 set1): (5 1 2 3 4 5)
(adjoin-set 6 set1): (6 1 2 3 4 5)
(intersection-set set1 set2): (2 3 4 5)
(union-set set1 set2): (1 2 3 4 5 2 3 4 5 6 7)

データの存在を確認しなくていいので、書き込みが速い。
データ量がおおきくなるので、検索に時間場合がある。
応用としてはログとかの書き込みに良さそう。

余談だけど、
この問題を会社の勉強会でやっている時に、重複ありの応用が何に使えるかって部分で
SQL王子になろうとしている僕としては、
MVCC(MultiVersion Concurrency Control)のことを言おうと思ったんだが、
「トランザクション、トランザクションの実現の技術が、ぐむぐむ」
みたいな感じでしか話せなくて、
そもそも「MVCC」の名前もど忘れしていたし、ちゃんと説明する事が出来なかった。
完全に残念な人状態だった。後悔。

僕のMVCCの理解が乏しかったら単なる間違えなんだけど、

重複させっぱなしでDBの中にデータは入れちゃう、
っていうのがMVCCの方法論だと思う。
そんで実際に見せるデータはうまいこと見せる。
だからリードロックとライトロックの獲得が競合しない。
みたいな事をいいたかったんだが、、、、、

んでま、そうすると、見た目のデータより、
実際のデータはどんどん膨らむから、バキュームが必要みたいな。

詳しくは　PostgreSQL完全機能リファレンス―実行例を通して「理解」を深める。の前半の方に載ってる。