Leistung von Traveling Salesman in F #

Question

Meine Frage ist nicht auf den Algorithmus selbst, sondern auf die Leistung von F #, wenn es an sein Limit geschoben wird. In diesem Fall ein Programm, wo ich versuche, das Problem mit 25 Städten durch rohe Gewalt zu lösen (Dynamische Programmierung)

(Der Algorithmus schien für ein kleines Beispiel gut zu funktionieren, und ich bin zuversichtlich, dass es seine Arbeit macht)

Ich drucke eine Zählervariable im Konsolenausgabefenster, um den Fortschritt zu überwachen. Wie für die ersten bis m=12 Iterationen erwartet, nimmt die Laufzeit exponentiell zu.

m=2 
1887ms; 
m=3 
1870ms; 
m=4 
1902ms; 
m=5 
2074ms; 
m=6 
2954ms; 
m=7 
6261ms; 
m=8 
16746ms; 
m=9 
38442ms; 
m=10 
80396ms; 
m=11 
140985ms; 
m=12 
207950ms; 

So obwohl die Leistung von vor Iteration 13 nicht stellar ist, zumindest scheint seine "überschaubar". Wenn mein Verständnis stimmt, sind Iteration 12 und 13 am CPU-lastigsten. Dennoch hätte ich von dem Ausführungsmuster eine Ausführungszeit von ungefähr 300000 ms für diese Iteration erwartet, und das ist nicht der Fall.

Zoom auf den Kontrollmonitor meines (neuen) iMAC Retina läuft auf MacOS X 10.11.3 El Capitan, ausgestattet mit 3,3 Ghz i7 Quad-Core, 16 GB RAM und einer SSD, F # läuft in Xamarin.Studio 6.0 . Ich sehe die Speicherbelegung durch das Programm ist eine große 3 GB. Es wurde überhaupt nicht optimiert, aber es sollte gut innerhalb der Fähigkeiten der Maschine sein und sollte keine Last sein?

m=13 sehr, sehr, sehr langsamer Fortschritt, im Tempo schien es, es würde Stunden dauern, um zu berechnen. Zu diesem Zeitpunkt wird auf der CPU-Seite des Monitors angegeben, dass der Prozess 105% der CPU verwendet (erste Spalte links). Nach 1 Stunde (und 2/3 die Iteration abgeschlossen) abgestürzt es mit der folgenden Meldung:

Error: Garbage collector could not allocate 16384 bytes of memory for major heap section.

Ich bin ein wenig überrascht, ich Garbage Collection tun müssen, weil, Speicher nicht wie das Hauptproblem aussah ?

ich definiere eine enormes Array2D mit 2^24 Einträgen und 24 Spalten = 17M * 24 Einträge von (float32 sbyte *) unter Verwendung von 32 + 8 = 40 Bits = 5 Bytes jedes so 2 GB

Vielleicht das ist, wo ist das Problem, dass ich eine for S in Subset_of_size_m Schleife mache?

Dies muss 2,700,000 mal bei Iteration 13 (gestoppt bei 1,860,000) in dieser Schleife gemacht werden. Ich mache einige Zuweisungen von Listen. Vielleicht gibt es dort eine Müllsammlung?

Ich habe das noch nie zuvor in F # gemacht (nur in R, wo es genügt, von Zeit zu Zeit den Befehl GC() oder remove(object) zu schreiben. Überwachung im Kontrollmonitor, Speicher scheint nie ein Problem im Vergleich zum verfügbaren RAM zu sein? Was passiert ist?

Ich verstehe, ich sollte vielleicht einen besseren Algorithmus finden, der weniger speicherintensiv ist, aber trotzdem ist es die gute Gelegenheit, um über dieses Problem zu lernen, und im Vergleich zu anderen Menschen, die das Problem gelöst, die Ausführungszeit wenn alles ging wie geplant, war für einen ersten (brutalen) Versuch nicht völlig lächerlich.Hier

ist der Quellcode

//////// Travelling Salesman problem //////// 


open System 
open System.Collections 
open System.Collections.Generic 
open System.IO 

open System.Windows 

open FSharp.Charting 

exception InnerError of string 


let stopWatch = System.Diagnostics.Stopwatch.StartNew() 

///////////////// preparing the data ///////////////// 

// format of the files 
//[number_of_cities] 
//[x_1] [y_1] // coordinate 

let x = File.ReadAllLines "/Users/francois-guillaume.rideau/Documents/MOOC/TSP.txt" 

let split (text:string)= 
    text.Split [|'\t';' '|] 

let splitInto2Values (A: string []) = 
    (float A.[0],float A.[1]) 

let parseLine (line:string) = 
    line 
    |> split 
    |> splitInto2Values 



let num_cities = int x.[0] // 25 

let cities = x |> Array.tail |> Array.map parseLine // [x_1][y_1] 

let dist_matrix = Array2D.create num_cities num_cities 0.0f 
for i in 0..(num_cities-1)do 
    for j in 0..(num_cities-1) do 
     dist_matrix.[i,j]<- float32 (sqrt ((fst cities.[i] - fst cities.[j])*(fst cities.[i] - fst cities.[j]) + (snd cities.[i] - snd cities.[j])*(snd cities.[i] - snd cities.[j]))) 

let arrayOfArrays = [| [| 0.0f; 2.0f;1.0f;4.0f |]; [|2.0f;0.0f; 3.0f;5.0f |]; [|1.0f;3.0f; 0.0f;6.0f |]; [|4.0f;5.0f; 6.0f;0.0f |] |] 
let example = Array2D.init 4 4 (fun i j -> arrayOfArrays.[i].[j]) 

// Dynamic programming algorithm 

// Subproblems: 
// For every destination j in {1,2,......n} every subset S in {1,2,....n} that contains 1 and j, let 
// A(S,j) = minimum length of a path of a path from 1 to j that visits precisely the vertices of S [exactly once each] 

// create A = Array2D indexed by subsets S that contain 1 and destinations j 
// Base Case A[S,1] = 0 if S = {1} , +infinity otherwise 
// for m = 2,3,4,.... n (m = subproblem size) 
//  for each Set S in {1,2,...n} of size m that contains 1 
//   for each j in S, j different from 1: 
//    A[S,j] = min (k in S, k <> j) {A[S-{j},k]+Ckj} 
// Return min (j=2 to n) A[{1,2,3,....,n},j]+Cj1 

let limit = 100000000.0f 

//// the first city is city 0 in array D. we put it apart, 
//// then we represents S as integers. 
//// we take the binary representation of integer, and the pth bit indicates whether city p+1 belongs to S 
//// for example S =11 = 1+2+8 contains cities 2,3 and 9 (members 11 will return [(0, 1); (1, 2); (3, 8)]) 

/////////////////////////////// with path /////////////////////////////////////////// 

let TSP_all_c_Dynamic_Programming_with_path_main(D:float32 [,]) = // solves the TSP problem when ALL cities are connected together with an exhaustive search in exponential time O(n^2 2^n) 
                // the input is a distance matrix in float32 
                // memory usage is not optimized at all.... 

    let num_cities = Array2D.length1 D 
    let l2 = Array2D.length2 D 
    if (l2<>num_cities) then failwith "Distance matrix is not a squared matrix" 
    let powers_of_2 = [|1;2;4;8;16;32;64;128;256;512;1024;2048;4096;8192;16384;32768;65536;131072;262144;524288;1048576;2097152;4194304;8388608;16777216|] 
    let power2 k =  
     if ((k >= 25) || (k<0)) then raise (InnerError("power exponent not allowed")) 
      else powers_of_2.[k] 

    let num_subsets = power2 (num_cities-1) 
    let S_full = num_subsets-1 

    let A = Array2D.create num_subsets (num_cities-1) (limit,-1y) 

    A.[0,0]<-(-0.0f,-2y) 

    let rec sumbits (n:int):int= 
     let rec helper acc m = 
     match m with 
      | 0 -> acc 
      | 1 -> acc+1 // remove this ? 
      | _ -> let r = m%2 
        helper (acc+r) (m>>>1) 
     helper 0 n 

    let hashtable = Array2D.create (num_cities-1) num_subsets false // hashtable.[i-1,n]=true if (sumbits n) = i 
    for k in 1..(num_subsets-1) do hashtable.[(sumbits k)-1,k]<-true 
    // member returns [(p,2^p);....] if the p+1th city is in S 
    let members S = [for j in 0..(num_cities-2) do let a= powers_of_2.[j] &&& S 
                if (a<>0) then yield (j,a)] // list length = num_cities-1 


    for m in 2..num_cities do // S size m 
     printfn "m=%A" m 
     let stopWatch = System.Diagnostics.Stopwatch.StartNew() 

     let mutable count = 1 

     let Subset_of_size_m = hashtable.[m-2,0..] |> Seq.mapi (fun i x -> (i,x)) |> Seq.filter (fun (a,b)-> (b=true)) |> Seq.map fst |> Seq.toList 
     for S in Subset_of_size_m do   
      if m = 2 then let (i,S') = (members S).Head 
          A.[S',i]<- (D.[0,i+1],-1y) // distance from 0 to city i+1 
        else 
          let S'_list = List.fold (fun acc x -> let a = (((snd x)^^^S_full)&&&S)    // list of subsets of size m-1 
                   if a = S then acc else (fst x,a)::acc) [] (members S) 
          for (j,S') in S'_list do 
           A.[S,j] <- ([for (k,expk) in (members S') do 
               yield (fst A.[S',k]+D.[j+1,k+1],k) ]|> List.min |> fun (a,b)->(a,sbyte b))// can do faster than that if we remember from above ? 
          count <- count + 1 // to check progress in the console 
          if count%10000 =0 then printfn "count=%A" count 

     printfn "%f" stopWatch.Elapsed.TotalMilliseconds 

    // printfn "%A" A 
    // A.[num_subsets-1,0..] 
    A 

let calculate_path_TSP_all_c_Dynamic_Programming_with_path (D:float32 [,]) = 
    // calls the core subroutine defined above 
    let A' = TSP_all_c_Dynamic_Programming_with_path_main D 
                // memory usage is not optimized at all.... 

    // from here its smooth sailing, just analyzing the results. 

    let num_cities = Array2D.length1 D 
    let l2 = Array2D.length2 D 
    if (l2<>num_cities) then failwith "Distance matrix is not a squared matrix" 

    let powers_of_2 = [|1;2;4;8;16;32;64;128;256;512;1024;2048;4096;8192;16384;32768;65536;131072;262144;524288;1048576;2097152;4194304;8388608;16777216|] 
    let power2 k =  
     if ((k >= 25) || (k<0)) then raise (InnerError("power exponent not allowed")) 
      else powers_of_2.[k] 

    let num_subsets = power2 (num_cities-1) 
    let S_full = num_subsets-1 

    let A'' = A'.[S_full,0..] 

    let res' = [for i in 0..num_cities-2 do yield (fst A''.[i]+ example.[0,i+1]) ] |> Seq.mapi (fun i x -> (i, x)) |> Seq.minBy snd 
    printfn "TSP answer = %A" res' 

    let path = Array.create (num_cities+1) -1y 

    let mutable current_city = sbyte (fst res') 
    path.[num_cities-1]<- current_city// the last city 

    let mutable current_S = S_full 
    let mutable next_S = -2 
    let mutable next_city = -2y 

    for k in num_cities-2..-1..1 do 
     next_city <- snd A'.[current_S,int current_city] 
     next_S <- (S_full^^^powers_of_2.[int current_city]) &&& current_S 
     //printfn "k=%A current_S=%A next_city=%A" k current_S next_city 
     path.[k]<-next_city 
     current_S<-next_S 
     current_city<-next_city 

    for i in 0..num_cities do path.[i]<-path.[i]+1y 
    printfn "path=%A" path 


////// main program ///// 

calculate_path_TSP_all_c_Dynamic_Programming_with_path dist_matrix 

Answer 1

Ich habe nicht Sie Code überhaupt analysiert, aber da Sie Targeting Debug/x86 Konfiguration bedeutet es, dass Sie App:

• nicht sicher haben Optimierung (die die Speichernutzung erhöhen kann), um mehr Debugging-Informationen zur Verfügung zu stellen
• verwendet nur 32-Bit-Anweisungen des x86-Prozessor-Befehlssatzes und deshalb kann es nicht mehr als 4 GB Speicher (oder le ss, depending on your OS)

Versuchen Sie, es zu etwas wie Release/x64 (*) zu ändern. Sie können auch Parameter von Monos eingebautem garbage collector optimieren.

Sie können davon ausgehen, dass die Anzahl der von Ihrem Algorithmus verarbeiteten Elemente drastisch abnimmt, wenn die von Ihrem Programm verwendeten Daten die Mehrheit des für einen Prozess verfügbaren Speichers belegen. In diesem Fall verbringt Ihr Programm die meiste Zeit mit Garbage Collections (jeder GC kann nur eine kleine Menge Speicher freigeben, da die Mehrheit der Objekte lebt) und nur einen Bruchteil der Zeit mit "echten" Berechnungen (und Berechnungen erfordern Speicherzuweisungen, die Trigger GC).

Die andere Sache, die hilfreich sein kann, wenn Sie die Speicherauslastung untersuchen, ist ein Speicherprofiler.

Sie erwähnten, dass Sie in R die Speicherbereinigung erzwingen können; In .NET können Sie das auch tun, indem Sie GC.Collect() aufrufen, jedoch wird in den meisten Fällen davon abgeraten (Garbage Collection wird automatisch durchgeführt, wenn es notwendig ist).

* Sie benötigen einen Compiler, der 64-Bit-Assemblys und eine 64-Bit-Common Language Runtime zum Ausführen Ihres Codes erstellt. Mono 2.10 on MacOS X doesn't support 64-bits unless it is built from sources:

Support for 64-bit VMs as of Mono 2.10 is only available if you build Mono from source code and install your own copy of the VM. In the future we will ship both mono and mono64 binaries for our users.

Neuere Versionen haben universelle Installateure und ich denke, dass sie 64-Bit unterstützen.