¿Por qué está usando && 75 veces más rápido que si ... fi y cómo aclarar el código?

38

Tengo el siguiente código de trabajo:

largest_prime=1
for number_under_test in {1..100}
do
  is_prime=true
  factors=''
  for ((divider = 2; divider < number_under_test-1; divider++));
  do
    remainder=$(($number_under_test % $divider))
    [ $remainder == 0 ] && [ is_prime ] && is_prime=false && factors+=$divider' '
  done
  [ $is_prime == true ] && echo "${number_under_test} is prime!" || echo "${number_under_test} is NOT prime (factors= $factors)"  [ $is_prime == true ] && largest_prime=$number_under_test
done
printf "\nLargest Prime= $largest_prime\n"

Este código se ejecuta rápidamente es 0.194 segundos. Sin embargo, me pareció && is_prime= falseun poco difícil de leer y podría parecer (a simple vista) como si estuviera siendo probado en lugar de estar configurado, que es lo que hace. Así que intenté cambiar el &&a an if...theny esto funciona, pero es 75 veces más lento a los 14.48 segundos. Es más notable en los números más altos.

largest_prime=1
for number_under_test in {1..100}
do
  is_prime=true
  factors=''
  for ((divider = 2; divider < number_under_test-1; divider++));
  do  
    remainder=$(($number_under_test % $divider))
    if ([ $remainder == 0 ] && [ $is_prime == true ]); then
      is_prime=false
      factors+=$divider' '
    fi  
  done
  [ $is_prime == true ] && echo "${number_under_test} is prime!" || echo "${number_under_test} is NOT prime (factors= $factors)"  [ $is_prime == true ] && largest_prime=$number_under_test
done  
printf "\nLargest Prime= $largest_prime\n"

¿Hay alguna para tener la claridad del bloque sin la lentitud?

Actualización (1/4/2015 10:40 am EST)

Gran respuesta! Ahora estoy usando lo siguiente. Algún otro comentario ?

largest_prime=1
separator=' '
for number_under_test in {1..100}; {
  is_prime=true
  factors=''
  for ((divider = 2; divider < (number_under_test/2)+1; divider++)) {
    remainder=$(($number_under_test % $divider))
    if [ $remainder == 0 ]; then
      is_prime=false
      factors+=$divider' '
    fi
  } 
  if $is_prime; then
    printf "\n${number_under_test} IS prime\n\n"
    largest_prime=$number_under_test
  else
    printf "${number_under_test} is NOT prime, factors are: "
    printf "$factors\n"
  fi
}
printf "\nLargest Prime= $largest_prime\n"
Michael Durrant
fuente
1
En una nota al margen, ejecutar su script imprime eso Largest Prime= 100en mi computadora.
Giulio Muscarello
3
También en una nota al margen, si está interesado en la eficiencia, una forma trivial de mejorar esto sería iterar solo en number_under_test/2lugar de hasta number_under_test-1: Ningún factor de un número n es mayor que n / 2, por lo que aún encontrará todos factores para números no primos al hacer esto. (Además, si solo estuvieras interesado en probar la primacía, sería suficiente iterar hasta sqrt (n), pero Bash no tiene una función incorporada para calcular raíces cuadradas de todos modos).
Malte Skoruppa
Mate, buen punto (+1). El único cambio fue que no funcionó para el número 4, así que tuve que hacerlo (number_under_test/2)+1para permitirlo
Michael Durrant
1
En su versión actualizada, los apoyos {}no son realmente necesarios después de la thencláusula porque el thenya sirve como operador de agrupación (junto con elif, elseo fi). De hecho, en algunos shells, podría escribir, por ejemplo, for i in 1 2 3; { echo $i; }con doo sin done.
Jonathan Leffler
1
+1 Jonathan, hice esos cambios y actualicé la actualización
Michael Durrant

Respuestas:

66

Eso es porque estás generando un sub-shell cada vez:

if ([ $remainder == 0 ] && [ $is_prime == true ]); then

Solo elimina los paréntesis

if [ $remainder == 0 ] && [ $is_prime == true ]; then

Si desea agrupar comandos, hay una sintaxis para hacerlo en el shell actual :

if { [ $remainder == 0 ] && [ $is_prime == true ]; }; then

(se requiere el punto y coma final, consulte el manual )

Tenga en cuenta que [ is_prime ]no es lo mismo que [ $is_prime == true ]: podría escribir eso simplemente $is_prime(sin corchetes) que invocaría el bash incorporado trueo el falsecomando.
[ is_prime ]es una prueba con un argumento, la cadena "is_prime": cuando [se le da un único argumento, el resultado es exitoso si el argumento no está vacío, y esa cadena literal siempre no está vacía, por lo tanto, siempre es "verdadera".

Para facilitar la lectura, cambiaría la línea muy larga

[ $is_prime == true ] && echo "${number_under_test} is prime!" || echo "${number_under_test} is NOT prime (factors= $factors)"  [ $is_prime == true ] && largest_prime=$number_under_test

a

if [ $is_prime == true ]; then
  echo "${number_under_test} is prime!"
else 
  echo "${number_under_test} is NOT prime (factors= $factors)"
  # removed extraneous [ $is_prime == true ] test that you probably
  # didn't notice off the edge of the screen
  largest_prime=$number_under_test
fi

No subestimes los espacios en blanco para mejorar la claridad.

Glenn Jackman
fuente
1
hay un largest_prime=$number_under_testerror
tipográfico
1
También vale la pena señalar que en bash, zsh, et al, [está invocando un programa llamado literalmente [, mientras que [[se implementa en el shell, por lo tanto, será más rápido. Intenta time for ((i = 0; $i < 1000; i++)); do [ 1 ]; doney compara con [[. Vea esta pregunta SO para más información.
kirb
2
bash implements [, es un incorporado. Desde un indicador de comandos de shell, escriba type -a [yhelp [
glenn jackman
@glennjackman Wow; No estaba al tanto de eso. Asumí que todavía era el caso porque which [todavía regresa /usr/bin/[. También me di cuenta de que implicaba que zsh era igual; para mí eso me dice que es una construcción. Pero entonces ... ¿por qué es [[más rápido?
kirb
2
@glennjackman command -ves otra buena whichalternativa; ver también aquí .
Abbafei
9

Creo que estás trabajando demasiado duro en esa función tuya. Considerar:

unset num div lprime; set -- "$((lprime=(num=(div=1))))"
while [     "$((     num += ! ( div *= ( div <= num   ) ) ))" -eq \
            "$((     num *=   ( div += 1 )   <= 101   ))" ]    && {
      set   "$(( ! ( num %      div )         * div   ))"     "$@"
      shift "$(( !    $1 +    ( $1 ==  1 )    *  $#   ))"
}; do [ "$div" -gt "$num" ] && echo "$*"      
done

La aritmética de Shell es bastante capaz de evaluar condiciones enteras por sí sola. Raramente necesita demasiadas pruebas y / o tareas externas. Este whilebucle duplica bastante bien tus bucles anidados:

No se imprime tanto, por supuesto, no escribí mucho, pero, por ejemplo, establecer el límite máximo en 16 en lugar de 101 como se escribe arriba y ...

2
3
4 2
5
6 3 2
7
8 4 2
9 3
10 5 2
11
12 6 4 3 2
13
14 7 2
15 5 3

Definitivamente está haciendo el trabajo. Y requiere muy poco más para aproximar su salida:

...
do [ "$div" -eq "$num" ] && shift &&
   printf "$num ${1+!}= prime.${1+\t%s\t%s}\n" \
          "factors= $*"                        \
          "lprime=$(( lprime = $# ? lprime : num ))"
done

Solo haciendo eso en lugar de la echoy ...

1 = prime.
2 = prime.
3 = prime.
4 != prime.     factors= 2      lprime=3
5 = prime.
6 != prime.     factors= 3 2    lprime=5
7 = prime.
8 != prime.     factors= 4 2    lprime=7
9 != prime.     factors= 3      lprime=7
10 != prime.    factors= 5 2    lprime=7
11 = prime.
12 != prime.    factors= 6 4 3 2        lprime=11
13 = prime.
14 != prime.    factors= 7 2    lprime=13
15 != prime.    factors= 5 3    lprime=13

Esto funciona busybox. Es muy portátil, rápido y fácil de usar.

Su problema de subshell va a ocurrir en la mayoría de los shells, pero es, con mucho , el más agudo en un bashshell. Alternaba entre hacer

( [ "$div" -gt "$num" ] ) && ...

... y la forma en que lo escribí arriba en varios shells para un techo de 101 y lo dashhice sin el subshell en .017 segundos y con el subshell en 1.8 segundos. busybox.149 y 2, zsh .149 y 4, bash.35 y 6, y ksh93en .149 y .160. ksh93no se bifurca para subcapas como deben hacerlo las otras cáscaras. Entonces, tal vez el problema no sea tanto el subshell como el shell .

mikeserv
fuente
¿Cuál es la ventaja de [ "$((...))" -eq "$((...))" ]más (( (...) == (...) ))? ¿Es este último menos portátil?
ruakh
@ruakh: portabilidad, velocidad, fiabilidad. [ "$((...))" -eq "$((...)) ]funciona en shells que no toman 15 segundos para ejecutar el programa, y ​​el otro no. Si la ventaja de uno sobre otro es cuestionable, entonces eso solo puede darle ventaja al primero, lo que significa que nunca hay una buena razón para usar (( (...) == (...) )).
mikeserv
Lo sentimos, pero su respuesta parece suponer que ya tengo un conocimiento detallado del soporte de shell para (( ... )). Estoy halagado, pero yo no tienen ese conocimiento detallado. (Recuerde, yo soy el que acaba de preguntar si (( ... ))es menos portátil). Así que realmente no puedo entender su respuesta. : - / ¿Podría ser un poco más explícito?
ruakh
@ruakh - Lo siento ... No vi que me preguntabas si era más portátil, solo cómo era ventajoso, por eso respondí sobre la portabilidad. De todos modos, el "$((...))"está especificado por POSIX y el otro es una extensión de shell. Los proyectiles POSIX son bastante capaces. Even dashy poshmanejará correctamente las pruebas de rama como "$((if_true ? (var=10) : (var=5) ))"y siempre se asignará $varcorrectamente. busyboxse rompe allí: siempre evalúa ambos lados independientemente del $if_truevalor de '.
mikeserv
@ruakh - oh hombre. Debo estar un poco apagado hoy ... dice ahí mismo ... ¿ Es este último menos portátil ? No vi eso antes, supongo ...
mikeserv