-2

構造定義:

(define-struct movie (title genre stars))
;; title is a nonempty string
;; genre is a nonempty string
;; stars us a list of nonempty strings

映画のリストを消費し、最も頻繁に発生するジャンルを生成するスキーム関数を作成しようとしています。

これまでのところ、私は次のものを持っています：

(define (popular-gnere movies)
(local
[(define acc movies genre)
(cond
[(empty? movies) genre]
[(equal? genre (movie-genre (first movies)))
(acc (rest movies genre)))

特定のジャンルが特定の映画のリストに何回登場したかをどのように数えることができるかについて、私は立ち往生しています。この場合の累積再帰が最も効率的であることは理解していますが、アキュムレータを完成させるのに問題があります。

4

2 に答える 2

0

まず、キーと値のデータ型を決定する必要があります。連想リストを使用することもできますが、ハッシュ テーブルの方が効率的です。

短いリストから始めましょう。

(define-struct movie (title genre stars))
(define films
  (list
   (make-movie "Godfater" "Crime" '("Marlon Brando" "Al Pacino"))
   (make-movie "Rambo" "Thriller" '("Sylvester Stallone"))
   (make-movie "Silence of the Lambs" "Crime" '("Jodie Foster" "Anthony Hopkins"))))

空のハッシュテーブルを作成します

(define h (make-hash))

次に、すべてのフィルムを処理し、ハッシュ テーブルを更新します。

> (for-each (lambda (e) (hash-update! h e add1 0)) (map movie-genre films))
> h
'#hash(("Thriller" . 1) ("Crime" . 2))

次に、最大数を見つける必要があります。

> (hash-values h)
'(1 2)
> (define most (foldl (lambda (e r) (if (> e r) e r)) 0 (hash-values h)))
> most
2

したがって、2 が最大数です。次に、カウント 2 ですべてのジャンルのリストを作成します。

> (hash->list h)
'(("Thriller" . 1) ("Crime" . 2))
> (foldl
   (lambda (e r)  (if (= (cdr e) most) (cons (car e) r) r))
   null
   (hash->list h))
'("Crime")

すべてを一緒に入れて：

(define (count-by-genre lst)
  (define h (make-hash))
  (for-each (lambda (e) (hash-update! h e add1 0)) (map movie-genre lst))
  (define most (foldl (lambda (e r) (if (> e r) e r)) 0 (hash-values h)))
  (foldl
   (lambda (e r)  (if (= (cdr e) most) (cons (car e) r) r))
   null
   (hash->list h)))

しかし、これはいくつかの理由で非常に非効率的です:

  1. ハッシュ テーブルを更新した後、それを繰り返し処理し、リストを作成してfoldlから、最高値を見つけるためだけに適用する必要がありますが、ハッシュ テーブルを更新している間はそれをメモしておくこともできました。
  2. 次に、 を使用して完全なリスト ( hash->list) と最終結果リストを作成しfoldlます。

たくさんのコンシングなど。forRacket 固有の構造を使用した、より効率的な代替バージョンは次のようになります。

(define (count-by-genre lst)
  (define h (make-hash))
  (define most
    (for/fold ((highest 0)) ((e (in-list (map movie-genre lst))))
      (define new (add1 (hash-ref h e 0)))
      (hash-set! h e new)
      (max highest new)))
  (for/fold ((res null)) (((k v) (in-hash h)))
    (if (= v most) (cons k res) res)))
于 2014-06-03T19:06:50.197 に答える