F＃旅行推銷員的表現

Question

我的問題不在算法本身，而是在F＃推到極限時的性能。在這個例子中，我試圖用蠻力解決25個城市的問題（動態編程）

（該算法似乎對一個小例子很好，我相信它能完成它的工作）

我在控制檯輸出窗口中打印一個計數變量來監視進度。 與第一次達到m=12迭代期望的一樣，運行時間呈指數增長。

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; 

所以雖然第13次迭代之前的表現並不是很好，至少它看起來是「可管理的」。實際上，如果我的理解是正確的，那麼迭代12和13是CPU最重的。儘管如此，我還是會從執行模式中預期，該迭代的執行時間大約爲300000ms，而不是這種情況。

放大在MacOS X上運行的我的（新）iMAC Retina的控制顯示器10.11.3 El Capitan配備了3.3Ghz i7四核，16 GB RAM和一個SSD，運行在Xamarin.Studio 6.0 。我看到該程序的內存使用量是一個很大的3 GB。它沒有被優化，但它應該在機器的能力範圍之內，並且不應該成爲負擔？

m=13非常非常非常非常緩慢的進展，按照速度，似乎需要幾個小時來計算。在這個階段，在顯示器的CPU側，它表示該進程使用CPU的105％（左側的第一列）。 1小時（和完成迭代的2/3）後墜毀以下消息：

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

我有點驚訝，我需要做垃圾回收，因爲內存看起來並不像的主要問題？

我正在與2^24項和24列= 17M限定巨大Array2D *使用32 + 8 = 40位= 5個字節每個所以2 GB

也許這就是（FLOAT32 *爲sbyte）的24項問題在於我做了一個for S in Subset_of_size_m循環？

這在迭代13（停在1,860,000）時必須完成2,700,000次，在這個循環中我做了一些列表的分配。那裏可能需要垃圾收集？我在F＃中從來沒有做過這樣的事情（只有在R的地方，它可以隨時編寫命令GC()或remove(object)）。在控制監視器中進行監視，與可用RAM相比，內存似乎永遠不成問題？發生了什麼？

我知道我也許應該找到一個更好的算法，它的內存密集程度較低，但無論如何它是學習這個問題的好機會，並且與其他解決問題的人相比，按計劃，第一次（野蠻）嘗試並不是完全荒謬的。

這裏是源代碼

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

我還沒有分析你的代碼在所有的，但因爲你的目標Debug/x86配置就意味着你應用程序：

• 沒有一定的優化（可能會增加內存使用量）以提供更多調試信息
• 僅使用x86處理器指令集的32位指令，並且因此它不能使用超過4GB的內存（或le ss，depending on your OS）

嘗試將其更改爲像Release/x64（*）。您還可以調整Mono內置的參數garbage collector。

可以預計的是，當你的程序使用的數據佔用大部分可用內存爲一個過程，你的算法處理單元的數量將大大減少。在這種情況下，你的程序大部分時間都在做垃圾回收（每個GC只能釋放少量的內存，因爲大部分對象是活着的），而且只有一小部分時間做「真正」的計算（並且計算需要內存分配觸發GC）。

當您調查內存使用情況時可能有幫助的其他內容是內存分析器。

你提到在R中你可以強制垃圾收集;在.NET中，你也可以通過調用GC.Collect()來做到這一點，然而，在大多數情況下使用它是不鼓勵的（垃圾收集在必要時自動執行）。

*您需要一個編譯器生成64位程序集和64位公共語言運行時來運行您的代碼。 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.

新版本具有普遍的安裝，我想，他們支持64位。