0

我想用Scheme语言来创建一个高效的特殊列表。例如：

函数名称：make-list
参数：max
(make-list max) -> (1 2 3 4 5 6 7 ... max)

我可以使用递归方法完成这项任务。 

#lang racket

(define (make-list max)
(define lst '())
(define count 1) 
(make-list-helper lst max count))

(define (make-list-helper lst max count) 
 (cond  
 [(> count max) lst]
 [else 
  (set! lst (append lst (list count))) 
  (make-list-helper lst max (add1 count)]))

然而，这种方法可以被认为是低的。我不知道如何提高其制作清单的效率。有人可以帮帮我吗？

4

3 回答 3

2

关键原则是避免使用 Schlemiel the Painter 算法，而您却没有这样做：append随着列表变长，重复使用会花费越来越多的时间。前置元素是O（1），而附加是O（列表长度）；所以让最里面的make-list-helper返回一个单数列表(max)，并用于cons在递归时添加元素。

（我更喜欢迭代解决方案，但我是一个普通的 lisper，所以我最好避免坚持任何方案）。

不包含代码，以免破坏您的学习乐趣。

于 2013-01-10T17:40:01.403 回答
2 
(define (make-list max)
  (let f ((i max)(a '()))
    (if (zero? i)
        a
        (f (- i 1) (cons i a)))))

这似乎是一个简单的迭代练习。

以上内容非常简单，您将在 Scheme 中的任何地方使用它。

确保您了解整个代码段的工作原理。

于 2013-01-10T17:46:13.447 回答
1

“效率”的另一个定义可能是：用最少的代码编写过程。考虑到这一点，问题的最短解决方案是使用现有程序来解决问题；例如，如果max = 10：

(define (make-list max-val)
  (build-list max-val add1))

(make-list 10)
=> '(1 2 3 4 5 6 7 8 9 10)

上面使用了作为 Racket 一部分的构建列表过程：

通过按顺序将 proc 应用于整数 from 0to创建一个包含 n 个元素的列表。(sub1 n)如果 lst 是结果列表，则(list-ref lst i)是 产生的值(proc i)。

另一个选择，同样适用于 Racket，是使用迭代和推导：

(define (make-list max-val)
  (for/list ([i (in-range 1 (add1 max-val))]) i))

(make-list 10)
=> '(1 2 3 4 5 6 7 8 9 10)

无论哪种方式，鉴于过程是语言核心库的一部分，您可以确定它们的性能非常好，除非分析器表明它们是瓶颈，否则无需担心。

于 2013-01-10T21:19:15.267 回答