在Scheme中使用append vs cons和reverse是否更快/更傳統？

當在Scheme中遞歸地構建列表時，我會看到兩種類型的關於Internet的例子。每次迭代中新值附加append。另一個在每次迭代前加上一個新值，cons然後在列表完成後reverse被調用一次。在Scheme中使用append vs cons和reverse是否更快/更傳統？

我的直覺是後者更快，但是如果Scheme解釋器緩存了列表指針的末尾或者正在進行其他優化，那麼前者將同樣快速且更具可讀性。如果口譯員正在進行這種優化，是否保證在所有口譯員中都可以使用？

來源

2015-10-23 John K

「最快，更可讀」。除了不熟悉新優化的有經驗的編程人員會不停地說「這不應該這樣做」。並追加*副本*的第一個列表，所以只保留一個指向另一個列表的末尾不是一個選項。另外，你總是可以利用並保存結果。不過，您不能將指針保存到空列表的最後一個缺點。 –

看到[this]（https://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons），[this]（http://stackoverflow.com/search?q=user%3A849891+modulo+cons），[this ]（http://stackoverflow.com/search?q=user%3A849891+head+sentinel）和[this]（http://stackoverflow.com/questions/26970021/understanding-loop-macro-expansion）。 –

始終優先使用cons。使用append效率非常低，因爲它總是遍歷列表到最後只是在那裏添加一個新元素，而cons在開始處添加元素。不存在指向列表末尾的指針，所以您建議的優化根本不會執行。

在構建大名單逐個元素這是相當重要的，因爲cons是O(1)操作，而append是O(n)爲每一個新加入的元素，降級爲O(n^2)複雜！（一個很好的比喻，請參閱：Schlemiel the Painter's algorithm）。最後，簡單地在開始時添加元素便宜很多，並且如果需要的話，在最後列出reverse，實現O(n)的複雜性。

來源

2015-10-23 14:57:07

在Scheme中使用append vs cons和reverse是否更快/更傳統？

回答

相關問題