-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

为什么不解决括号问题并正确缩进代码。按CRTL+ i。如果标识错误，您可能缺少括号。按下Run进行评估，您将收到正确的错误消息。当你有一些不会产生错误的东西时，更新这个问题。

回答您的问题，您向本地程序添加的参数多于全局。这样你就有一个参数，当你在当前元素中找到搜索元素时，你会增加一个计数。例如。

(define (length lst)
  (define (length-aux lst cnt)
    (if (null? lst)
        cnt
        (length-aux (cdr lst) (add1 cnt))))
  (length-aux lst 0))

或者更好的命名let

(define (length lst)
  (let length-aux ((lst lst) (cnt 0))
    (if (null? lst)
        cnt
        (length-aux (cdr lst) (add1 cnt)))))

编辑

我建议至少有 4 个帮助程序来解决每个问题。（如果您使用球拍自己的remove,count和，则更少argmax）。请注意，可能有很多其他方法可以解决这个问题，但这是我在没有哈希表的情况下解决它的方法。

由于您只对流派感兴趣，因此首先要想象的是，您可以这样做(map movie-genre lst)，以便在主要助手中获得要使用的流派列表。

在您的主要助手中，您可以建立一个具有流派和计数的缺点列表。为此，您使用一个助手count， (count 'c '(a b c d c c a) 0) ==> 3您只需获取第一个流派并将列表计算为第一个累积值，然后处理(remove 'c '(a b c d c c a) '()) ==> (a d b a)列表其余部分的结果。处理完成后，您的累加器中有((a . 4) (b . 6) ...)您需要一个助手(max-genre 'a 4 '((b . 6) (c . 20) (d . 10))) ; ==> c

主要助手看起来像这样：

(define (aux lst acc)
  (if (null? lst) 
      (max-genre (caar acc) (cdar acc) (cdr acc))
      (aux (remove (car lst) lst '())
           (cons (cons (car lst) (count (car lst) lst 0)) acc))))

现在，您可以一次性使用哈希表更简单地完成此操作。在阅读所有元素一次之后，您仍然必须拥有max-genre/ 。argmax

于 2014-06-03T10:06:10.093 回答
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.

很多consing和东西。使用特定于 Racket 的结构的另一种更有效的版本for可能是：

(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 回答