1votos

Carrera de "¡Baja la escalera!" en F#

por josejuan hace 4 años

Una traslación directa de la versión de Haskell arroja en F# unos rendimientos muy inferiores. Usando la misma máquina (8 cores) tarda 6 veces más de tiempo. Seguramente la paralelización con "Array.Parallel" no es la más eficiente para este tipo de paralelización (muchas pequeñas operaciones).

Una variante que convierte al popular juguete en una carrera de la que debes calcular las mejores rutas de los corredores.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
type Row = int array 
type Tree = Row list 
 
let row2row (a: Row) (b: Row) : Row = 
    let best (i: int) (c: int) : int = 
        let cL = b.[i] 
        let cR = b.[i + 1] 
        c + if cL <= cR then cL else cR 
    Array.Parallel.mapi best a 
 
let rec costsTree (t: Tree) : Row * Tree = 
        match t with 
        | x::[] -> (x, [x]) 
        | x::xs -> let (y, ys) = costsTree xs 
                   let z       = row2row x y 
                   (z, z::ys) 
 
let randomRow (rnd: System.Random) (w: int) : Row = Array.ofList <| List.map (fun _ -> rnd.Next(10)) [1 .. w] 
 
let randomTree (w: int) (r: int) : Tree = 
    let rnd = System.Random(1) 
    List.map (randomRow rnd) [w .. w + r] 
 
[<EntryPoint>] 
let main argv = 
    printfn "Generando árbol..." 
    let (w, r) = (System.Int32.Parse(argv.[0]), System.Int32.Parse(argv.[1])) 
    let tree = randomTree w r 
    printfn "Total rows: %A" (List.length tree) 
    printfn "Calculando rutas mínimas..." 
    let t0 = System.DateTime.UtcNow 
    let (s, _) = costsTree tree 
    let t1 = System.DateTime.UtcNow 
    printfn "%A" s 
    printfn "%A" ((t1 - t0).TotalSeconds) 
    0 // devolver un código de salida entero 
 
// Ejemplo de ejecución sobre la misma máquina y filas que la versión de Haskell 
// 
//      C:\DATOS_OFFLINE\tmp\testing\net45>downStairs.exe 2 22000 
//      Generando árbol... 
//      Total rows: 22001 
//      Calculando rutas mínimas... 
//      [|44557; 44557|] 
//      16.3488287 
// 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.