FParsec爲什麼使用列表？

我想我會嘗試使用FParsec編寫一個快速解析器，並很快意識到返回一個列表是一個嚴重的性能問題many。後來我發現，使用在一個文檔的ResizeArray替代：FParsec爲什麼使用列表？

let manyA2 p1 p = 
    Inline.Many(firstElementParser = p1, 
       elementParser = p, 
       stateFromFirstElement = (fun x0 -> 
              let ra = ResizeArray<_>() 
              ra.Add(x0) 
              ra), 
       foldState = (fun ra x -> ra.Add(x); ra), 
       resultFromState = (fun ra -> ra.ToArray()), 
       resultForEmptySequence = (fun() -> [||])) 

let manyA p = manyA2 p p

在我的代碼使用這種替代使得它運行快好幾倍。那麼爲什麼FParsec默認使用列表而不是ResizeArray？

來源

2015-04-01 Jon Harrop

除非團隊中的成員貢獻了這一點，否則將是最好的猜測...因此可能不適合用於計算器。從寫作類似事物的個人經驗來看，專注於以可維護的方式讓事情在性能上工作往往是更有利的策略......至少在產品的前幾個版本中。只要有「足夠快」的工作，那麼每個人都很高興。 – lzcd 2015-04-01 22:08:19

我同意但作者已回覆。 :-) – 2015-04-02 15:38:30

使用內置的F＃列表類型作爲序列組合器的結果類型，使得組合器在F＃中使用起來更加方便，並且可以說會導致更習慣的客戶端代碼。由於大多數F＃開發人員在性能上比簡單和優雅（至少在我的經驗中）更重視使用列表作爲缺省設計API時的正確選擇。同時我試圖讓用戶很容易定義他們自己的專用序列組合器。

目前，返回列表的序列組合器也使用內部列表來構建序列。對於具有超過約2個元素的序列，這是次優的，因爲在返回之前該列表必須被顛倒。但是，我不確定更改實現是否值得付出努力，因爲如果您的解析器對性能非常敏感，並且您正在解析長序列，那麼最好不要使用列表。

我可能應該添加一個關於使用數組而不是列表的章節關於性能的用戶指南章節。

來源

2015-04-02 11:53:47

這很有道理，謝謝。現在我想起它，我不確定會有更好的選擇。一個'ResizeArray'在一個'many'裏面會很棒，但是如果你有很多（很多...）''那麼你會想要一些你可以有效地連接的東西。 – 2015-04-02 15:40:26

對於性能關鍵分析器（combinator）函數，您始終可以選擇下拉到FParsec的低級API並「手動」實現分析器。對於嵌套序列組合器，這將例如允許您將元素解析到單個容器中。它還允許你使用直接的'CharStream'方法調用來跳過分隔符和空格，這可能會給你帶來額外的性能提升。 – 2015-04-02 16:37:31

FParsec爲什麼使用列表？

回答

相關問題