filter - 使用 Racket 构建过滤器内置函数

Question

我正在尝试使用 Racket 构建过滤器(内置函数)作为练习。

我创建了以下代码:

(define (filter lista-1 check-function)
 (define (fil-iter lista-1 check-function lista-2)
  (cond ((null? lista-1) lista-2)
        ((check-function (car lista-1)) (fil-iter (cdr lista-1) check-function (append lista-2 (list (car lista-1)))))
        (else (fil-iter (cdr lista-1) check-function lista-2))))
   (trace fil-iter)
   (fil-iter lista-1 check-function '()))

我用“奇数？”、“偶数？”做了一些测试。和“数字？”作为“检查功能”。

所有输出都是正确的。但我可能没有看到什么……我的直觉告诉我这里有问题。

Answer 1

你的函数是正确的，只是它的复杂度为 n² 而它可能有 n 的复杂度。

原因是您使用 append 而不是 cons 来构建结果，并且 append 的成本与列表，而 cons 具有恒定成本。所以，如果你想要一个具有线性复杂度的函数，你应该这样写:

(define (filter lista-1 check-function)
 (define (fil-iter lista-1 check-function lista-2)
  (cond ((null? lista-1) (reverse lista-2))
        ((check-function (car lista-1))
         (fil-iter (cdr lista-1) check-function (cons (car lista-1) lista-2)))
        (else (fil-iter (cdr lista-1) check-function lista-2))))
   (fil-iter lista-1 check-function '()))

请注意，最后必须反转结果，但这不会改变函数的复杂性，因为 reverse 的复杂度与列表的大小成线性关系，并且只执行一次，在函数结束。

您还可以简化函数，注意参数 check-function 不会在每次调用助手 fil-iter 时被修改，因此可以在其中省略它:

(define (filter lista-1 check-function)
 (define (fil-iter lista-1 lista-2)
  (cond ((null? lista-1) (reverse lista-2))
        ((check-function (car lista-1))
         (fil-iter (cdr lista-1) (cons (car lista-1) lista-2)))
        (else (fil-iter (cdr lista-1) lista-2))))
   (fil-iter lista-1 '()))