Dlaczego użycie && 75 razy szybciej niż gdyby ... fi i jak uczynić kod jaśniejszym

38

Mam następujący działający kod:

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"

Ten kod działa szybko i wynosi 0,194 sekundy. Jednak uważam, że && is_prime= falsejest trochę trudny do odczytania i może wyglądać (dla niewprawnego oka), jakby był testowany, a nie ustawiony, co robi. Próbowałem więc zmienić &&na if...theni to działa - ale jest 75 razy wolniejsze przy 14,48 sekundy. Jest to najbardziej zauważalne przy wyższych liczbach.

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"

Czy jest jakaś klarowność bloku bez powolności?

Aktualizacja (1/4/2015 10:40 EST)

Świetna opinia! Teraz używam następujących. Jakaś inna opinia ?

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
źródło
1
Z jednej strony uruchomienie skryptu powoduje wydrukowanie go Largest Prime= 100na moim komputerze.
Giulio Muscarello,
3
Również na marginesie, jeśli jesteś zainteresowany wydajnością, jednym trywialnym sposobem na poprawienie tego byłoby iterowanie do number_under_test/2zamiast zamiast do number_under_test-1: Żaden czynnik liczby n nie jest większy niż n / 2, więc nadal znajdziesz wszystko Czynniki dla liczb niepierwszych wykonując to. (Również jeśli chciałbyś tylko przetestować prymityw, wystarczy iterować do sqrt (n), ale Bash nie ma wbudowanej funkcji do obliczania pierwiastków kwadratowych.)
Malte Skoruppa
Matowy, dobry punkt (+1). Jedyną zmianą było to, że nie działało dla liczby 4, więc musiałem to zrobić, aby na to (number_under_test/2)+1pozwolić
Michael Durrant
1
W zaktualizowaną wersją, szelki {}nie są naprawdę potrzebne po thenklauzuli, ponieważ thenjuż służy jako operator grupującego (wraz z elif, elselub fi). W rzeczywistości w niektórych powłokach można pisać na przykład for i in 1 2 3; { echo $i; }bez dolub done.
Jonathan Leffler
1
+1 Jonathan, dokonałem tych zmian i zaktualizowałem aktualizację
Michael Durrant

Odpowiedzi:

66

Jest tak, ponieważ za każdym razem spawnujesz podpowłokę:

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

Po prostu usuń nawiasy

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

Jeśli chcesz pogrupować polecenia, w bieżącej powłoce jest dostępna składnia :

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

(wymagany jest średnik końcowy, patrz instrukcja )

Zauważ, że [ is_prime ]to nie to samo, co [ $is_prime == true ]: możesz napisać to tak prosto $is_prime(bez nawiasów), które wywołałoby wbudowane bash truelub falsepolecenie.
[ is_prime ]jest testem z jednym argumentem, ciągiem „is_prime” - gdy [podano pojedynczy argument, wynikiem jest sukces, jeśli argument nie jest pusty, a ten literalny ciąg jest zawsze niepusty, a zatem zawsze „prawda”.

Dla czytelności zmieniłbym bardzo długą linię

[ $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

do

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

Nie lekceważ białych znaków, aby poprawić przejrzystość.

Glenn Jackman
źródło
1
jest literówka - largest_prime=$number_under_testpowinien być w ówczesnej gałęzi (ten sam błąd jest w oryginale)
JJoao
1
Warto również zauważyć, że w bash, zsh i in. [Wywołują program dosłownie wywoływany [, podczas gdy [[jest implementowany w powłoce - stąd będzie on szybszy. Spróbuj time for ((i = 0; $i < 1000; i++)); do [ 1 ]; donei porównaj z [[. Zobacz to SO pytanie, aby uzyskać więcej informacji.
kirb
2
bash implementuje [, to jest wbudowane. W wierszu poleceń wpisz type -a [ihelp [
glenn jackman
@glennjackman Wow; nie byłam tego świadoma. Zakładałem, że nadal tak jest, ponieważ which [wciąż powraca /usr/bin/[. Właśnie zdałem sobie sprawę, że sugerowałem, że zsh jest taki sam; dla mnie to mówi mi, że to jest wbudowane. Ale potem ... dlaczego jest [[szybszy?
kirb
2
@glennjackman command -vto kolejna dobra whichalternatywa; patrz także tutaj .
Abbafei,
9

Myślę, że zbyt ciężko pracujesz nad tą funkcją. Rozważać:

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

Arytmetyka powłoki jest w stanie sama ocenić warunki całkowite. Rzadko wymaga zbyt wielu testów i / lub zadań zewnętrznych. Ta jedna whilepętla dość dobrze powiela zagnieżdżone pętle:

Nie drukuje się tak dużo, oczywiście, nie napisałem zbyt wiele, ale na przykład ustawiłem pułap na 16 zamiast 101, jak napisano powyżej i ...

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

To zdecydowanie działa. Przybliżenie wydajności wymaga bardzo niewiele więcej:

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

Po prostu robienie tego, a nie echo...

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

To działa w busybox. Jest bardzo przenośny, szybki i łatwy w użyciu.

Twój problem z podpowłoką wystąpi w większości powłok, ale jest zdecydowanie najbardziej dotkliwy w bashpowłoce. Na przemian robiłem

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

... i sposób, w jaki napisałem to powyżej w kilku powłokach dla pułapu 101 i dashzrobiłem to bez podpowłoki w 0,017 sekundy i z podpowłoką w 1,8 sekundy. busybox.149 i 2, zsh .149 i 4, bash.35 i 6, oraz ksh93w .149 i .160. ksh93nie rozwidla dla podpowłoki, tak jak inne powłoki. Więc może problemem jest nie tyle podpowłoka, ile powłoka .

mikeserv
źródło
Co jest zaletą [ "$((...))" -eq "$((...))" ]w ciągu (( (...) == (...) ))? Czy ten ostatni jest mniej przenośny?
ruakh
@ruakh - przenośność, szybkość, niezawodność. [ "$((...))" -eq "$((...)) ]działa w powłokach, których uruchomienie nie zajmuje 15 sekund, a druga nie. Jeśli przewaga jednego nad drugim jest w ogóle wątpliwa, może to dać przewagę tylko temu pierwszemu, co oznacza, że nigdy nie ma dobrego powodu, aby z niego korzystać (( (...) == (...) )).
mikeserv
Przepraszamy, ale twoja odpowiedź wydaje się zakładać, że mam już szczegółową wiedzę na temat obsługi powłoki (( ... )). Pochlebia mi, ale ja nie nie mieć tej szczegółowej wiedzy. (Pamiętaj, to ja właśnie zapytałem, czy (( ... ))jest mniej przenośny.) Tak więc naprawdę nie mogę zrozumieć twojej odpowiedzi. : - / Czy możesz być bardziej precyzyjny?
ruakh
@ruakh - Przepraszam ... Nie widziałem, że pytasz, czy jest bardziej przenośny, tylko jak to było korzystne - dlatego odpowiedziałem na przenośność. W każdym razie, "$((...))"jest określony przez POSIX, a drugi to rozszerzenie powłoki. Pociski POSIX są całkiem zdolne. Nawet dashi poshpoprawnie obsłuży testy gałęzi, takie jak "$((if_true ? (var=10) : (var=5) ))"i zawsze $varpoprawnie przypisuje . busyboxpęka tam - zawsze ewaluuje obie strony bez względu na $if_truewartość.
mikeserv
@ruakh - o rany. Muszę dziś trochę odpocząć ... mówi się, że ... czy ta ostatnia jest mniej przenośna ? Chyba nie widziałem tego wcześniej ...?
mikeserv