Выполнение поездки продавцом в F #

Question

Мой вопрос не о самом алгоритме, а о производительности F #, когда он приближается к своему пределу. В этом случае программа, в которой я пытаюсь решить проблему с 25 городами с помощью грубой силы (динамическое программирование)

(Алгоритм, похоже, отлично подходит для небольшого примера, и я уверен, что он выполняет свою работу)

Я печатаю переменную count в окне вывода консоли для отслеживания прогресса. Как и ожидалось для первых итераций до 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 является самой тяжелой. Тем не менее, я ожидал бы от шаблона исполнения, времени выполнения около 300000ms для этой итерации, и это не так.

Масштабирование на контрольном мониторе моей (новой) сетчатки iMAC, работающей на MacOS X 10.11.3 El Capitan, оснащенный четырехъядерным процессором iOS 4 ГГц, 16 ГБ оперативной памяти и SSD, F #, работающим внутри Xamarin.Studio 6.0 , Я вижу, что использование памяти в программе - это большой 3 ГБ. Он не был оптимизирован вообще, но он должен быть хорошо внутри возможностей машины и не должен быть бременем?

m=13 очень-очень медленный прогресс, в темпе, по-видимому, потребовалось бы несколько часов, чтобы вычислить. На этом этапе, на стороне процессора монитора, он говорит, что процесс использует 105% CPU (первый столбец слева). Через 1 час (и 2/3 завершения итерации) он упал со следующим сообщением:

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

Я немного удивлен, что мне нужно сделать Garbage Collection, потому что память не была похожа на главный вопрос ?

я определяю огромный Array2D с 2^24 записей и 24 столбцов = 17M * 24 вхождений (float32 * SByte) с использованием 32 + 8 = 40 бит = 5 байт каждый так 2 Гб

Возможно Thats где проблема в том, что я делаю цикл for S in Subset_of_size_m?

Это должно быть сделано 2,700,000 раз на итерации 13 (остановлено на 1,860,000) в этом цикле. Я делаю некоторые задания списков. Возможно, там есть коллекция мусора?

Я никогда не делал этого раньше в F # (только в R, где хватало время, чтобы написать команду GC() или remove(object). Мониторинг в контрольном мониторе памяти никогда не кажется проблемой по сравнению с доступной оперативной памятью? Что происходит?

Я понимаю, что я должен найти лучший алгоритм, который будет менее интенсивным в памяти, но в любом случае это хороший повод узнать об этой проблеме и сравнить с другими людьми, которые решили проблему, время выполнения, если все пошло как и планировалось, не было совершенно смешно для первой (жестокой) попытки.

Вот исходный код

//////// 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 конфигурации это означает, что ваше приложение:

• не уверен оптимизация (что может увеличить использование памяти), чтобы обеспечить дополнительную информацию об отладке
• использует только 32-разрядные инструкции набора инструкций процессора x86, и из-за этого он не может использовать более 4 ГБ памяти (или le ss, depending on your OS)

Попробуйте изменить его на что-то вроде Release/x64 (*). Вы также можете настроить параметры встроенного Mono garbage collector.

Вы можете ожидать, что количество элементов, обработанных вашим алгоритмом, значительно уменьшится, если данные, используемые вашей программой, занимают большую часть памяти, доступной для процесса. В таком случае вы обычно тратите большую часть времени на сборку мусора (каждый GC может освобождать только небольшой объем памяти, потому что большинство объектов живы), и лишь часть времени делает «реальные» вычисления (а вычисления требуют выделения памяти, которые триггер GC).

Другое, что может быть полезно, когда вы изучаете использование памяти, является профилировщиком памяти.

Вы упомянули, что в R вы можете принудительно собрать мусор; в .NET вы также можете сделать это, вызвав GC.Collect(), однако в большинстве случаев его обескураживают (сбор мусора выполняется автоматически, когда это необходимо).

* Вам нужен компилятор, производящий 64-битные сборки и 64-разрядную версию Common Language Runtime для запуска вашего кода. 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-бит.