Неизменный Словарь наверху?

Question

Неизменный Словарь наверху?

При использовании неизменных словарей в F#, сколько наверху там при добавлении / удаление записей?

Это будет рассматривать все блоки как неизменные и клонировать их и только воссоздавать блок, кто объект, изменился?

Даже если это имеет место, кажется, что существует большое копирование, которое должно быть сделано для создания нового словаря (?)

6

f# dictionary immutability

задан Roger Johansson 8 May 2010 в 05:41

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 - это примерно хороший пример для «траты» на ребалансировку дерева. Но уже поздно, поэтому я не уверен, достаточно ли хорошо обдумал это. :)

1

ответ дан 17 December 2019 в 00:05

Другие вопросы по тегам:

f# dictionary immutability

Похожие вопросы:

score 6 · Accepted Answer

Я рассмотрел реализацию типа F # Map и думаю, что он реализован как функциональное дерево AVL . Он хранит значения во внутренних узлах дерева, а также в листах и для каждого узла гарантирует, что | height (left) - height (right) | <= 1 .

Я думаю, что средняя и наихудшая сложность равна O (log (n)) :

Insert , нам нужно клонировать все узлы на пути от корня до вновь вставленный элемент и высота дерева не больше O (log (n)) . На «обратном пути» дереву может потребоваться перебалансировать каждый узел, но это также только O (log (n))
Remove аналогично - мы находим элемент, а затем клонируем все узлы из корень к этому элементу (перебалансировка узлов на обратном пути к корню)

Обратите внимание, что другие структуры данных, которым не нужно перебалансировать все узлы от корня к текущему при вставке / удалении, на самом деле не будут полезно в неизменяемом сценарии, потому что вам в любом случае нужно создавать новые узлы для всего пути.