Punto de referencia de números perfectos -- go campo con benchmarking camp codereview Relacionados El problema

Benchmark of Perfect Numbers


2
vote

problema

Español

Escribí una pieza de código para comparar la detección de números perfectos hasta 10000. El código original está aquí, en C:

  #include <stdio.h>  int isPerfectNumber(int num) {     if (num == 1) { return 0; }      int i, c = num - 1;     for (i = 2; i <= num / 2; ++i) {         if (num % i == 0) { c -= i; }     }      return c == 0; }  int main(int argc, char* argv[]) {     int i;     for (i = 0; i < 10000; ++i) {         if (isPerfectNumber(i)) {             printf("%d ", i);         }     }     return 0; }   

Luego escribí el mismo código en varios idiomas diferentes (C, C #, Java, V8 JavaScript, Python y Go).

Después de la evaluación comparativa, obtuve los siguientes resultados:

  • C: 92.8 MS
  • C #: 97.9 MS
  • Ir: 208.85 ms
  • java: 130.65 ms
  • v8 javascript: 279.15 ms
  • Python: 1126.35 MS

Esperaba bastante exactamente este patrón de más rápido para más lento, excepto para ir . ¿Por qué mi implementación es tan lenta? Admito que sé muy poco acerca de la oportunidad, pero estaba bajo la impresión de que, dado que es un lenguaje compilado, es probable que sea tan rápido como lo fue al menos C #.

Aquí está mi implementación de Go:

  package main  import "fmt"  func main() {     for i := 0; i < 10000; i++ {         if (isPerfectNumber(i)) {             fmt.Println(i)         }     } }  func isPerfectNumber(num int) bool {     if num == 1 { return false }      c := num - 1     for i := 2; i <= num / 2; i++ {         if num % i == 0 { c -= i }     }      return c == 0 }   

¿Acabo de encontrar algo o son los resultados? ¿Estoy viendo precisa?

FYI: I Benchmark ejecutando el código 10 veces sin sincronizarlo, luego ejecutar otras 20 veces y tomar el promedio de esas 20 pruebas.

Original en ingles

I wrote a piece of code to benchmark the detection of perfect numbers up to 10000. The original code is here, in C:

#include <stdio.h>  int isPerfectNumber(int num) {     if (num == 1) { return 0; }      int i, c = num - 1;     for (i = 2; i <= num / 2; ++i) {         if (num % i == 0) { c -= i; }     }      return c == 0; }  int main(int argc, char* argv[]) {     int i;     for (i = 0; i < 10000; ++i) {         if (isPerfectNumber(i)) {             printf("%d\n", i);         }     }     return 0; } 

I then wrote the same code in a number of different languages (C, C#, Java, V8 Javascript, Python and Go).

After benchmarking, I got the following results:

  • C: 92.8 ms
  • C#: 97.9 ms
  • Go: 208.85 ms
  • Java: 130.65 ms
  • V8 Javascript: 279.15 ms
  • Python: 1126.35 ms

I expected pretty much exactly this pattern of fastest to slowest, except for Go. Why is my Go implementation so slow? I admit I know very little about Go but I was under the impression that since it is a compiled language it is likely to be as fast as at least C# was.

Here is my Go implementation:

package main  import "fmt"  func main() {     for i := 0; i < 10000; i++ {         if (isPerfectNumber(i)) {             fmt.Println(i)         }     } }  func isPerfectNumber(num int) bool {     if num == 1 { return false }      c := num - 1     for i := 2; i <= num / 2; i++ {         if num % i == 0 { c -= i }     }      return c == 0 } 

Have I just mucked something up or are the results I am seeing accurate?

FYI: I benchmark by running the code 10 times without timing it, then running another 20 times and take the average of those 20 tests.

     
 
 

Lista de respuestas

3
 
vote
vote
La mejor respuesta
 

He golpeado el número a System.out.println(whichFloor(37)); 3 y perfilado. Parece que la operación de Modulo es la más cara aquí:

  System.out.println(whichFloor(37)); 4  

Parece que los compiladores C pueden optimizar el módulo aquí, mientras que el compilador Go no puede. Sugeriría abrir un problema al respecto en The Go Bug Tracker . Si C puede hacer eso, vaya también.

 

I've bumped the number to 100000 and profiled. It seems that modulo operation is the most expensive here:

ROUTINE ======================== main.isPerfectNumber in /tmp/so/main.go     31.72s     31.72s (flat, cum)   100% of Total          .          .     19:   if num == 1 {          .          .     20:       return false          .          .     21:   }          .          .     22:          .          .     23:   c := num - 1      2.35s      2.35s     24:   for i := 2; i <= num/2; i++ {     29.37s     29.37s     25:       if num%i == 0 {          .          .     26:           c -= i          .          .     27:       }          .          .     28:   }          .          .     29:          .          .     30:   return c == 0 

It seems that C compilers are able to optimize modulo here, while the Go compiler cannot. I'd suggest opening an issue about it on the Go bug tracker. If C can do that, Go should as well.

 
 
3
 
vote

Tomé tu código y jugué con él un poco ... y me di cuenta de un par de cosas:

  1. No estás buscando una revisión de código, pero tratando de averiguar por qué el código IR es más lento de lo esperado.
  2. No hay respuesta que lo satisfaga más que la respuesta de AINAR-G: https://codereview.stackexchange.com/ A / 155256/31503 .... Pero, este sitio es revisión del código, y pensé que revisaría el código (aunque eso no es lo que está solicitando específicamente).

primero, mientras que su código no es horrible, hay algunas mejoras que se realizarán:

  • Utilice bloques de declaración de múltiples líneas. Código como:

      if num == 1 { return false }   

    debe ser:

      if num == 1 {     return false }   
  • Utilice un mejor nombre de variable para c . Me doy cuenta de que está copiando el código de un programa C, pero esa es una variable simple para cambiar el nombre de algo como difference . Encontré el c particularmente difícil de averiguar, no es obvio cuál es el 9988776655544335 , o cómo se utiliza el 9988777655544336 . Tuve que caminar por el código para identificar su propósito. (Estoy seguro de que creerá que es obvio, pero recuerde que ha estado mirando el código por mucho más tiempo).

  • La validación de entrada debe devolver false Para todos los valores Menos de 2 , no solo 9988776655544339 . Su cheque if num == 1 { return false } 0 debe ser if num == 1 { return false } 1

Ahora, sobre ese algoritmo ... de nuevo, me doy cuenta de que usted está comparando el mismo algoritmo en diferentes idiomas, pero hay algunas optimizaciones básicas que puede hacer, algunas más significativas que otras:

  • Uso if num == 1 { return false } 2 en lugar de if num == 1 { return false } 3 para el cheque de restricción de bucle (0,4% Ahorro)
  • calcular if num == 1 { return false } 4 solo una vez. No hay necesidad de calcularlo en cada bucle. Esto ahorró el 0,2% del tiempo para mí.
  • Abandonar el bucle cuando if num == 1 { return false } 5 va negativo (es decir, los factores se suman a más del valor de entrada) (ahorro de 0.6%)
  • Uso de división y amplificador; multiplicación en lugar de modulo (gracias ainar-g) ...e.e. En lugar de if num == 1 { return false } 6 Uso if num == 1 { return false } 7 - muy poco 0.0% ...

Ninguna de estas optimizaciones hará suficiente diferencia en su evaluación del rendimiento de GoN relativo a otros idiomas, aunque.

Las optimizaciones más grandes deben ser más inteligentes sobre lo que hace con la información en varios puntos. Específicamente, cada factor de un número tiene un compañero (a menos que el factor sea la raíz cuadrada exacta del valor). Al informar el socio superior al mismo tiempo que descubrir el factor inferior, puede limitar el espacio de búsqueda a la raíz cuadrada del valor. Esto ahorra mucho cálculo.

Por ejemplo, este código:

  if num == 1 {     return false } 8  

Este es el más rápido, obtuve el código sin también entrar en la factorización principal (que es la siguiente etapa del proceso, para el registro).

¿Cuánto más rápido es la función anterior (en comparación con su método)? & gt; 50 veces más rápido.

Otro comentario, viene con un poderoso sistema de evaluación comparativa que también está integrado en el sistema de arnés de prueba. Cuando hago referencia varias versiones del código, obtengo los resultados:

  if num == 1 {     return false } 9  

Los resultados anteriores se basan en las siguientes implementaciones de su función (en el mismo orden anterior):

  c0  

Los casos de prueba y los puntos de referencia para los anteriores se construyen como:

  c1  
 

I took your code and played with it a bit... and realized a couple of things:

  1. You're not really looking for a code review, but trying to find out why the Go code is slower than expected.
  2. There's no answer that will satisfy you any more than Ainar-G's answer: https://codereview.stackexchange.com/a/155256/31503 .... but, this site is Code Review, and I figured I would review the code (even though that's not what you're specifically asking for).

First up, while your code is not horrible, there are some improvements to be made:

  • Use multi-line statement blocks. Code like :

    if num == 1 { return false } 

    should be:

    if num == 1 {     return false } 
  • Use better variable name for c. I realize that you're copying the code from a C program, but that's a simple variable to rename to something like difference. I found the c particularly hard to figure out, it's not obvious what the c is short for, or how the c is even used. I had to walk through the code to identify its purpose. (I am sure that you'll think that it's obvious, but remember you've been looking at the code for a lot longer).

  • input validation should return false for all values less than 2, not just 1. Your check if num == 1 should be if num <= 1

Now, about that algorithm... again, I realize that you are comparing the same algorithm in different languages, but there are some basic optimizations you can do, some more significant than others:

  • use num >> 1 instead of num / 2 for the loop constraint check (0.4% saving)
  • compute num/2 just once. No need to compute it in each loop. This saved 0.2% of the time for me.
  • abandon the loop when c goes negative (i.e. the factors add up to more than the input value) (0.6% saving)
  • use division&multiplication instead of modulo (thanks Ainar-G).. i.e. instead of num%i == 0 use q := num / i; if q * i == num .... - very little 0.0%...

None of these optimizations will make enough difference in your evaluation of Go performance relative to other languages, though.

The bigger optimizations are to be smarter about what you do with the information at various points. Specifically, each factor of a number has a partner (unless the factor is the exact square-root of the value). By computing the upper partner at the same time as discovering the lower factor, you can limit the search space to the square-root of the value. This saves a lot of computation.

For example, this code:

func isPerfectRoot(num int) (b bool) {     if num <= 1 {         return     }     difference := num - 1     for fact := 2; difference >= 0 && fact*fact <= num; fact++ {         quotient := num / fact         if quotient*fact == num {             // fact is an actual factor with partner `quotient`             difference -= fact             if quotient != fact {                 // not a square root                 difference -= quotient             }         }     }     return difference == 0 } 

This is the fastest I got the code going without also getting in to prime factorization (which is the next step of the process, for the record).

How much faster is the above function (compared to your method)? >50 times faster.

One other comment, Go comes with a powerful benchmarking system that's built in to the test harness system too. When I benchmark various versions of the code I get the results:

rolf@rolftp:~/go/src/perfect$ go test -bench . ./... BenchmarkPerfect/Perfect-OP-8                        5     261767255 ns/op BenchmarkPerfect/Perfect-Clean-8                     5     253655127 ns/op BenchmarkPerfect/Perfect-OneDiv-8                    5     249030400 ns/op BenchmarkPerfect/Perfect-NegOut-8                    5     237762650 ns/op BenchmarkPerfect/Perfect-NoMod-8                     5     236858595 ns/op BenchmarkPerfect/Perfect-Root-8                    300       4805556 ns/op BenchmarkPerfect/Perfect-RootOne-8                 300       4805588 ns/op PASS ok    perfect 20.553s 

The above results are based on the following implementations of your function (in the same order as above):

package main  import ()  func isPerfectNumber(num int) bool {     if num == 1 {         return false     }      c := num - 1     for i := 2; i <= num/2; i++ {         if num%i == 0 {             c -= i         }     }      return c == 0 }  func isPerfectClean(num int) (b bool) {     if num <= 1 {         return     }     difference := num - 1     for i := 2; i <= num>>1; i++ {         if num%i == 0 {             difference -= i         }     }     return difference == 0 }  func isPerfectOneDiv(num int) (b bool) {     if num <= 1 {         return     }     difference := num - 1     limit := num / 2     for i := 2; i <= limit; i++ {         if num%i == 0 {             difference -= i         }     }     return difference == 0 }  func isPerfectNegOut(num int) (b bool) {     if num <= 1 {         return     }     difference := num - 1     limit := num / 2     for i := 2; difference >= 0 && i <= limit; i++ {         if num%i == 0 {             difference -= i         }     }     return difference == 0 }  func isPerfectNoMod(num int) (b bool) {     if num <= 1 {         return     }     difference := num - 1     limit := num / 2     for i := 2; difference >= 0 && i <= limit; i++ {         quot := num / i         if quot*i == num {             difference -= i         }     }     return difference == 0 }  func isPerfectRoot(num int) (b bool) {     if num <= 1 {         return     }     difference := num - 1     for fact := 2; difference >= 0 && fact*fact <= num; fact++ {         quotient := num / fact         if quotient*fact == num {             // fact is an actual factor with partner `quotient`             difference -= fact             if quotient != fact {                 // not a square root                 difference -= quotient             }         }     }     return difference == 0 }  func isPerfectRootOne(num int) (b bool) {     if num == 1 {         return     }     difference := num - 1     for fact := 2; difference >= 0 && fact*fact <= num; fact++ {         quot := num / fact         if quot*fact == num {             difference -= fact             if quot != fact {                 // not a square root                 difference -= quot             }         }     }     return difference == 0 } 

The test cases and benchmarks for the above are built like:

package main  import (     "fmt"     "testing" )  var perfects = []int{6, 28, 496, 8128}  var perfectFns = map[string](func(int) bool){     "OP":      isPerfectNumber,     "Clean":   isPerfectClean,     "OneDiv":  isPerfectOneDiv,     "NegOut":  isPerfectNegOut,     "NoMod":   isPerfectNoMod,     "Root":    isPerfectRoot,     "RootOne": isPerfectRootOne, }  func isP(i int) bool {     for _, p := range perfects {         if i == p {             return true         }     }     return false }  func testFn(fn func(int) bool) error {     for i := 1; i < 10000; i++ {         p := fn(i)         x := isP(i)         if p != x {             return fmt.Errorf("Expected value %v to be perfect: %v but it came back as perfect: %v", i, x, p)         }     }     return nil }  func TestPerfect(t *testing.T) {     for n, fn := range perfectFns {         if err := testFn(fn); err != nil {             t.Errorf("Error in perfect %v: %v", n, err)         }     } }  func runFn(fn func(int) bool) int {     cnt := 0     for i := 1; i < 10000; i++ {         if fn(i) {             cnt++         }     }     return cnt }  func BenchmarkPerfect(b *testing.B) {     for n, fn := range perfectFns {         b.Run("Perfect-"+n, func(b *testing.B) {             for i := 0; i <= b.N; i++ {                 runFn(fn)             }         })     } } 
 
 

Relacionados problema

8  Un puerto de un simple registrador  ( A port of a simple logger ) 
Estoy mirando por altar un simple registrador que escribí un rato en Python a un idioma que resultaría en menos tiempo de tiempo de ejecución desde el registr...

3  Std :: String :: Longitud vs Strlen usando Google Benchmark  ( Stdstringlength vs strlen using google benchmark ) 
Escribí mi primer punto de referencia usando Google Benchmark para verificar lo que es más rápido entre el uso de std::string::length y strlen44 para calc...

2  Variaciones de la función de evaluación comparativa  ( Benchmarking function variations ) 
Estoy tratando de hacer referencia a dos variaciones de una de mis funciones. Es decir, estas funciones son para mostrar valores enteros en la línea de comand...

3  Solicitudes HTTP de Golang  ( Golang http requests ) 
Estoy empezando a aprender sobre Golang y me gustaría tener algún consejo sobre el siguiente programa. package main import ( "fmt" "net/http" ...

14  Biblioteca simple de micro-evaluación  ( Simple micro benchmarking library ) 
Estoy trabajando en una simple biblioteca de micro-evaluación en Java. Esta biblioteca facilita el punto de referencia múltiples implementaciones de referen...

3  Un punto de referencia de tiempo de ejecución para múltiples programas utilizando el módulo de subproceso de Python  ( A runtime benchmark for multiple programs using the python subprocess module ) 
Me gustaría comentarios sobre mi script de referencia, para usar en Linux. ¿Qué es otro método para la evaluación comparativa que podría ser mejor / más fácil...

4  Medir el tiempo de ejecución de algoritmos de clasificación  ( Measure execution time of sorting algorithms ) 
Tengo que medir el tiempo de ejecución de ciertos algoritmos de clasificación que se aprueba como funciones en el siguiente programa. Tampoco tengo que medirl...

11  Marco de micro-referencia  ( Micro benchmark framework ) 
Pequeñas funciones de evaluación comparativa en Java es notoriamente difícil, y hay una serie de herramientas para ayudar (calibrador, otros). Esas otras herr...

4  Helper Utilities para una evaluación comparativa más fácil en C  ( Helper utilities for easier benchmarking in c ) 
Tengo esta pequeña biblioteca para medir el tiempo de ejecución en milisegundos y devolver la duración más el resultado: execres.h X4 execres.c ...

11  Escáner en Scala  ( Scanner in scala ) 
que quería implementar 'código> 99887766555443333 / Código> en Scala. El objetivo de esta clase es: implementar una interfaz de colección SCALA (probable...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos