f# - studio - superponer graficas en r

¿Por qué reducir es más rápido que la suma o la suma?

Question

Mi compañero de trabajo y yo estábamos comparando la velocidad de las funciones C # al pasar en lambdas para hacer el trabajo en comparación con las funciones inline con respecto al tiempo dedicado a trabajar. Descubrimos que incurrió en un costo al pasar una proyección lambda a una función de selección de C # (por ejemplo) y quería ver si F # tenía los mismos problemas o si hacía algo diferente.

Independientemente de nuestro propósito original, tropezamos con algo que no podemos entender. En el siguiente ejemplo, sumamos una lista de 3 formas diferentes

1. Reducir
2. Suma
3. SumBy

module fs

open NUnit.Framework
open FsUnit
open System
open System.Diagnostics;

[<Test>]
let sumTest() = 
    let nums = [0..1000]

    let repeat = 100000

    let stopWatch = new Stopwatch()

    stopWatch.Start()

    let sumsReduce = 
        [
            for i in [0..repeat] do
                yield List.reduce (+) nums
        ]

    Console.WriteLine("reduce = {0} - Time = {1}", List.head sumsReduce, stopWatch.Elapsed.TotalSeconds); 
    stopWatch.Restart()

    let sumsSum = 
        [
            for i in [0..repeat] do
                yield List.sum nums
        ]

    Console.WriteLine("sum = {0} - Time = {1}", List.head sumsSum, stopWatch.Elapsed.TotalSeconds); 
    stopWatch.Restart()


    let sumsSumBy = 
        [
            for i in [0..repeat] do
                yield List.sumBy id nums
        ]

    Console.WriteLine("sumBy = {0} - Time = {1}", List.head sumsSumBy, stopWatch.Elapsed.TotalSeconds); 
    stopWatch.Restart()

La salida a esto se ve así:

reduce = 500500 - Time = 0.2725156
sum = 500500 - Time = 1.1183165
sumBy = 500500 - Time = 1.1126781

Entonces, reducir claramente es el gran ganador aquí. En la descompilación, puedo ver que reduce se reduce

[Serializable]
internal class sumsReduce/u004021/u002D1 : OptimizedClosures.FSharpFunc<int, int, int>
{
  internal sumsReduce/u004021/u002D1()
  {
    base./u002Ector();
  }

  public override int Invoke(int x, int y)
  {
    return x + y;
  }
}

Pero me está costando averiguar qué suma y qué suma están haciendo. ¿De dónde es la discrepancia de tiempo?

La respuesta actual sugiere que reducir es 5 veces más rápido porque originalmente estaba dando reducir un operador no verificado. Sin embargo, actualizar la prueba para usar un operador verificado (desde el módulo Checked ) y todavía obtengo el mismo resultado

let sumsReduce = 
        [
            for i in [0..repeat] do
                yield List.reduce (Checked.(+)) nums
        ]

Observe que la discrepancia de tiempo todavía existe

reduce = 500500 - Time = 0.274697
sum = 500500 - Time = 1.1126796
sumBy = 500500 - Time = 1.1370642

Answer 1

Sum y SumBy usan un enumerador:

    while e.MoveNext() do
        acc <- Checked.(+) acc e.Current
    acc

mientras que reduce usa un bucle recursivo con un cierre optimizado: (reducir usos se pliega debajo de la tapa - pliegue la cola de la cabeza )

    let fold<''T,''State> f (s:''State) (list: ''T list) = 
        match list with 
        | [] -> s
        | _ -> 
            let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
            let rec loop s xs = 
                match xs with 
                | [] -> s
                | h::t -> loop (f.Invoke(s,h)) t
            loop s list

El uso de cierres optimizados a menudo puede generar un aumento del rendimiento.

Answer 2

sum y sumBy usan la aritmética controlada, pero está pasando el operador sin sumBy + para reduce , no exactamente manzanas a manzanas.