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?
text-processing
grep
sort
coreutils
kamaal
sumber
sumber
grep
,egrep
, ataufgrep
.Jawaban:
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.
sumber
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)
sumber
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 .
sumber
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.
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
wc
dandiff
.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.
sumber
Saya tidak berpikir begitu, tetapi itu beralih ke algoritma "cepat" non-RE ketika diberi flag -f (atau dipanggil sebagai fgrep).
sumber