Mengapa menggunakan && 75 kali lebih cepat daripada jika ... dan bagaimana membuat kode menjadi lebih jelas

38

Saya memiliki kode kerja berikut:

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"

Kode ini berjalan cepat adalah 0,194 detik. Namun saya menemukan && is_prime= falsesedikit sulit untuk dibaca dan itu bisa terlihat (dengan mata yang tidak terlatih) seolah-olah sedang diuji daripada ditetapkan yang memang demikian. Jadi saya mencoba mengubah &&menjadi if...thendan ini berhasil - tetapi 75 kali lebih lambat pada 14,48 detik. Ini paling terlihat pada angka yang lebih tinggi.

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"

Apakah ada kejelasan blok tanpa kelambatan?

Pembaruan (1/4/2015 10:40 pagi EST)

Umpan balik yang bagus! Saya sekarang menggunakan yang berikut ini. Ada tanggapan lain?

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"
shell shell-script Michael Durrant
sumber
1
Pada sidenote, menjalankan skrip Anda akan mencetaknya Largest Prime= 100di komputer saya.
Giulio Muscarello
3
Juga pada sidenote, jika Anda tertarik pada efisiensi, satu cara sepele untuk meningkatkan ini adalah dengan hanya beralih ke number_under_test/2alih-alih hingga number_under_test-1: Tidak ada faktor angka n lebih besar dari n / 2, sehingga Anda masih akan menemukan semua faktor untuk bilangan non-prima dengan melakukan ini. (Juga jika Anda hanya tertarik untuk menguji primeness, itu akan cukup untuk beralih ke sqrt (n), tetapi Bash tetap memiliki fungsi
bawaan
Matte, poin bagus (+1). Satu-satunya perubahan adalah itu tidak berhasil untuk nomor 4 jadi saya harus membuatnya (number_under_test/2)+1untuk memungkinkan
Michael Durrant
1
Dalam versi diperbarui Anda, kawat gigi {}tidak benar-benar diperlukan setelah thenklausa karena thensudah berfungsi sebagai operator pengelompokan (bersama dengan elif, elseatau fi). Bahkan, dalam beberapa shell, Anda dapat menulis, misalnya, for i in 1 2 3; { echo $i; }tanpa doatau done.
Jonathan Leffler
1
+1 Jonathan, saya membuat perubahan itu dan memperbarui pembaruan
Michael Durrant

Jawaban:

66

Itu karena Anda menghasilkan sub-shell setiap kali:

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

Hapus saja tanda kurung

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

Jika Anda ingin mengelompokkan perintah, ada sintaks untuk melakukannya di shell saat ini :

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

(tanda titik koma diperlukan, lihat manual )

Catatan yang [ is_prime ]tidak sama dengan [ $is_prime == true ]: Anda bisa menulisnya secara sederhana $is_prime(tanpa tanda kurung) yang akan memanggil bash built-in trueatau falseperintah.
[ is_prime ]adalah tes dengan satu argumen, string "is_prime" - ketika [diberikan argumen tunggal, hasilnya berhasil jika argumen tidak kosong, dan string literal selalu tidak kosong, maka selalu "benar".

Untuk keterbacaan, saya akan mengubah baris yang sangat panjang

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

untuk

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

Jangan meremehkan spasi putih untuk meningkatkan kejelasan.

glenn jackman
sumber
1
ada salah ketik - largest_prime=$number_under_testharus di cabang saat itu (kesalahan yang sama ada di aslinya)
JJoao
1
Perlu juga dicatat bahwa dalam bash, zsh, et al, [menjalankan program yang secara harfiah disebut [, sedangkan [[diimplementasikan dalam shell - maka itu akan lebih cepat. Coba time for ((i = 0; $i < 1000; i++)); do [ 1 ]; donedan bandingkan [[. Lihat pertanyaan SO ini untuk info lebih lanjut.
kirb
2
implementasi bash [, itu builtin. Dari prompt shell, ketik type -a [danhelp [
glenn jackman
@glennjackman Wow; tidak menyadarinya. Saya berasumsi itu masih terjadi karena which [masih kembali /usr/bin/[. Saya juga baru menyadari bahwa saya menyiratkan zsh adalah sama; bagi saya yang mengatakan itu adalah builtin. Tetapi kemudian ... mengapa [[lebih cepat?
kirb
2
@glennjackman command -vadalah whichalternatif lain yang bagus ; lihat juga di sini .
Abbafei
9

Saya pikir Anda bekerja terlalu keras pada fungsi Anda itu. Mempertimbangkan:

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

Aritmatika shell cukup mampu mengevaluasi kondisi bilangan bulat sendiri. Jarang membutuhkan terlalu banyak tes dan / atau tugas luar. Satu whileloop ini menduplikasi loop bersarang dengan cukup baik:

Itu tidak banyak mencetak, tentu saja, saya tidak menulis terlalu banyak, tetapi, misalnya mengatur langit-langit menjadi 16 daripada 101 seperti yang tertulis di atas dan ...

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

Pasti melakukan pekerjaan. Dan sangat sedikit yang dibutuhkan untuk memperkirakan output Anda:

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

Hanya melakukan itu daripada 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

Ini berfungsi di busybox. Ini sangat portabel, cepat, dan mudah digunakan.

Masalah subkulit Anda akan terjadi di sebagian besar shell, tetapi, sejauh ini , paling akut di bashshell. Saya bergantian antara melakukan 

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

... dan cara saya menulisnya di atas dalam beberapa kerang untuk langit-langit 101 dan dashmelakukannya tanpa subkulit dalam 0,017 detik dan dengan subkulit dalam 1,8 detik. busybox.149 dan 2, zsh .149 dan 4, bash.35 dan 6, dan ksh93dalam .149 dan .160. ksh93tidak membayar untuk subkulit seperti kulit kerang lainnya. Jadi mungkin masalahnya tidak terlalu banyak subshell seperti shell .

mikeserv
sumber
Apa keuntungan dari [ "$((...))" -eq "$((...))" ]atas (( (...) == (...) ))? Apakah yang terakhir kurang portabel?
ruakh
@ruakh - portabilitas, kecepatan, keandalan. [ "$((...))" -eq "$((...)) ]bekerja dalam shell yang tidak membutuhkan waktu 15 detik untuk menjalankan program, dan yang lainnya tidak. Jika keuntungan satu sama lain dipertanyakan sama sekali, maka itu hanya dapat memberikan keunggulan bagi yang pertama, yang berarti tidak pernah ada alasan yang baik untuk menggunakannya (( (...) == (...) )).
mikeserv
Maaf, tetapi balasan Anda tampaknya menganggap bahwa saya sudah memiliki pengetahuan terperinci tentang dukungan shell untuk (( ... )). Aku tersanjung, tapi saya tidak tidak memiliki pengetahuan rinci. (Ingat, akulah yang baru saja bertanya apakah (( ... ))itu kurang portabel.) Jadi aku benar-benar tidak masuk akal dengan balasanmu. : - / Bisakah Anda menjadi sedikit lebih eksplisit?
ruakh
@ruakh - Saya minta maaf ... Saya tidak melihat bahwa Anda bertanya apakah itu lebih portabel, hanya bagaimana itu menguntungkan - itulah sebabnya saya menjawab tentang portabilitas. Bagaimanapun, "$((...))"ini POSIX-ditentukan dan yang lainnya adalah ekstensi shell. Kerang POSIX cukup mampu. Bahkan dashdan poshdengan benar akan menangani tes cabang seperti "$((if_true ? (var=10) : (var=5) ))"dan selalu menetapkan $vardengan benar. busyboxistirahat di sana - selalu mengevaluasi kedua belah pihak terlepas dari $if_truenilai.
mikeserv
@ruakh - oh man. Saya harus sedikit libur hari ini ... katanya di sana ... apakah yang terakhir kurang portabel ? Saya tidak melihat itu sebelumnya, saya kira ...?
mikeserv