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.