불변의 사전 오버 헤드?

Question

F #에 불변 사전을 사용할 때 항목을 추가/제거 할 때 얼마나 많은 오버 헤드가 있습니까?

전체 버킷을 변경 불가능한 것으로 간주하고 복제하고 항목이 변경된 버켓 만 다시 작성합니까? 그런 경우가 있더라도

, (?) 새로운 사전을 만들기 위해 수행해야 할 복사 많이있다처럼 보인다 트리 구조의 많은 재사용 할 수

Answer 1

F # Map<K,V> 유형의 구현을 살펴본 결과 functional AVL tree으로 구현 된 것 같습니다. Tree의 내부 노드와 leafs에 값을 저장하고 각 노드에 대해 | height (left) - height (right) | < = 1.

  A 
     / \ 
     B  C 
    / \ 
    D  E 

나는 평균과 최악의 복잡성 모두 O(log(n))이라고 생각 :

• 삽입 우리가 새로 삽입 된 요소와의 루트에서 경로에있는 모든 노드를 복제 할 필요가 나무의 높이는 많아야 O(log(n))입니다. 은 "돌아 오는 길"에 만 O(log(n))

• 를 제거 트리 각 노드를 재조정해야 할 수도 있습니다,하지만 또한 것은 유사하다 - 우리는 요소를 발견하고 그 요소에 루트에서 모든 노드 (재조정 노드를 복제 삽입의 현재 하나에 루트에서 모든 노드를 재조정 할 필요가 없습니다 다른 데이터 구조/삭제가 불변 정말 유용하지 않을 것이라는 점을 다시 루트로가는 길)

참고 왜냐하면 전체 경로에 대해 새 노드를 만들 필요가 있기 때문입니다.

Answer 2

. 알고리즘의 복잡성에 대해서는 잘 모릅니다. 평균적으로 상각 된 logN '낭비'와 같은 것이 있습니다 ...

측정 할 프로그램을 작성하지 않으시겠습니까? (나는 그것을 자신을 시도하는 오늘 밤에 동기를 부여 할 수 있다면 우리는 볼 수 있습니다.)

편집

좋아, 여기에 내가 해킹 뭔가입니다. 여기에 유용한 데이터가 있는지 여부는 결정하지 않았습니다.

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 

내 상자 FSI이 실행

, 나는 메모리가 슈퍼 선형하지만 너무 심하게 확장 될 수 있습니다 제안

--> 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 

를 얻을. 나는 gen0 컬렉션이 대략 트리의 재조정이라는 '낭비'에 대한 좋은 대용품이라고 추정하고 있습니다. 그러나 늦었 기 때문에 충분히 잘 생각한 것인지 확신 할 수 없습니다. :)