La evaluación comparativa de su aplicación suele ser una buena idea cuando se trata de ajustar su rendimiento. El paquete de de contiene una función de evaluación comparativa que se puede utilizar para examinar el rendimiento de su código de . En este artículo, veremos cómo escribir pruebas comparativas simples que puedan brindarnos buenos conocimientos sobre una solución algorítmica determinada. prueba Golang Golang El buen viejo cálculo del número de Fibonacci es una serie numérica clásica donde cada número subsiguiente es la suma de los dos números anteriores: 1 1 2 3 5 8 13... El número de Fibonacci Exploremos dos implementaciones diferentes: recursiva y secuencial. Escribiremos pruebas unitarias y comparativas para cada enfoque y luego podremos compararlas. Enfoque recursivo Cuando observa el , parece ser muy sencillo de implementar en casi cualquier lenguaje de programación. Y probablemente el primer enfoque para resolverlo es usar : algoritmo de Fibonacci recursividad fibo { n <= { n } RecursiveFibonacci(n ) + RecursiveFibonacci(n ) } package func RecursiveFibonacci (n ) uint uint if 1 return return -1 -2 Cada iteración de la serie descarta los resultados anteriores y luego vuelve a calcular los pasos intermedios para cada iteración posterior. Agreguemos algunas pruebas unitarias: fibo { data := [] { n want }{ { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, } _, d := data { got := RecursiveFibonacci(dn); got != d.want { t.Errorf( , got, d.want) } } } package import "testing" func TestRecursiveFibonacci (t *testing.T) struct uint uint 0 0 1 1 2 1 3 2 4 3 5 5 6 8 10 55 42 267914296 for range if "got: %d, want: %d" Funciona: tiago:~/develop/ /fibonacci/fibo$ test -run TestRecursiveFibonacci PASS ok bitbucket.org/tiagoharris/fibonacci/fibo go go 1.875s Enfoque secuencial Esta implementación alternativa elimina la recursividad y en su lugar utiliza un bucle for simple y un par de variables. Si lo piensas bien, el algoritmo no es más que una suma de N números. Partimos de 0 y 1 e iremos sumando sumas sucesivas: fibo { n <= { (n) } n2, n1 = , i := ( ); i < n; i++ { n2, n1 = n1, n1+n2 } n2 + n1 } package func SequentialFibonacci (n ) uint uint if 1 return uint var uint 0 1 for uint 2 return Agreguemos algunas pruebas unitarias: { data := [] { n want }{ { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, } _, d := data { got := SequentialFibonacci(dn); got != d.want { t.Errorf( , got, d.want) } } } func TestSequentialFibonacci (t *testing.T) struct uint uint 0 0 1 1 2 1 3 2 4 3 5 5 6 8 10 55 42 267914296 for range if "got: %d, want: %d" También funciona: tiago:~/develop/ /fibonacci/fibo$ test -run TestSequentialFibonacci PASS ok bitbucket.org/tiagoharris/fibonacci/fibo go go 0.631s Tenga en cuenta que aquí tenemos una mejora considerable en el rendimiento; 0,631 s frente a 1,875 s. evaluación comparativa Para medir el rendimiento, podríamos medir el tiempo de ejecución y mostrarlo con algunas declaraciones de impresión, por supuesto. Pero ofrece una herramienta muy sofisticada para la evaluación comparativa y es bastante simple de usar. Golang Escribir un punto de referencia es muy similar a escribir una prueba, ya que comparten la infraestructura del paquete de prueba. Algunas de las diferencias clave son: Las funciones de Benchmark comienzan con ' ', no con ' '; Benchmark Test El paquete de prueba ejecuta varias veces las funciones de referencia. El valor de 'bN' aumentará cada vez hasta que el corredor de referencia esté satisfecho con la estabilidad de la referencia; Cada punto de referencia debe ejecutar el código bajo prueba bN veces. Por lo tanto, un bucle 'for' estará presente en cada función de referencia. Nuestro archivo final contendrá pruebas unitarias y comparativas: fibo_test.go fibo ( ) { i := ; i < bN; i++ { RecursiveFibonacci( ) } } { i := ; i < bN; i++ { RecursiveFibonacci( ) } } { i := ; i < bN; i++ { SequentialFibonacci( ) } } { i := ; i < bN; i++ { SequentialFibonacci( ) } } { data := [] { n want }{ { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, } _, d := data { got := RecursiveFibonacci(dn); got != d.want { t.Errorf( , got, d.want) } } } { data := [] { n want }{ { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, } _, d := data { got := SequentialFibonacci(dn); got != d.want { t.Errorf( , got, d.want) } } } package import "testing" func BenchmarkTestRecursiveFibonacci_10 (b *testing.B) for 0 10 func BenchmarkTestRecursiveFibonacci_20 (b *testing.B) for 0 20 func BenchmarkTestSequentialFibonacci_10 (b *testing.B) for 0 10 func BenchmarkTestSequentialFibonacci_20 (b *testing.B) for 0 20 func TestRecursiveFibonacci (t *testing.T) struct uint uint 0 0 1 1 2 1 3 2 4 3 5 5 6 8 10 55 42 267914296 for range if "got: %d, want: %d" func TestSequentialFibonacci (t *testing.T) struct uint uint 0 0 1 1 2 1 3 2 4 3 5 5 6 8 10 55 42 267914296 for range if "got: %d, want: %d" Compararemos los enfoques recursivo y secuencial calculando la secuencia para 10 y 20. Con las pruebas de referencia implementadas, todo lo que tenemos que hacer es invocarlas a través de "go test -bench=.". De forma predeterminada, se ejecuta utilizando todas las CPU disponibles. Puede cambiar así: "ir a prueba -cpu=4 -bench=.". Mi máquina tiene 8 CPU, como podemos ver ejecutando : htop Vamos a ejecutarlo: tiago:~/develop/ /fibonacci/fibo$ test -bench=. goos: darwin goarch: amd64 pkg: bitbucket.org/tiagoharris/fibonacci/fibo cpu: Intel(R) Core(TM) i7 HQ CPU @ GHz BenchmarkTestRecursiveFibonacci_10 ns/op BenchmarkTestRecursiveFibonacci_20 ns/op BenchmarkTestSequentialFibonacci_10 ns/op BenchmarkTestSequentialFibonacci_20 ns/op PASS ok bitbucket.org/tiagoharris/fibonacci/fibo go go -7820 2.90 -8 3534949 335.2 -8 28592 41587 -8 372993714 3.221 -8 193414836 6.175 8.406s El formato de salida es: Benchmark< -name>-<number-of-cpus> number of executions speed of each operation test Ahora podemos tener una mejor idea de cómo el enfoque secuencial es mucho más eficiente que el recursivo: se ejecutó 3.534,949 veces con una velocidad de 335,2 ns/op, mientras que se ejecutó 372.993,714 veces con una velocidad de 3,221 ns/op; BenchmarkTestRecursiveFibonacci10-8 BenchmarkTestSequentialFibonacci10-8 se ejecutó 28.592 veces con una velocidad de 41730 ns/op, mientras que se ejecutó 193.414,836 veces con una velocidad de 6,175 ns/op. BenchmarkTestRecursiveFibonacci20-8 BenchmarkTestSequentialFibonacci20-8 Trazado de gráficos Soy un gran fan de . Incluso he escrito un que muestra cómo puede ser útil. gnuplot artículo Este es el archivo que se usará para trazar un : gnuplot gráfico de caja terminal png grid output graphic_file_name title datafile separator key off ylabel y_label yrange[y_range_min:y_range_max] format y xtics rotate style fill solid boxwidth 0.5 plot [ =0:*] file_path every ::i::i using column_1:column_2:xtic(2) with boxes ## # gnuplot script to generate a performance graphic. # # it expects the following parameters: # # file_path - path to the file from which the data will be read # graphic_file_name - the graphic file name to be saved # y_label - the desired label for y axis # y_range_min - minimum range for values in y axis # y_range_max - maximum range for values in y axis # column_1 - the first column to be used in plot command # column_2 - the second column to be used in plot command # # Author: Tiago Melo (tiagoharris@gmail.com) ## # graphic will be saved as 800x600 png image file set # allows grid lines to be drawn on the plot set # setting the graphic file name to be saved set # the graphic's main title set "performance comparison" # since the input file is a CSV file, we need to tell gnuplot that data fields are separated by comma set "," # disable key box set # label for y axis set # range for values in y axis set # to avoid displaying large numbers in exponential format set "%.0f" # vertical label for x values set # set boxplots set set # plot graphic for each line of input file for i Este es el objetivo de en nuestro que ejecuta las pruebas de referencia y traza gráficos tanto para la cantidad de operaciones como para la velocidad de cada operación, para que podamos compararlas fácilmente: referencia Makefile benchmark: @ fibo ; \ go -bench=. | tee ../graphic/out.dat ; \ awk ../graphic/out.dat > ../graphic/final.dat ; \ gnuplot -e -e -e -e -e -e -e ../graphic/performance.gp ; \ gnuplot -e -e -e -e -e -e -e ../graphic/performance.gp ; \ rm -f ../graphic/out.dat ../graphic/final.dat ; \ cd test '/Benchmark/{count ++; gsub(/BenchmarkTest/,""); printf("%d,%s,%s,%s\n",count,$$1,$$2,$$3)}' "file_path='../graphic/final.dat'" "graphic_file_name='../graphic/operations.png'" "y_label='number of operations'" "y_range_min='000000000''" "y_range_max='400000000'" "column_1=1" "column_2=3" "file_path='../graphic/final.dat'" "graphic_file_name='../graphic/time_operations.png'" "y_label='each operation in nanoseconds'" "y_range_min='000''" "y_range_max='45000'" "column_1=1" "column_2=4" echo "'graphic/operations.png' and 'graphic/time_operations.png' graphics were generated." Primero, ejecuta las pruebas de referencia utilizando un con el comando , lo que hace posible mostrar la salida en la terminal y guardarla en un archivo. tubo tee Luego, usamos el comando para analizar nuestro archivo en un formato que se usará para trazar los gráficos. Se parece a esto: awk CSV ,RecursiveFibonacci_10 , , ,RecursiveFibonacci_20 , , ,SequentialFibonacci_10 , , ,SequentialFibonacci_20 , , 1 -8 3579872 334.3 2 -8 29028 42352 3 -8 375031484 3.238 4 -8 195996889 6.148 A continuación, llamamos a dos veces: 1) genera un gráfico para el número de ejecuciones 2) genera un gráfico para la velocidad de cada operación. gnuplot Vamos a ejecutarlo: tiago:~/develop/go/fibonacci$ make benchmark goos: darwin goarch: amd64 pkg: bitbucket.org/tiagoharris/fibonacci/fibo cpu: Intel(R) Core(TM) i7-7820HQ CPU @ 2.90GHz BenchmarkTestRecursiveFibonacci_10-8 3579872 334.3 ns/op BenchmarkTestRecursiveFibonacci_20-8 29028 42352 ns/op BenchmarkTestSequentialFibonacci_10-8 375031484 3.238 ns/op BenchmarkTestSequentialFibonacci_20-8 195996889 6.148 ns/op PASS ok bitbucket.org/tiagoharris/fibonacci/fibo 8.844s and graphics were generated. 'graphic/operations.png' 'graphic/time_operations.png' Impresionante. Número de operaciones: Velocidad de cada operación: Bastante genial, ¿no? Bonificación: cálculo de grandes números de Fibonacci La primera idea que me viene a la mente sería usar una variable entera de 128 bits. Desafortunadamente, Go no tiene uno (todavía). Pero incluso entonces, hay uno de los números de que no cabe en un entero de 128 bits y necesitaríamos un entero de 256 bits y así sucesivamente. Afortunadamente, Go tiene un paquete llamado y su tipo que será muy útil en esta implementación: Fibonacci math/big Int { n <= { big.NewInt( (n)) } n2, n1 = big.NewInt( ), big.NewInt( ) i := ( ); i < n; i++ { n2.Add(n2, n1) n1, n2 = n2, n1 } n1 } * . func SequentialFibonacciBig (n ) uint big Int if 1 return int64 var 0 1 for uint 1 return Para probarlo, aquí está nuestro que acepta el número deseado como parámetro: main.go main ( ) { n flag.Uint64Var(&n, , , ) flag.Parse() fmt.Printf( , n, fibo.SequentialFibonacciBig( (n))) } package import "flag" "fmt" "bitbucket.org/tiagoharris/fibonacci/fibo" func main () var uint64 "n" 0 "n" "%d: %d\n" uint Y aquí está nuestro objetivo en para ejecutarlo: Makefile @ go build -a -installsuffix cgo -o main . @ if [ -z ]; then echo >&2 please set the number via the variable N; exit 2; fi ## build: build app's binary build: ## run: run the app run: build " " $(N) Vamos a ejecutarlo por, digamos, 200: tiago:~/develop/go/fibonacci$ make run N=200 200: 280571172992510140037611932413038677189525 Conclusión En este artículo, aprendimos cómo usar la utilidad de referencia de de y cómo usar para trazar gráficos para una mejor comparación. prueba Golang gnuplot Descarga la fuente Aquí: https://bitbucket.org/tiagoharris/fibonacci/src/master/