10

私はScheme（Racket経由）と（それほどではありませんが）関数型プログラミングに不慣れで、変数と再帰による累積の長所と短所についてアドバイスを使用できます。この例では、移動平均を計算しようとしています。したがって、 list'(1 2 3 4 5)の場合、3 期間の移動平均は になります'(1 2 2 3 4)。アイデアは、期間の前の数値はまだ計算の一部ではなく、セットの期間の長さに達すると、選択した期間に従ってリストのサブセットの平均化を開始するというものです。

したがって、私の最初の試みは次のようになりました。

(define (avg lst)
  (cond
   [(null? lst) '()]
   [(/ (apply + lst) (length lst))]))

(define (make-averager period)
  (let ([prev '()])
    (lambda (i)
      (set! prev (cons i prev))
      (cond
       [(< (length prev) period) i]
       [else (avg (take prev period))]))))

(map (make-averager 3) '(1 2 3 4 5))

> '(1 2 2 3 4)

これは機能します。そして、私は地図の使い方が好きです。構成可能で、リファクタリングが可能です。将来、次のようないとこがいることがわかります。

(map (make-bollinger 5) '(1 2 3 4 5))
(map (make-std-deviation 2) '(1 2 3 4 5))

等

しかし、Scheme の精神ではありません (そうですか?)。ということで、以下のように書き直しました。

(define (moving-average l period)
  (let loop ([l l] [acc '()])
    (if (null? l)
        l
        (let* ([acc (cons (car l) acc)]
               [next
                 (cond
                  [(< (length acc) period) (car acc)]
                  [else (avg (take acc period))])])
          (cons next (loop (cdr l) acc))))))

 (moving-average '(1 2 3 4 5) 3)
 > '(1 2 2 3 4)

さて、このバージョンは一見すると理解するのがより困難です。だから私はいくつかの質問があります：

  1. ラケットの組み込み反復構造のいくつかを使用して、再帰バージョンを表現するよりエレガントな方法はありfor/foldますか? 書かれているように末尾再帰ですか？

  2. アキュムレータ変数を使用せずに最初のバージョンを作成する方法はありますか?

  3. このタイプの問題は、特にSchemeでベストプラクティスが認められているより大きなパターンの一部ですか?

4

3 に答える 3

7

あなたがリストの最初のリストよりも前に開始しているのに、リストの最後で急激に停止しているのは、私には少し奇妙です。つまり、最初の要素を単独で取得し、最初の 2 つの要素を単独で取得しますが、最後の要素または最後の 2 つの要素については同じことを行いません。

これは、問題の解決策とは多少直交しています。ここでアキュムレータがあなたの人生を楽にしてくれるとは思いません。アキュムレータなしで解決策を書きます:

#ラングラケット

(require rackunit)

;; given a list of numbers and a period, 
;; return a list of the averages of all 
;; consecutive sequences of 'period' 
;; numbers taken from the list.
(define ((moving-average period) l)
  (cond [(< (length l) period) empty]
        [else (cons (mean (take l period)) 
                    ((moving-average period) (rest l)))]))

;; compute the mean of a list of numbers
(define (mean l)
  (/ (apply + l) (length l)))

(check-equal? (mean '(4 4 1)) 3)
(check-equal? ((moving-average 3) '(1 3 2 7 6)) '(2 4 5))
于 2012-02-01T05:35:15.753 に答える
0

原則として、再帰および/または反復の方法を反復ステップの内容から分離する必要があります。あなたはあなたの質問に言及foldしていますが、これは正しいステップのポイントです.リストトラバーサルメカニズムを処理し、ウィンドウに値を指定して指定した関数を呼び出す何らかの形式の高次関数が必要です。

これを 3 分で調理しました。おそらく多くの点で間違っていますが、アイデアが得られるはずです。

;;;
;;; Traverse a list from left to right and call fn with the "windows"
;;; of the list.  fn will be called like this:
;;;
;;;     (fn prev cur next accum)
;;;
;;; where cur is the "current" element, prev and next are the
;;; predecessor and successor of cur, and accum either init or the
;;; accumulated result from the preceeding call to fn (like
;;; fold-left).
;;;
;;; The left-edge and right-edge arguments specify the values to use
;;; as the predecessor of the first element of the list and the
;;; successor of the last.
;;;
;;; If the list is empty, returns init.
;;;
(define (windowed-traversal fn left-end right-end init list)
  (if (null? list)
      init
      (windowed-traversal fn
                          (car list)
                          right-end
                          (fn left-end
                              (car list)
                              (if (null? (cdr list))
                                  right-end
                                  (second list))
                              init)
                          (cdr list))))

(define (moving-average list)
  (reverse!
   (windowed-traversal (lambda (prev cur next list-accum)
                         (cons (avg (filter true? (list prev cur next)))
                               list-accum))
                       #f
                       #f
                       '()
                       list)))
于 2012-02-01T23:21:37.310 に答える
0

または、リストを n 要素のウィンドウに変換する関数を定義してから、ウィンドウに平均をマップすることもできます。

(define (partition lst default size)
  (define (iter lst len result)
    (if (< len 3)
      (reverse result)
      (iter (rest lst)
            (- len 1)
            (cons (take lst 3) result))))
  (iter (cons default (cons default lst))
        (+ (length lst) 2)
        empty))

(define (avg lst)
  (cond
   [(null? lst) 0]
   [(/ (apply + lst) (length lst))]))

(map avg (partition (list 1 2 3 4 5) 0 3))

また、このpartition関数は末尾再帰であるため、スタック スペースを消費しないことにも注意してください。これがresultand のreverse呼び出しのポイントです。length繰り返し呼び出し(O(N^2) ランタイムにつながる) や関数のハッキングを避けるために、リストの長さを明示的に追跡しat-least-size-3ます。末尾再帰を気にしない場合は、次のバリアントがpartition機能するはずです。

(define (partition lst default size)
  (define (iter lst len)
    (if (< len 3)
      empty
      (cons (take lst 3)
            (iter (rest lst)
                  (- len 1)))))
  (iter (cons default (cons default lst))
        (+ (length lst) 2)))

最後のコメント - 空のリストのデフォルト値として '() を使用すると、明示的にチェックしないと危険です。数値が 0 より大きい場合は、0 (または -1) がデフォルト値として適切に機能する可能性があります。値を使用しているコードを強制終了することはありませんが、簡単に確認でき、正当な平均値として表示することはできません。

于 2012-02-02T04:18:47.763 に答える