Sangat sedikit yang benar-benar mati di internet. Archive.org kebetulan memiliki satu snapshot tunggal dari posting blog itu dari saat ditayangkan . Disalin di sini:
Beberapa ilmu komputer perbaikan, untuk auditor PCI di audiens saya.
Saya memberikan Anda sebuah array bilangan bulat acak. Bagaimana Anda bisa tahu jika nomor tiga ada di dalamnya?
Nah, ada cara yang jelas: periksa angka secara berurutan sampai Anda menemukan "3" atau buang array. Pencarian linear. Diberikan 10 angka, Anda harus menganggap itu bisa mengambil 10 langkah; N angka, N langkah.
Gambar 1.png
Pencarian linear buruk. Sulit untuk melakukan yang lebih buruk daripada linear. Mari kita tingkatkan itu. Sortir susunannya.
Gambar 2.png
Array yang diurutkan menunjukkan strategi yang berbeda: lompat bagian tengah array dan lihat apakah nilai yang Anda cari kurang dari (ke kiri) atau lebih besar dari (ke kanan). Ulangi, potong array menjadi dua setiap kali, sampai Anda menemukan nilainya.
Pencarian biner. Dengan 10 angka, akan dibutuhkan sebanyak 3 langkah — log2 dari 10 — untuk menemukan salah satunya dalam array yang diurutkan. O (log n) pencarian mengagumkan. Jika Anda memiliki 65.000 elemen, hanya perlu mengambil 16 langkah untuk menemukan salah satunya. Gandakan elemen, dan ini 17 langkah.
Tapi array yang diurutkan menyedot; untuk satu hal, pengurutan lebih mahal daripada pencarian linear. Jadi kami tidak banyak menggunakan pencarian biner; sebagai gantinya, kami menggunakan pohon biner.
Gambar 3.png
Untuk mencari pohon biner, Anda mulai dari atas, dan tanyakan pada diri sendiri "apakah kunci saya kurang dari (kiri) atau lebih besar dari (kanan) simpul saat ini", dan ulangi sampai ok, ok, ok, Anda sudah mengetahui hal ini. Tapi pohon itu cantik, bukan?
Pencarian dengan pohon biner (seimbang) adalah O (log n), seperti pencarian biner, bervariasi dengan jumlah elemen dalam pohon. Pohon biner luar biasa: Anda mendapatkan pencarian cepat dan sortir traversal, sesuatu yang tidak Anda dapatkan dari tabel hash. Pohon biner adalah implementasi tabel default yang lebih baik daripada tabel hash. 2.
Tapi pohon biner bukan satu-satunya mekanisme pencarian terstruktur pohon. Biner mencoba radix, juga disebut pohon PATRICIA, bekerja seperti pohon biner dengan satu perbedaan mendasar. Alih-alih membandingkan lebih besar dari / kurang dari pada setiap node, Anda memeriksa untuk melihat apakah sedikit diatur, bercabang tepat jika sudah diatur dan dibiarkan jika tidak.
Gambar 4.png
Saya meninggalkan banyak tentang bagaimana radix biner mencoba bekerja. Ini memalukan, karena percobaan radix terkenal sangat tidak terdokumentasi - Sedgewick secara terkenal mengacaukan mereka dalam "Algoritma", dan halaman Wikipedia untuk mereka payah. Orang-orang masih berdebat tentang apa yang memanggil mereka! Sebagai pengganti penjelasan tentang backlink dan edge-position-berlabel edge, inilah implementasi Ruby kecil.
Inilah mengapa percobaan radix keren:
Search performance varies with the key size, not the number of elements in the tree. With 16 bit keys, you’re guaranteed 16 steps
terlepas dari jumlah elemen di pohon, tanpa menyeimbangkan.
More importantly, radix tries give you lexicographic matching, which is a puffed-up way of saying “search with trailing wildcard”, or
"Pencarian gaya-baris-penyelesaian-gaya". Di pohon radix, Anda dapat dengan cepat mencari "ro *" dan mendapatkan "roma" dan "romantis" dan "roswell".
3.
Aku kehilanganmu.
Mari kita letakkan ini dalam konteks. Mencoba adalah struktur data penting untuk perutean Internet. Masalah perutean seperti ini:
You have a routing table with entries for “10.0.1.20/32 -> a” and “10.0.0.0/16 -> b”.
You need packets for 10.0.1.20 to go to “a”
You need packets for 10.0.1.21 to to to “b”
Ini adalah masalah yang sulit untuk dipecahkan dengan pohon biner dasar, tetapi dengan trix radix, Anda hanya meminta "1010.0000.0000.0000.0000.0001.0100" (untuk 10.0.1.20) dan "1010." (untuk 10.0.0.0 ). Pencarian leksikografis memberi Anda "kecocokan terbaik" untuk perutean. Anda dapat mencobanya di kode Ruby di atas; tambahkan * ”10.0.0.0” .to_ip ke trie, dan cari “10.0.0.1” .to_ip.
Korespondensi antara perutean dan percobaan radix sangat kuat sehingga perpustakaan umum tujuan umum radix trie (yang berasal dari CPAN) sebenarnya dicuri dari GateD. Omong-omong, omong-omong, dan jangan menggunakannya.
Jika Anda memahami cara kerja trie, Anda juga memahami cara kerja ekspresi reguler. Coba adalah kasus khusus deterministic finite automata (DFAs), di mana cabang didasarkan secara eksklusif pada perbandingan bit dan selalu cabang ke depan. Mesin regex yang baik hanya menangani DFA dengan lebih banyak "fitur". Jika gambar saya masuk akal bagi Anda, gambar-gambar dalam artikel yang bagus tentang algoritma pengurangan NFA-DFA Thompson juga akan, dan artikel itu akan membuat Anda lebih pintar. 4.
Anda seorang operator jaringan di ISP backbone. Dunia Anda sebagian besar terdiri dari "awalan" - jaringan IP / pasangan netmask. Netmask di awalan itu sangat penting bagi Anda. Misalnya, 121/8 milik Korea; 121.128 / 10 milik Korea Telecom, 121.128.10 / 24 milik pelanggan KT, dan 121.128.10.53 adalah satu komputer di dalam pelanggan itu. Jika Anda melacak botnet atau operasi spamming atau penyebaran worm, nomor netmask itu cukup penting bagi Anda.
Sayangnya, meskipun penting, di mana pun pada paket IP tidak ada cap "netmask" - netmasks sepenuhnya merupakan detail konfigurasi. Jadi, ketika Anda menonton lalu lintas, pada dasarnya Anda memiliki data ini untuk digunakan:
ips.png
Anehnya, diberikan cukup paket untuk dilihat, ini adalah informasi yang cukup untuk menebak dengan netmask. Saat bekerja di Sony, Kenjiro Cho datang dengan cara yang sangat elegan untuk melakukan itu, berdasarkan percobaan. Begini caranya:
Ambil trix biner radix dasar, seperti yang digunakan oleh router perangkat lunak. Tetapi mengikat jumlah node di pohon, katakanlah 10.000. Pada tautan backbone, merekam alamat dari header IP, Anda akan menghabiskan 10.000 node dalam beberapa saat.
Simpan daftar node dalam daftar, diurutkan dalam urutan LRU. Dengan kata lain, ketika Anda mencocokkan alamat IP dengan sebuah simpul, "sentuh" simpul itu, letakkan di bagian atas daftar. Secara bertahap, alamat yang sering terlihat menggelembung ke atas, dan node yang jarang terlihat tenggelam ke bawah.
Gambar 6.png
Sekarang triknya. Ketika Anda kehabisan node dan membutuhkan yang baru, ambil kembali dari bagian bawah daftar. Tetapi ketika Anda melakukannya, gulung data dari node ke induknya, seperti:
Gambar 5.png
10.0.1.2 dan 10.0.1.3 adalah saudara kandung / 32, dua bagian dari 10.0.1.2/31. Untuk mendapatkan kembali, gabungkan menjadi 10.0.1.2/31. Jika Anda perlu mendapatkan kembali 10.0.1.2/31, Anda dapat menggabungkannya dengan 10.0.1.0/31 untuk membentuk 10.0.1.0/30.
Lakukan ini selama, katakanlah, satu menit, dan sumber-sumber yang menonjol akan mempertahankan posisi mereka di pohon dengan tetap berada di bagian atas daftar LRU, sementara gelembung kebisingan sekitar / 0 hingga / 0. Untuk daftar mentah IP di atas, dengan pohon 100 simpul, Anda dapatkan ini.
Cho menyebut Aguri heuristik ini. 5.
Aguri adalah lisensi BSD. Anda dapat mengunduhnya, dan program driver yang menonton paket melalui pcap, dari beranda lama Cho. 6.
Saya pergi ke suatu tempat dengan ini, tapi saya 1300 kata dalam posting ini sekarang, dan jika Anda adalah orang algoritma Anda sudah bosan dengan saya sekarang, dan jika Anda tidak, Anda bosan dengan saya sekarang. Jadi, biarkan Aguri tenggelam, dan aku akan memberimu sesuatu yang keren dan tidak berguna untuk dilakukan minggu ini.
Ada banyak tautan yang tersebar di sana. Sayangnya, Archive.org tidak menyimpan gambar, hanya teks, sehingga beberapa di antaranya telah hilang. Inilah yang telah diarsipkan:
