以高效率製作清單

我想用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)]))

但是，這種方法可以認爲是低的。我不知道如何提高列表的效率。有人可以幫我嗎？

來源

2013-01-10 Ray Sun

我知道它可能不適用於你的情況，但你可以看看懶惰的球拍，因爲這些類型的列表不需要建立，直到他們真的需要。 –

順便說一句，沒有很好的理由在代碼中使用'set！'。 –

「效率」的另一個定義可能是：用最少的代碼編寫過程。考慮到這一點，問題的最短解決方案是使用現有的程序來解決問題;例如，如果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)

上述利用了build-list過程這是球拍的一部分的：

創建由爲了從0施加PROC到整數(sub1 n) n個元素的列表。如果lst是結果列表，則(list-ref lst i)是由(proc i)產生的值。

另一個選擇，也爲球拍，是使用iterations and comprehensions：

(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-10 21:19:15

關鍵原則是避免Schlemiel the Painter's algorithm，你不這樣做：當列表變長時，使用append反覆佔用越來越多。前置元素是O（1），而追加是O（列表的長度）;所以使最裏面的make-list-helper返回單個列表(max)，並使用cons預先遞歸遞歸元素。（我更喜歡迭代解決方案，但我是一個普通的lisper，所以我最好避免堅持任何的方案）。

不包含任何代碼以避免損害您的學習樂趣。

來源

2013-01-10 17:40:01

謝謝！我會嘗試這種方法！ :-) –

(define (make-list max) 
    (let f ((i max)(a '())) 
    (if (zero? i) 
     a 
     (f (- i 1) (cons i a)))))

這似乎是一個迭代的簡單練習。

上述過程非常簡單，您可以在Scheme中的任何位置使用它。

確保您瞭解整個代碼段的工作原理。

來源

2013-01-10 17:46:13 leppie

以高效率製作清單

回答

相關問題