Common Lisp中最大的子列表 [英] Largest sublist in Common Lisp

问题描述

我正在尝试使用Common Lisp从列表中获取最大的子列表.

I'm trying to get the largest sublist from a list using Common Lisp.

(defun maxlist (list)
(setq maxlen (loop for x in list maximize (list-length x)))
(loop for x in list (when (equalp maxlen (list-length x)) (return-from maxlist x)))
)

这个想法是遍历列表两次:第一个循环获取最大子列表的大小，第二个循环获取所需的列表.但是由于某些原因，我在return-from行中总是收到错误消息.我想念什么?

The idea is to iterate through the list twice: the first loop gets the size of the largest sublist and the second one retrieves the required list. But for some reason I keep getting an error in the return-from line. What am I missing?

推荐答案

loop

的主要问题

这里有一些问题.首先，您可以编写如下的循环. Common Lisp中有return-from和while形式，但是 loop 定义了自己的小语言，它也可以识别while和return，因此您可以使用以下语言:

Main problem with loop

There are a few problems here. First, you can write the loop as the following. There are return-from and while forms in Common Lisp, but loop defines its own little language that also recognizes while and return, so you can just use those:

(loop for x in list
      when (equalp maxlen (list-length x))
      return x)

实际上，可以使用find更简洁地编写这样的循环.只是

A loop like this can actually be written more concisely with find though. It's just

(find maxlen list :key list-length :test 'equalp)

但是，请注意，list-length应该始终返回数字或nil，因此equalp是过大的.您可以只使用eql，这是find的默认设置，因此您甚至可以编写

Note, however, that list-length should always return a number or nil, so equalp is overkill. You can just use eql, and that's the default for find, so you can even write

(find maxlen list :key list-length)

list-length和maximize

list-length与length非常相似，不同之处在于，如果列表具有圆形结构，则返回nil，而用不正确的列表调用length是错误的.但是，如果您使用的是(loop ... maximize ...)，则不能有nil值，因此list-length不能处理length的唯一情况是仍然会出现错误.例如

list-length and maximize

list-length is a lot like length, except that if a list has circular structure, it returns nil, whereas it's an error to call length with an improper list. But if you're using (loop ... maximize ...), you can't have nil values, so the only case that list-length handles that length wouldn't is one that will still give you an error. E.g.,

CL-USER> (loop for x in '(4 3 nil) maximize x)
; Evaluation aborted on #<TYPE-ERROR expected-type: REAL datum: NIL>.

(实际上，length也可以与其他类型的序列一起使用，因此，如果您传递矢量，则list-length会出错，但length不会.)因此，如果您知道它们都是正确的列表，您可以

(Actually, length works with other types of sequences too, so list-length would error if you passed a vector, but length wouldn't.) So, if you know that they're all proper lists, you can just

(loop for x in list
      maximizing (length x))

如果它们不一定都是正确的列表(因此您确实需要list-length)，那么您需要像这样警惕:

If they're not all necessarily proper lists (so that you do need list-length), then you need to guard like:

(loop for x in list
      for len = (list-length x)
      unless (null len) maximize len)

更有效的argmax

但是，现在您要遍历该列表两次，并且要计算每个子列表的长度两次.一次是计算最大长度，另一个是当您找到一个具有最大值的值.如果您一次性完成此操作，则可以节省时间. argmax没有明显的优雅解决方案，但以下是基于reduce，loop和do*的实现.

A more efficient argmax

However, right now you're making two passes over the list, and you're computing the length of each sublist twice. Once is when you compute the maximum length, and the other is when you go to find one with the maximum value. If you do this in one pass, you'll save time. argmax doesn't have an obvious elegant solution, but here are implementations based on reduce, loop, and do*.

(defun argmax (fn list &key (predicate '>) (key 'identity))
  (destructuring-bind (first &rest rest) list
    (car (reduce (lambda (maxxv x)
                   (destructuring-bind (maxx . maxv) maxxv
                     (declare (ignore maxx))
                     (let ((v (funcall fn (funcall key x))))
                       (if (funcall predicate v maxv)
                           (cons x v)
                           maxxv))))
                 rest
                 :initial-value (cons first (funcall fn (funcall key first)))))))

(defun argmax (function list &key (predicate '>) (key 'identity))
  (loop
     for x in list
     for v = (funcall function (funcall key x))
     for maxx = x then maxx
     for maxv = v then maxv
     when (funcall predicate v maxv)
     do (setq maxx x
              maxv v)
     finally (return maxx)))

(defun argmax (function list &key (predicate '>) (key 'identity))
  (do* ((x (pop list)
           (pop list))
        (v (funcall function (funcall key x))
           (funcall function (funcall key x)))
        (maxx x)
        (maxv v))
       ((endp list) maxx)
    (when (funcall predicate v maxv)
      (setq maxx x
            maxv v))))

它们产生相同的结果:

CL-USER> (argmax 'length '((1 2 3) (4 5) (6 7 8 9)))
(6 7 8 9)
CL-USER> (argmax 'length '((1 2 3) (6 7 8 9) (4 5)))
(6 7 8 9)
CL-USER> (argmax 'length '((6 7 8 9) (1 2 3) (4 5)))
(6 7 8 9)

这篇关于Common Lisp中最大的子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！