Seberapa cerdas utilitas unix?

8

Utilitas Unix seperti sort, find, grep, diff et al sangat berguna untuk melakukan tugas cepat, terkadang tanpa menulis kode apa pun.

Saya ingin tahu algoritma apa yang mereka gunakan secara internal dan bagaimana cara cerdas menentukan algoritma tertentu untuk tugas tertentu? Misalnya jika sort mendapat file input yang besar, apakah akan menggunakan algoritma yang berbeda untuk ukuran data yang berbeda?

Apakah grep secara cerdas beralih algoritma saat mencari set data yang berbeda?

kamaal
sumber
4
Mereka sangat cerdas sehingga suatu hari akan mengambil alih Bumi. Tetapi untuk sekarang Anda harus memutuskan mana yang Anda akan digunakan, seperti grep, egrep, atau fgrep.
Keith
1
Tetapi jika Anda menggunakan egrep secara teratur dan kemudian tiba-tiba beralih ke fgrep, itu mungkin memutuskan untuk membunuh Anda dalam tidur Anda karena tidak setia.
Shadur
1
Mereka secerdas tangan yang memegangnya.
luis.espinal

Jawaban:

7

Unix hanyalah sebuah standar, ia menentukan apa yang harus dilakukan implementasi, tetapi tidak bagaimana mereka harus melakukannya.

Oleh karena itu implementasi grep / sort / find kemungkinan besar akan menggunakan pendekatan yang berbeda pada sistem yang berbeda (dan bahkan satu sistem, seperti Linux, ada implementasi bersamaan).

Untuk Linux, Anda selalu dapat melihat ke dalam kode sumber.

Šimon Tóth
sumber
2
Untuk melengkapi jawaban Anda: gnu.org/software/coreutils
sahid
Mengapa Anda perlu melihat kode sumbernya? Algoritma greps dikenal dan didokumentasikan. Bahkan di halaman Wikipedia untuk grep. tautan
Akun Terhapus
@Deleted Saya pikir Anda salah mengira prinsip dengan implementasi.
Šimon Tóth
@Let_Me_Be: Algoritma dan bahkan implementasinya dikenal dan didokumentasikan. tautan tautan
Akun Terhapus
@Deleted Mungkin saya tidak mengerti apa yang ingin Anda katakan, tetapi Linux grep dari coreutils menggunakan algoritma tertentu, tidak berarti semua implementasi menggunakan algoritma ini. Dan ya, Anda benar karena algoritme cenderung terkenal (karena itulah tujuan mendesainnya).
Šimon Tóth
2

Anda mungkin tertarik pada posting milis ini oleh penulis grep GNU asli yang menjelaskan beberapa optimasi grep GNU. Eksplorasi lain yang menyenangkan oleh ridiculous_fish (penulis Hex Fiend)

Tidak yakin
sumber
1

Standar UNIX tidak menentukan detail implementasi untuk alat sistem standar, kecuali untuk kasus yang sangat langka. Anda dapat menemukan vesion Spesifikasi Single Unix terbaru di sini (peringatan: diperlukan pendaftaran).

Dengan pemikiran itu, setiap UNIX (Sistem V dan turunan langsung seperti BSD, Solaris, Mac OS X, dll.) Atau Sistem Operasi berbasis UNIX (turunan jauh atau serupa: Linux, Minix) memiliki implementasi sendiri dari utilitas yang dijelaskan dalam spesifikasi UNIX. Untuk misalnya. lihatlah FreeBSD dan Linux / GNU Coreutils . Berhati-hatilah karena beberapa alat memisahkan keseluruhan proyek sendiri seperti GNU diff atau GNU grep . Juga fakta lain adalah bahwa beberapa implementasi dari alat-alat ini mungkin menemukan jalan mereka ke sistem seperti UNIX lain sebagai standar kemudian yang mereka awalnya ditulis, untuk misalnya beberapa gnu coreutils di freebsd atau GCC.

Bonus: Untuk membungkus kepala Anda di sekitar pohon keluarga UNIX, lihat grafik ini .

Shinnok
sumber
0

Saya ingin tahu algoritma apa yang mereka gunakan secara internal dan bagaimana cara cerdas menentukan algoritma tertentu untuk tugas tertentu? Misalnya jika sort mendapat file input yang besar, apakah akan menggunakan algoritma yang berbeda untuk ukuran data yang berbeda?

Itu pertanyaan yang menarik (+1 untuk itu). Saya tidak tahu apa jawabannya, tetapi jika saya adalah Anda, saya akan melihat kode sumber utilitas GNU tipikal untuk mendapatkan gambaran tentang algoritma mereka.

Apakah grep secara cerdas beralih algoritma saat mencari set data yang berbeda?

Saya kira tidak. Jangan mengutip saya karena saya tidak bisa benar-benar memberi tahu Anda dengan kepastian 100%, tapi saya benar-benar tidak berpikir begitu. Filsafat UNIX tentang hal-hal adalah bahwa satu hal melakukan satu hal dan satu hal saja. Itulah mengapa kita memiliki beberapa versi grep ( grep, egrep, fgrep).

Juga, idenya adalah untuk melakukan satu hal dan hanya satu hal pada saat run-time. Perilaku dan algoritma yang berbeda dapat dikonfigurasikan sebagai argumen baris perintah, sehingga program yang sama dapat bertindak sedikit berbeda (dan mungkin sedikit lebih dioptimalkan) antara menjalankan. Contoh yang baik adalah perintah wcdan diff.

Namun, adaptasi perilaku berbasis konfigurasi (melalui argumen garis cmd); mereka tidak mengubah / mengadaptasi perilaku saat run-time. Ini biasanya merupakan kompleksitas yang tidak perlu untuk jenis artefak yang menjadi tujuan alat UNIX.

Kompleksitas seperti itu lebih cocok untuk alat IMO yang lebih kompleks dan kurang umum.

luis.espinal
sumber
2
Tema di sini lebih dari TIDAK, mereka sebenarnya bodoh! . Anda harus memberi tahu mereka apa yang harus dilakukan. Bagaimanapun, kami tidak ingin mereka terlalu pintar pada kami, Anda tahu.
tshepang
0

Apakah grep secara cerdas beralih algoritma saat mencari set data yang berbeda?

Saya tidak berpikir begitu, tetapi itu beralih ke algoritma "cepat" non-RE ketika diberi flag -f (atau dipanggil sebagai fgrep).

kmarsh
sumber
yaitu tidak benar-benar cerdas :)
tshepang