Ottenere la lunghezza costante recuperare la costante di tempo con elenchi immutabili in un contesto di programmazione funzionale

Question

Attualmente sto affrontando il problema di dover eseguire i calcoli in base alla lunghezza di una determinata lista. Dovendo scorrere tutti gli elementi della lista per conoscerne le dimensioni è una grossa penalizzazione delle prestazioni dato che sto usando liste piuttosto grandi.

Quali sono gli approcci suggeriti al problema?

Immagino che potrei sempre portare un valore di dimensione insieme alla lista in modo da conoscere in anticipo la sua dimensione senza doverlo calcolare sul sito di chiamata ma sembra un approccio fragile. Potrei anche definire un proprio tipo di lista in cui ogni nodo ha come proprietà la dimensione delle liste ma poi perderei la leva fornita dalle librerie del mio linguaggio di programmazione per gli elenchi standard.

Come gestite questo nella vostra routine quotidiana?

Attualmente sto usando F #. Sono consapevole di poter utilizzare le liste mutabili (array) di .NET, che potrebbero risolvere il problema. Sono molto più interessato, però, all'approccio funzionale puramente immutabile.

Answer 1

Il built-in F # di tipo lista non ha la cache della lunghezza e non c'è modo di aggiungere che in qualche modo intelligente, quindi avrai bisogno di definire il proprio tipo . Penso che scrivere un wrapper per il tipo F # list esistente sia probabilmente l'opzione migliore.

In questo modo, è possibile evitare conversioni esplicite - quando si avvolgono l'elenco, non sarà effettivamente copiarlo (come nella realizzazione di svick), ma l'involucro può facilmente memorizzare nella cache la proprietà 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 

Il Il modo migliore per lavorare con il wrapper è usare LengthList.ofList per creare LengthList da un elenco F # standard e usare la proprietà LengthList.toList (o solo la List) prima di utilizzare qualsiasi funzione dal modulo standard List.

Tuttavia, dipende dalla complessità del codice: se è necessaria solo la lunghezza in un paio di punti, potrebbe essere più semplice tenerlo separatamente e utilizzare una tupla list<'T> * int.

Answer 2

Non vedo perché accarezzare la lunghezza è un approccio fragile. Prova qualcosa del genere (Haskell):

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 

e così via. Se questo è in una libreria o in un modulo, puoi renderlo sicuro (credo) non esportando il costruttore NList.

Potrebbe anche essere possibile forzare GHC a memoizing length, ma non sono sicuro di come o quando.

Answer 3

In F #, la maggior parte delle funzioni List ha le stesse funzioni Seq. Ciò significa che puoi semplicemente implementare la tua lista collegata immutabile che porta la lunghezza di ogni nodo. Qualcosa di simile a questo:

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

Come gestite questo nella vostra routine quotidiana?

Non lo facciamo, perché questo non è un problema nella routine quotidiana. Sembra un problema forse in domini limitati.

Se hai creato gli elenchi di recente, probabilmente hai già eseguito O (N), quindi camminare per la lista non è un grosso problema.

Se si stanno creando alcuni elenchi molto grandi che quindi non "cambiano" molto (ovviamente non cambiano mai, ma intendo cambiare il set di riferimenti ai capi degli elenchi utilizzati nel proprio dominio/algoritmo), quindi può avere senso semplicemente avere un dizionario a lato delle tuple di lunghezza di riferimento-a-testa di lista * e consultare il dizionario quando si richiedono lunghezze (facendo il vero lavoro per camminarle quando necessario, ma i risultati di memorizzazione nella cache per le domande future la stessa lista).

Infine, se si ha veramente a che fare con un algoritmo che deve aggiornare costantemente gli elenchi in gioco e consultare costantemente le lunghezze, quindi creare il proprio tipo di dati tipo elenco (sì, sarà anche necessario scrivere la mappa/filtro e tutti gli altri).

(In generale, penso che in genere sia preferibile utilizzare le strutture dati incorporate il 99,99% del tempo. Nello 0,01% del tempo in cui si sta sviluppando un algoritmo o un bit di codice che deve essere molto altamente ottimizzato, quindi quasi sempre è necessario abbandonare le strutture dati integrate (che sono abbastanza buone per la maggior parte dei casi) e utilizzare una struttura dati personalizzata progettata per risolvere il problema esatto su cui si sta lavorando. Data Structures "per idee e insight in quel caso, ma raramente si passa a questo caso.)