Data.Sequence.Seq與[]相比有多快？

對於所有可能的操作，顯然Seq漸近地執行與[]相同或更好。但是由於其結構比列表更復雜，對於小尺寸的系統而言，其不斷的開銷可能會使其變慢。我想知道有多少，特別是：Data.Sequence.Seq與[]相比有多快？

被<|相比:慢多少？
摺疊/穿越Seq與摺疊/穿越[]（不包括摺疊/穿越功能的成本）相比，要慢多少？
\xs x -> xs ++ [x]變得比|>慢什麼尺寸（大約）？
++變得慢於><的尺寸（大約）是多少？
與列表中的模式匹配相比，調用viewl和結果上的模式匹配的成本是多少？
n -element Seq佔用多少內存相比n -lelement list？（不計算由元素，只有結構所佔用的內存。）

我知道這是很難衡量，因爲與Seq我們談論攤銷複雜，但我想知道至少有一些粗略的數據。

來源

2013-02-10 Petr Pudlák

沒有這樣的比較存在。我建議使用標準基準庫自己生成它。 – 2013-02-10 14:35:20

如果有人最終決定在這個基準上進行基準測試，那麼爲了比較而放入一個「Vector」也是很有意義的。會很高興看到結果。收藏這個。 – 2013-02-10 14:38:04

由於在真實代碼中使用GHC，中間列表往往會融合並重寫並消失，這使得它們更像控制結構而不是數據結構本身，這也很困難（或不是特別有用）。 – jberryman 2013-02-10 21:51:27

這應該是一個開始 - http://www.haskell.org/haskellwiki/Performance#Data.Sequence_vs._lists

甲序列使用倍儘可能多的空間的等效列表5/6和4/3之間（假設每個節點一個字的開銷，如在GHC）。如果僅使用deque操作，則空間使用量將接近該範圍的下限，因爲所有內部節點都是三元的。大量使用split和append會導致序列使用與列表大致相同的空間。詳細說明：

長度爲n的列表由n個cons節點組成，每個節點佔用3個字。
長度爲n的序列具有近似n /（k-1）個節點，其中k是內部節點（每個2或3）的平均arity。每個節點都有一個指針，一個大小和開銷，加上每個元素的指針，即n（3 /（k-1）+ 1）個字。

列表是一個非常重要的常量因子，在頭部（cons和head）操作更快，使其成爲類似堆棧和流式訪問模式的更高效選擇。 Data.Sequence對於其他訪問模式（如隊列和隨機訪問）更快。

來源

2013-02-10 14:46:35 manojlds

我還有一個具體的結果添加到上面的答案。我正在解決一個朗之萬方程。我使用List和Data.Sequence。在此解決方案中，列表/序列後面的很多插入操作正在進行。總之，我沒有看到速度有任何提高，實際上性能隨着序列而惡化。此外，與Data.Sequence，我需要增加可用於Haskell RTS的內存。

因爲我絕對不是優化的權威;我在下面發佈了這兩種情況。我很樂意知道這是否可以改進。這兩個代碼都是用-O2標誌編譯的。

Solution with List，需要約13.01秒
Solution with Data.Sequence，需要約15.13秒

來源

2014-10-31 16:44:09 Dilawar

你的序列/列表有多長？ – 2014-11-02 15:20:21

他們倆都有10^6個元素。 – Dilawar 2014-11-04 08:05:42

如果有人在這裏，我測試鏈接的代碼出於好奇，並在我的機器seq稍快。（〜5％）這也是一個不好的例子，因爲在這兩個案例中，比較歸結爲通過在前面添加並倒轉來建立清單。或者通過在最後添加Seq然後將其轉換爲列表而不是直接使用它來構建Seq。但即使在我的機器列表中速度較慢，所以我想象不是由數據結構的選擇造成的速度差異，而是代碼中的其他變化。 – 2016-07-27 23:24:14

Data.Sequence.Seq與[]相比有多快？

回答

相關問題