非常に長いリストをフィルタリングすると、最大の再帰エラーが発生する可能性があります (仕様では最大 1000 万と言われています)。
(define (inversion L)
(let loop ((accumulator 0) (L L))
(if (null? L)
accumulator
(loop
(+ accumulator
(fold
(lambda (init next)
(if (> (car l) next)
(+ init 1)
init))
0
(cdr L)))
(cdr L)))))
第二に、これは読みやすくなりますが、そのフォールドを独自の関数に引き出します
(define (inversions-from-car L)
(fold
(lambda (init next)
(if (> (car l) next)
(+ init 1)
init))
0
(cdr L)))
(define (inversion L)
(let loop ((accumulator 0) (L L))
(if (null? L)
accumulator
(loop
(+ accumulator
(inversions-from-car L)
(cdr L)))))
書かれているように、n^2 の複雑さがあるため、これはデータ構造で遊ぶのに適した問題のように見えます。
n(log n) まで下げることができると思います
左側のノード数とペアになった値のリストにソートされたツリーを作成するとします。このセットの
'(2 3 8 6 1) -> '(1 2 3 6 8) ->
(*tree (*entry 3 2 2)
(*tree (*entry 2 1 1)
(*tree (*entry 1 0 1)
()
())
())
(*tree (*entry 8 1 1)
(*tree (*entry 6 0 1)
()
())
()))
*tree と *entry は type-tage です *tree には entry、left と right が必要です *entry には value、#left、number が必要です)
元のリストでアキュムレータがゼロの最初のものを見つけることから始めます
'(2 3 8 6 1)
Enrty の値が FIRST に一致する場合、アキュムレータに #left を追加します
値がエントリである場合は、アキュムレータを使用してツリーの左の枝で FIRST 再帰を実行します。
エントリの値が FIRST より小さい場合、アキュムレータに #left を追加して右の分岐を再帰します。
null ツリーの場合はエラーをスローします
次に、ツリーを更新する必要があります。
エントリの値が FIRST に等しい場合、エントリを変更して数値を 1 減らします
エントリの値が FIRST より大きい場合、エントリを変更して #left を 1 減らし、左の分岐で再帰します。
エントリの値が first より小さい場合、右の分岐で再帰します
null ツリーの場合はエラーをスローします
これらのルールを単一のトラバーサルに組み合わせることができます
さらに、#left が 0 で number が 0 の場合、右の分岐が null の場合はこのツリーを空のツリーに変更し、それ以外の場合は右の分岐を変更するというルールを追加します。
これはラフです（アイデアのテストされていないバージョン）
(define (rev-sorted-list->count-list L) ;;sort should be resverse of
;; final desired order
(let loop ((value (car L)) (count 1) (L (cdr L)) (acc '()))
(cond ((null? L) '())
((= value (car l))
(loop value (+ 1 count) (cdr L) acc))
(else
(loop (car l) 1 (cdr L) (cons (cons value count) acc))))))
(define (make-tree count c-L)
(let* ((middle (ceiling (+ 1 count) 2))
(left-count (- middle 1))
(right-count (-count middle))
(left (if (= 0 left-count)
null-tree
(make-tree left-count c-L)))
(entry+right
(let loop ((index 1) (L c-L))
(if (= index middle)
L
(loop (+ 1 index) (cdr L)))))
(entry
(make-entry
(caar entry+right)
left-count
(cdar entry+right))))
(build-tree
entry
left
(if (= 0 right-count)
null-tree
(make-tree right-count (cdr entry+right))))))
;;form left branches from starting points
;;;form right from stopping points
;;never mutating c-L or copies
;;if count = 0 then null tree
(define (build-tree entry left right)
(list '*tree entry left right)
(define (entry tree)
(cadr tree)
(define (left-branch tree)
(caddr tree))
(define (right-branch tree)
(cadddr tree))
(define null-tree (list '*tree '()))
(define (null-tree? tree)
(null? (entry tree)))
(define (make-entry value Nleft count)
(let ((vec (make-vector 3)))
(begin (vector-set! vec 0 value)
(vector-set! vec 1 Nleft)
(vector-set! vec 2 count)
vec)))
;;might meessage passing function here
(define (entry-value entry)
(vector-ref entry 0))
(define (entry-Nleft entry)
(vector-ref entry 1))
(define (entry-Nleft-set! entry int)
(vector-set! entry 1 int))
(define (entry-count entry)
(vector-ref entry 2))
(define (entry-count-set! entry int)
(vector-set! entry 2 int))
(define (inversions! Test-List Search-Tree)
(let loop ((acc 0) (L Test-list) (T Search-tree))
(cond ((null? L) acc)
((null-tree? T) (error "null tree "
"in inner loop of inversion!"))
((= (car L) (entry-value (entry T)))
(entry-count-set! (entry T)
(- (entry-count (entry T)) 1))
(if (and (= 0 (entry-count (entry T)))
(= 0 (entry-Nleft (entry T))))
(set-cdr! T (right-branch T))
'skip)
(loop (+ acc (entry-Nleft (entry T)))
(cdr L)
Search-tree))
((< (car L) (entry-value (entry T)))
(entry-Nleft-set! (entry T)
(- (entry-Nleft (entry T)) 1))
(loop acc L (left-branch T)))
((> (car L) (entry-value (entry T)))
(loop (+ acc (entry-Nleft (entry T)))
L
(right-branch T))))))