Понимание изменчивости в F#: тематическое исследование
Я новичок в F#, и это моя первая попытка программирования чего-то серьезного. Извините, код немного длинный, но есть некоторые проблемы с изменчивостью, которые я не понимаю.
Это реализация алгоритма Каргера MinCut для вычисления mincut на компоненте неориентированного графа. Я не буду обсуждать здесь, как работает алгоритм, для получения дополнительной информации https://en.wikipedia.org/wiki/Karger%27s_algorithm Важно то, что это рандомизированный алгоритм, который запускает определенное количество пробных прогонов и принимает "лучший" пробег.
Теперь я понимаю, что мог бы избежать многих проблем, описанных ниже, если бы я создавал определенную функцию для каждого случайного испытания, но я хотел бы ТОЧНО понять, что не так в приведенной ниже реализации.
Я запускаю код на этом простом графике (сокращение составляет 2, когда мы разрезаем график на 2 компонента (1,2,3,4) и (5,6,7,8) только с двумя ребрами между этими 2 компонентами.)
3--4-----5--6
|\/| |\/|
|/\| |/\|
2--1-----7--8
файл simplegraph.txt должен закодировать этот график следующим образом (1-й столбец = номер узла, другие столбцы = ссылки)
1 2 3 4 7
2 1 3 4
3 1 2 4
4 1 2 3 5
5 4 6 7 8
6 5 7 8
7 1 5 6 8
8 5 6 7
Этот код может выглядеть слишком императивным программированием, извините за это.
Таким образом, есть главная петля для каждого вызова. первое выполнение (когда i=1) выглядит гладким и безупречным, но у меня есть выполнение ошибок времени выполнения, когда i=2, потому что выглядит, что некоторые переменные, такие как WG, не инициализируются правильно, вызывая ошибки, связанные с привязкой.
WG, WG1 и WGmin являются type wgraphobj, которые являются записью объектов Dictionary, WG1 определен вне основного цикла, и я не делаю новых назначений для WG1. [но его тип изменчив, хотя, увы]
Я определил первый WG с инструкцией
let mutable WG = WG1
затем в начале цикла for я пишу
WG <- WG1
а затем позже я изменяю объект WG в каждом испытании, чтобы сделать некоторые вычисления. Когда испытание закончено, и мы переходим к следующему испытанию (увеличивается), я хочу сбросить WG в исходное состояние, подобное WG1. но, кажется, это не работает, и я не понимаю, почему...
Вот полный код
MyModule.fs [некоторые функции не нужны для выполнения]
namespace MyModule
module Dict =
open System.Collections.Generic
let toSeq d = d |> Seq.map (fun (KeyValue(k,v)) -> (k,v))
let toArray (d:IDictionary<_,_>) = d |> toSeq |> Seq.toArray
let toList (d:IDictionary<_,_>) = d |> toSeq |> Seq.toList
let ofMap (m:Map<'k,'v>) = new Dictionary<'k,'v>(m) :> IDictionary<'k,'v>
let ofList (l:('k * 'v) list) = new Dictionary<'k,'v>(l |> Map.ofList) :> IDictionary<'k,'v>
let ofSeq (s:('k * 'v) seq) = new Dictionary<'k,'v>(s |> Map.ofSeq) :> IDictionary<'k,'v>
let ofArray (a:('k * 'v) []) = new Dictionary<'k,'v>(a |> Map.ofArray) :> IDictionary<'k,'v>
Karger.fs
open MyModule.Dict
open System.IO
let x = File.ReadAllLines "\..\simplegraph.txt";;
// val x : string [] =
let splitAtTab (text:string)=
text.Split [|'\t';' '|]
let splitIntoKeyValue (s:seq<'T>) =
(Seq.head s, Seq.tail s)
let parseLine (line:string)=
line
|> splitAtTab
|> Array.filter (fun s -> not(s=""))
|> Array.map (fun s-> (int s))
|> Array.toSeq
|> splitIntoKeyValue
let y =
x |> Array.map parseLine
open System.Collections.Generic
// let graph = new Map <int, int array>
let graphD = new Dictionary<int,int seq>()
y |> Array.iter graphD.Add
let graphM = y |> Map.ofArray //immutable
let N = y.Length // number of nodes
let Nruns = 2
let remove_table = new Dictionary<int,bool>()
[for i in 1..N do yield (i,false)] |> List.iter remove_table.Add
// let remove_table = seq [|for a in 1 ..N -> false|] // plus court
let label_head_table = new Dictionary<int,int>()
[for i in 1..N do yield (i,i)] |> List.iter label_head_table.Add
let label = new Dictionary<int,int seq>()
[for i in 1..N do yield (i,[i])] |> List.iter label.Add
let mutable min_cut = 1000000
type wgraphobj =
{ Graph : Dictionary<int,int seq>
RemoveTable : Dictionary<int,bool>
Label : Dictionary<int,int seq>
LabelHead : Dictionary<int,int> }
let WG1 = {Graph = graphD;
RemoveTable = remove_table;
Label = label;
LabelHead = label_head_table}
let mutable WGmin = WG1
let IsNotRemoved x = //
match x with
| (i,false) -> true
| (i,true) -> false
let IsNotRemoved1 WG i = //
(i,WG.RemoveTable.[i]) |>IsNotRemoved
let GetLiveNode d =
let myfun x =
match x with
| (i,b) -> i
d |> toList |> List.filter IsNotRemoved |> List.map myfun
let rand = System.Random()
// subsets a dictionary given a sub_list of keys
let D_Subset (dict:Dictionary<'T,'U>) (sub_list:list<'T>) =
let z = Dictionary<'T,'U>() // create new empty dictionary
sub_list |> List.filter (fun k -> dict.ContainsKey k)
|> List.map (fun k -> (k, dict.[k]))
|> List.iter (fun s -> z.Add s)
z
// subsets a dictionary given a sub_list of keys to remove
let D_SubsetC (dict:Dictionary<'T,'U>) (sub_list:list<'T>) =
let z = dict
sub_list |> List.filter (fun k -> dict.ContainsKey k)
|> List.map (fun k -> (dict.Remove k)) |>ignore
z
// subsets a sequence by values in a sequence
let S_Subset (S:seq<'T>)(sub_list:seq<'T>) =
S |> Seq.filter (fun s-> Seq.exists (fun elem -> elem = s) sub_list)
let S_SubsetC (S:seq<'T>)(sub_list:seq<'T>) =
S |> Seq.filter (fun s-> not(Seq.exists (fun elem -> elem = s) sub_list))
[<EntryPoint>]
let main argv =
let mutable u = 0
let mutable v = 0
let mutable r = 0
let mutable N_cut = 1000000
let mutable cluster_A_min = seq [0]
let mutable cluster_B_min = seq [0]
let mutable WG = WG1
let mutable LiveNodeList = [0]
// when i = 2, i encounter problems with mutability
for i in 1 .. Nruns do
WG <- WG1
printfn "%d" i
for k in 1..(N-2) do
LiveNodeList <- GetLiveNode WG.RemoveTable
r <- rand.Next(0,N-k)
u <- LiveNodeList.[r] //selecting a live node
let uuu = WG.Graph.[u] |> Seq.map (fun s -> WG.LabelHead.[s] )
|> Seq.filter (IsNotRemoved1 WG)
|> Seq.distinct
let n_edge = uuu |> Seq.length
let x = rand.Next(1,n_edge)
let mutable ok = false //maybe we can take this out
while not(ok) do
// selecting the edge from node u
v <- WG.LabelHead.[Array.get (uuu |> Seq.toArray) (x-1)]
let vvv = WG.Graph.[v] |> Seq.map (fun s -> WG.LabelHead.[s] )
|> Seq.filter (IsNotRemoved1 WG)
|> Seq.distinct
let zzz = S_SubsetC (Seq.concat [uuu;vvv] |> Seq.distinct) [u;v]
WG.Graph.[u] <- zzz
let lab_u = WG.Label.[u]
let lab_v = WG.Label.[v]
WG.Label.[u] <- Seq.concat [lab_u;lab_v] |> Seq.distinct
if (k<N-1) then
WG.RemoveTable.[v]<-true
//updating Label_head for all members of Label.[v]
WG.LabelHead.[v]<- u
for j in WG.Label.[v] do
WG.LabelHead.[j]<- u
ok <- true
printfn "u= %d v=%d" u v
// end of for k in 1..(N-2)
// counting cuts
// u,v contain the 2 indexes of groupings
let cluster_A = WG.Label.[u]
let cluster_B = S_SubsetC (seq[for i in 1..N do yield i]) cluster_A // defined as complementary of A
// let WG2 = {Graph = D_Subset WG1.Graph (cluster_A |> Seq.toList)
// RemoveTable = remove_table
// Label = D_Subset WG1.Graph (cluster_A |> Seq.toList)
// LabelHead = label_head_table}
let cross_edge = // returns keyvalue pair (k,S')
let IsInCluster cluster (k,S) =
(k,S_Subset S cluster)
graphM |> toSeq |> Seq.map (IsInCluster cluster_B)
N_cut <-
cross_edge |> Seq.map (fun (k:int,v:int seq)-> Seq.length v)
|> Seq.sum
if (N_cut<min_cut) then
min_cut <- N_cut
WGmin <- WG
cluster_A_min <- cluster_A
cluster_B_min <- cluster_B
// end of for i in 1..Nruns
0 // return an integer exit code
Описание алгоритма: (я не думаю, что это слишком важно для решения моей проблемы)
на каждом испытании есть несколько шагов. на каждом шаге мы объединяем 2 узла в 1 (эффективно удаляя 1), обновляя граф. мы делаем это 6 раз, пока не останется только 2 узла, которые мы определяем как 2 кластера, и мы смотрим на количество перекрестных ребер между этими 2 кластерами. если нам "повезет", то эти 2 кластера будут (1,2,3,4) и (5,6,7,8) и найдут правильное количество сокращений. на каждом шаге объект WG обновляется с эффектами слияния 2 узлов, причем только живые узлы (те, которые не исключены в результате слияния 2 узлов) идеально обновляются.
WG.Graph - обновленный граф
WG.Label содержит метки узлов, которые были объединены в текущий узел
WG.LabelHead содержит метку узла, в который этот узел был объединен
WG.RemoveTable говорит, был ли удален узел или нет.
Заранее спасибо всем, кто захочет взглянуть на это!
1 ответ
"Кажется, не работает", потому что wgraphobj является ссылочным типом, который выделяется в стеке, что означает, что когда вы изменяете внутренности WG ты тоже мутируешь внутренности WG1 потому что они одинаковые внутренности.
Это именно тот беспорядок, в который вы попадаете, если используете изменяемое состояние. Вот почему люди рекомендуют не использовать его. В частности, использование изменяемых словарей подрывает надежность вашего алгоритма. Я рекомендую использовать собственный эффективный неизменяемый словарь F# (называемый Map) вместо
Теперь, в ответ на ваш комментарий о WG.Graph <- GraphD дает ошибку компиляции.
WG изменчив, но WG.Graph нет (но содержание WG.Graph снова изменчивы). Есть разница, позвольте мне попытаться объяснить это.
WG изменчив в том смысле, что он указывает на некоторый объект типа wgraphobj, но вы можете сделать так, чтобы в ходе вашей программы он указывал на другой объект того же типа.
WG.Graph с другой стороны, поле упаковано внутри WG, Это указывает на некоторый объект типа Dictionary<_,_>, И вы не можете указать это на другой объект. Вы можете создать другой wgraphobj в котором поле Graph указать другой словарь, но вы не можете изменить, где поле Graph оригинала wgraphobj точки.
Для того, чтобы сделать поле Graph сам изменяемый, вы можете объявить это так:
type wgraphobj = {
mutable Graph: Dictionary<int, int seq>
...
Тогда вы сможете изменить это поле:
WG.Graph <- GraphD
Обратите внимание, что в этом случае вам не нужно объявлять значение WG сам как mutable,
Тем не менее, мне кажется, что для ваших целей вы можете пойти по пути создания нового экземпляра wgraphobj с полем Graph изменил, и присвоив его изменяемой ссылке WG:
WG.Graph <- { WG with Graph = GraphD }