Immutable Sözlük genel gider?

Question

F # içinde değişmez sözlükler kullanıldığında, giriş eklerken/çıkarırken ne kadar ek yük var?

Tüm kovaları değişmez olarak kabul edip bunları klonlayacak ve yalnızca öğeyi değiştiren kovayı yeniden oluşturacak mı? Bu durumda dahi

, (?) Yeni sözlük oluşturmak için yapılması gereken kopyalama bir sürü var gibi görünüyor ağaç yapısının bir çok yeniden kullanılabilir

Answer 1

F # Map<K,V> türünün uygulamasına baktım ve bunun bir functional AVL tree olarak uygulandığını düşünüyorum. Ağaçların iç düğümlerinde ve yapraklarda ve her düğüm için değerleri depolar, | yükseklik (sol) - yükseklik (sağ) | < = 1.

  A 
     / \ 
     B  C 
    / \ 
    D  E 

Ben ortalama ve en kötü durum karmaşıklığı hem O(log(n)) olduğunu düşünüyorum:

• takın biz, yeni eklenen eleman ve kökten yolunda bütün düğümlerin klonlamak gerekir Ağacın yüksekliği en fazla O(log(n)). "Dönüş yolu" üzerinde sadece O(log(n))

• çıkarın ağaç her düğümü yeniden dengelemek gerekebilir, ama bu da var benzer - biz eleman bulmak ve sonra o elemana kökünden tüm düğümleri (rebalancing düğümleri klonlamak yerleştirme geçerli birine kökünden tüm düğümleri yeniden dengelemek gerekmez diğer veri-yapıları/silme değişmez gerçekten yararlı olmayacağını kök geri yolda)

Not üzerinde senaryo, çünkü zaten tüm yol için yeni düğümler oluşturmanız gerekir.

Answer 2

. Ben algoritmik karmaşıklığı offhand bilmiyorum, ortalama olarak tahmin ediyorum sadece gibi logn 'atık' amortize gibi ...

Neden ölçmek için bir program yazmaya çalışmayın? (Kendim denemek için bu gece motive eğer Göreceğiz.)

DÜZENLEME

Tamam, burada girildi şeydir. Burada yararlı bir veri olup olmadığına karar vermedim.

open System 

let rng = new Random() 
let shuffle (array : _[]) = 
    let n = array.Length 
    for x in 1..n do 
     let i = n-x 
     let j = rng.Next(i+1) 
     let tmp = array.[i] 
     array.[i] <- array.[j] 
     array.[j] <- tmp 

let TryTwoToThe k = 
    let N = pown 2 k 

    GC.Collect() 

    let a = Array.init N id 

    let makeRandomTreeAndDiscard() = 
     shuffle a 
     let mutable m = Map.empty 
     for i in 0..N-1 do 
      m <- m.Add(i,i) 

    for i in 1..20 do 
     makeRandomTreeAndDiscard() 
    for i in 1..20 do 
     makeRandomTreeAndDiscard() 
    for i in 1..20 do 
     makeRandomTreeAndDiscard() 

#time 
// run these as separate interactions 
printfn "16" 
TryTwoToThe 16 

printfn "17" 
TryTwoToThe 17 

printfn "18" 
TryTwoToThe 18 

benim kutuyu FSI bu çalıştırmak

, ben hafıza süper doğrusal ama çok kötü bir şekilde ölçekleme olabilir anlaşılacağı

--> Timing now on 

> 
16 
Real: 00:00:08.079, CPU: 00:00:08.062, GC gen0: 677, gen1: 30, gen2: 1 
> 
17 
Real: 00:00:17.144, CPU: 00:00:17.218, GC gen0: 1482, gen1: 47, gen2: 4 
> 
18 
Real: 00:00:37.790, CPU: 00:00:38.421, GC gen0: 3400, gen1: 1059, gen2: 17 

olsun. Gen0 koleksiyonlarının ağacın yeniden dengelenmesi için “atık” için kabaca iyi bir vekil olduğunu düşünüyorum. Ama geç oldu, bu yüzden yeterince iyi düşünmüşsem emin değilim. :)