在函數式編程環境中獲取恆定長度的檢索時間常量與不可變列表

Question

我目前面臨的問題是必須根據給定列表的長度進行計算。不得不迭代列表中的所有元素以知道其大小是一個巨大的性能損失，因爲我使用的是較大的列表。

這個問題的建議方法是什麼？

我想我可以隨身攜帶大小值和列表，所以我事先知道它的大小，而不必在調用站點計算它，但這似乎是一個脆弱的方法。我也可以定義一個自己的列表，其中每個節點的屬性都是列表的大小，但是我會失去編程語言庫提供的用於標準列表的槓桿作用。

你們在日常工作中如何處理這個問題？

我目前使用F＃。我知道我可以使用.NET的可變（數組）列表，這將解決問題。儘管如此，我對這種純粹不可變的功能方法更感興趣。

Answer 1

內置的F＃列表類型不具有任何長度緩存和沒有辦法增加，在一些巧妙的方式，所以你需要定義自己的類型。我認爲爲現有的F＃list類型編寫封裝器可能是最佳選擇。

這樣，就可以避免顯式轉換 - 當你包的列表中，它實際上並不會複製它（如在svick的實現），但包裝可以很容易地緩存Length屬性：

open System.Collections 

type LengthList<'T>(list:list<'T>) = 
    let length = lazy list.Length 
    member x.Length = length.Value 
    member x.List = list 
    interface IEnumerable with 
    member x.GetEnumerator() = (list :> IEnumerable).GetEnumerator() 
    interface seq<'T> with //' 
    member x.GetEnumerator() = (list :> seq<_>).GetEnumerator() 

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>] 
module LengthList = 
    let ofList l = LengthList<_>(l) 
    let ofSeq s = LengthList<_>(List.ofSeq s) 
    let toList (l:LengthList<_>) = l.List 
    let length (l:LengthList<_>) = l.Length 

的使用包裝器的最佳方式是使用LengthList.ofList從標準F＃列表創建LengthList，並在使用標準List模塊的任何功能之前使用LengthList.toList（或只是List）屬性。

但是，這取決於你的代碼的複雜性 - 如果你只需要幾個地方的長度，那麼它可能更容易分開保存並使用元組list<'T> * int。

Answer 2

我不明白爲什麼選擇周圍的長度是一個脆弱的方法。試試像這樣（哈斯克爾）：

data NList a = NList Int [a] 

nNil :: NList [a] 
nNil = NList 0 [] 

nCons :: a -> NList a -> NList a 
nCons x (NList n xs) = NList (n+1) (x:xs) 

nHead :: NList a -> a 
nHead (NList _ (x:_)) = x 

nTail :: NList a -> NList a 
nTail (NList n (_:xs)) = NList (n-1) xs 

convert :: [a] -> NList a 
convert xs = NList (length xs) xs 

等等。如果這是在一個庫或模塊中，您可以通過不導出構造函數NList來使其安全（我認爲）。

它也可能強制GHC進行記憶length，但我不知道如何或何時。

Answer 3

在F＃中，大多數List函數都具有等效的Seq函數。這意味着，您可以實現您自己的不變鏈接列表，每個節點都帶有長度。事情是這樣的：

type MyList<'T>(item : Option<'T * MyList<'T>>) = 

    let length = 
     match item with 
     | None -> 0 
     | Some (_, tail) -> tail.Length + 1 

    member this.Length = length 

    member private this.sequence = 
     match item with 
     | None -> Seq.empty 
     | Some (x, tail) -> 
      seq { 
       yield x 
       yield! tail.sequence 
      } 

    interface seq<'T> with 
     member this.GetEnumerator() = 
      (this.sequence).GetEnumerator() 
     member this.GetEnumerator() = 
      (this.sequence :> System.Collections.IEnumerable).GetEnumerator() 

module MyList = 
    let rec ofList list = 
     match list with 
     | [] -> MyList None 
     | head::tail -> MyList(Some (head, ofList tail)) 

Answer 4

你們在日常生活中如何處理這個問題？

我們不這樣做，因爲這不是日常生活中的問題。這聽起來像是一個問題，也許在有限的領域。

如果您最近創建了列表，那麼您可能已經完成了O（N）工作，因此，走這個列表以獲取其長度可能不是什麼大不了的事情。

如果你製作了幾個非常大的列表，然後不會「改變」很多（顯然不會改變，但我的意思是改變在您的域/算法中使用的列表頭的引用集），那麼它可能有意義的只是在引用到列表頭部長度元組的一側提供一個字典，並且在詢問長度時請參考字典（在需要的時候做真正的工作來行走它們，但是爲將來的問題提供緩存結果相同的列表）。最後，如果你真的在處理一些需要不斷更新列表並且不斷查詢長度的算法，那麼創建你自己的列表類數據類型（是的，你還需要編寫map /過濾器和其他）。 （一般來說，我認爲99.99％的時間通常最好使用內置的數據結構，在0.01％的時間內，你正在開發一個算法或者一些代碼，這些代碼需要非常精確高度優化，那麼幾乎總是需要放棄內置的數據結構（這對大多數情況來說已經足夠好了），並且使用專門用於解決您正在處理的確切問題的自定義數據結構。請參閱wikipedia或Okasaki的「Purely Functional數據結構「的想法和啓發，在這種情況下，但很少去那種情況下。）