Bir metin içinde belirli bir deseni aramak, ilk bakışta basit görünür: her konumdan başlayıp karakterleri karşılaştırırız. Ancak uzun metinler ve tekrar eden örüntüler devreye girdiğinde bu yaklaşım pahalılaşır. Z Algoritması, daha önce yapılmış karşılaştırmaları akıllıca yeniden kullanarak örüntü eşleştirmeyi doğrusal zamanda gerçekleştiren zarif bir tekniktir.
Bir arama kutusuna pro yazdığınızda saniyeler değil, milisaniyeler içinde programlama, proje ve profil önerilerinin belirmesi sihir değildir: sahnenin arkasında çoğu zaman Trie veri yapısı çalışır. Prefix tree olarak da bilinen Trie, kelimeleri karakter karakter dallandırarak saklar. Böylece tüm kelime listesini her tuş vuruşunda baştan sona dolaşmak yerine, yalnızca yazılan öneke karşılık gelen dalı takip ederiz.
Bir ikili arama ağacında (BST) hızlı arama, ekleme ve silme isteriz; ancak anahtarlar sıralı gelirse ağaç bir çubuğa dönüşebilir. Treap, bu talihsiz senaryoyu rastgelelik yardımıyla büyük ölçüde engeller. Adı, tree ve heap kelimelerinin birleşimidir: Anahtarlara göre BST, rastgele önceliklere göre ise heap davranışı sergiler. Böylece AVL veya Kırmızı-Siyah ağaçların katı dengeleme kurallarına alternatif, zarif bir yaklaşım sunar.
Bir kitap arşivinde, DNA dizisinde ya da milyonlarca log satırında belirli bir ifadeyi aradığınızı düşünün. Klasik yöntemle metni baştan sona taramak çoğu zaman yeterlidir; fakat aynı dev metinde binlerce farklı sorgu çalıştırılacaksa maliyet hızla büyür. Suffix Tree ve Suffix Array, metni bir kez ön işleyip sonraki örüntü aramalarını çok daha hızlı hale getiren iki güçlü veri yapısıdır.
Devamı...Splay Tree, klasik ikili arama ağacının (BST) heyecanlı ve biraz da inatçı kuzenidir: Bir düğüme eriştiğiniz anda onu ağacın köküne kadar taşımaya çalışır. Amaç, yakın geçmişte sık kullanılan verilere gelecekte daha hızlı ulaşmaktır. Dengeli ağaçlar gibi her an kusursuz görünmek zorunda değildir; bunun yerine kullanım alışkanlıklarınızı öğrenir.
Devamı...Bir dizideki belirli aralıkların minimumunu, maksimumunu ya da EBOB’unu defalarca bulmanız gerektiğini düşünün. Veri hiç değişmiyorsa, her sorguda aralığı baştan taramak gereksiz bir maliyettir. Sparse Table, ön işlem süresini ve belleği göze alarak sorguları özellikle minimum/maksimum gibi işlemlerde $O(1)$ sürede cevaplayan etkileyici bir veri yapısıdır. Adındaki “sparse” kelimesi yanıltıcı olabilir: Bu yapı seyrek verilerden çok, $2$’nin kuvveti uzunluğundaki önceden hesaplanmış aralık bloklarından oluşur.
Devamı...Sıralı verilerde arama yapmak istediğinizde bağlı listeler basit ama yavaştır; dengeli ikili arama ağaçları ise hızlı ama uygulaması görece karmaşıktır. Skip List, bu iki dünyanın arasına eğlenceli bir olasılık fikri yerleştirir: Bazı düğümlere rastgele seçilen ek “hız şeritleri” verir. Böylece listeyi tamamen yeniden dengelemeden, ortalama durumda oldukça hızlı arama, ekleme ve silme işlemleri sunar.
Devamı...Dağıtık sistemlerde aynı veriyi birden fazla makinede tutmak harikadır; tek bir sunucu bozulduğunda sistem ayakta kalır. Fakat işin zor kısmı şudur: Ağ gecikebilir, makineler sessizce kapanabilir ve iki sunucu aynı anda farklı şeylerin doğru olduğuna inanabilir. Raft, bu kaosu yönetmek için tasarlanmış, anlaşılabilirliği önceleyen bir konsensüs algoritmasıdır. Temel hedefi, tüm sağlıklı düğümlerin işlemleri aynı sırayla uygulamasını sağlamaktır.
Dağıtık sistemlerde en zor soru çoğu zaman “veri nerede?” değil, “herkes aynı kararı verdi mi?” sorusudur. Ağ gecikebilir, makineler kapanabilir ve mesajlar kaybolabilir; buna rağmen banka bakiyesinin, lider seçiminin ya da sipariş durumunun tek bir doğru geçmişi olmalıdır. Paxos, düğümlerin çökebildiği bu kaotik ortamda ortak bir değerde uzlaşmayı sağlayan klasik consensus algoritmasıdır.
Bir dizideki çok sayıda aralık sorgusuna cevap vermek, ilk bakışta masum görünür: Her sorgu için ilgili aralığı dolaşır, sonucu hesaplar ve devam edersiniz. Ancak $N=Q=10^5$ olduğunda, her sorguyu tek tek taramak yaklaşık $O(NQ)$ maliyet üretir. İşte Mo Algoritması tam burada sahneye çıkar: Sorguları akıllıca yeniden sıralayarak, önceki sorgudan elde edilen bilgiyi mümkün olduğunca korur.
Devamı...
Bir dosyanın, veritabanı yedeğinin ya da milyonlarca işlemden oluşan bir blok zinciri bloğunun değiştirilmediğini nasıl kanıtlarsınız? Tüm veriyi her seferinde baştan sona karşılaştırmak güvenlidir, fakat pahalıdır. Merkle ağacı, kriptografik özetleri hiyerarşik biçimde birleştirerek bu sorunu çözer: Küçük bir kanıt paketiyle devasa bir veri kümesindeki belirli bir kaydın bütünlüğü doğrulanabilir.
Devamı...Bir metindeki en uzun palindromik alt diziyi bulmak, ilk bakışta her karakteri merkez kabul edip iki yana açılma fikriyle kolay görünür. Ancak uzun metinlerde bu yaklaşım pahalılaşır. Manacher algoritması, daha önce hesaplanan palindromların simetrisini akıllıca yeniden kullanarak problemi $O(n)$ zamanda çözer. Adı biraz sihirbazlık çağrıştırsa da arkasındaki fikir oldukça sistematiktir.
Bir ağacın kenarlarını çalışma anında ekleyip silmek, ardından iki düğüm arasındaki yolun toplamını saniyeler içinde sormak ilk bakışta masum görünür. Ancak klasik DFS, BFS veya sabit köklenmiş ağır-hafif ayrıştırması bu dünyada zorlanır. Link-Cut Tree (LCT), dinamik ormanlar üzerinde bağlantı, yol sorgusu ve kök değiştirme işlemlerini amortize olarak $O(\log n)$ sürede gerçekleştiren gelişmiş bir veri yapısıdır.
Bir e-ticaret sitesinde kaç farklı kullanıcının ürünü görüntülediğini, bir log kümesinde kaç benzersiz IP bulunduğunu ya da bir kampanyanın gerçek erişimini saymak istiyorsunuz. Tüm kimlikleri Set içinde tutmak kesin sonuç verir; ancak yüz milyonlarca kayıt geldiğinde bellek bütçeniz hızla tükenir. HyperLogLog (HLL), bu noktada küçük ve sabit sayılabilecek bellek karşılığında çok isabetli bir yaklaşık benzersiz eleman sayısı üretir.
Ağaçlar; organizasyon şemalarından dosya sistemlerine, oyun haritalarından ağ topolojilerine kadar pek çok yerde karşımıza çıkar. Ancak iki düğüm arasındaki yol üzerindeki toplamı, maksimumu veya güncellemeleri hızlı biçimde hesaplamak istediğimizde klasik DFS yaklaşımı yetersiz kalır. Heavy-Light Decomposition (HLD), ağacı parçalara ayırarak bu karmaşık yol sorgularını etkileyici biçimde hızlandıran güçlü bir tekniktir.
Devamı...
Öncelik kuyruğu denince çoğumuzun aklına ikili yığın (binary heap) gelir: eleman ekle, en küçüğü al, işlem tamam. Ancak Dijkstra veya Prim gibi algoritmalarda bazı anahtarların değeri sürekli azaltılıyorsa, teorik olarak daha iddialı bir oyuncu sahneye çıkar: Fibonacci Heap. Bu veri yapısı, bazı pahalı işleri erteleyerek özellikle decrease-key operasyonunu amortismanlı olarak son derece ucuz hâle getirir.
Hash tabloları, anahtarları ortalama $O(1)$ sürede bulma vaadiyle programlamanın görünmez kahramanlarıdır. Ancak iki anahtar aynı konuma düştüğünde ortaya çıkan çakışma, bu vaadi zorlayabilir. Cuckoo Hashing, çakışmayı zincirleme listelerle uzatmak yerine iki farklı olası yuva sunar ve gerekirse mevcut elemanı yerinden “tekmeleyerek” taşır. Adını da yumurtasını başka kuşların yuvasına bırakan guguk kuşundan alır.
Devamı...Bir not alma uygulamasını iki telefonda, internet bağlantısı olmadan kullandığınızı düşünün. Aynı notu bir cihazda silerken diğerinde yeni bir madde eklediniz. Bağlantı geri geldiğinde klasik bir sistem genellikle “hangi sürüm doğru?” diye panikler. CRDT’ler ise bu tartışmayı matematiksel kurallarla çözer: Her cihaz değişiklik yapabilir, ardından veriler sıradan bağımsız biçimde birleşerek aynı sonuca ulaşır.
Dağıtık sistemlerde veriyi sunuculara paylaştırmak ilk bakışta kolay görünür: bir anahtarın hash değerini alır, sunucu sayısına göre modunu hesaplar ve hedefi buluruz. Fakat yeni bir sunucu eklediğinizde ya da arızalı bir makineyi kümeden çıkardığınızda bu sade yaklaşım, neredeyse bütün verilerin farklı yerlere taşınmasına yol açabilir. Consistent Hashing, tam bu taşınma fırtınasını küçültmek için tasarlanmış akıllı bir dağıtım tekniğidir.
Devamı...Bir metinde tek bir kelime aramak kolaydır; indexOf, regex veya KMP çoğu zaman yeterlidir. Peki bir log akışında binlerce zararlı imzayı, bir sözlükte binlerce anahtar sözcüğü ya da bir DNA dizisinde çok sayıda motifi aynı anda bulmak gerekirse? Her kelime için metni yeniden taramak, büyüyen veriyle birlikte pahalılaşır. Aho-Corasick, bu problemi bir trie ve akıllı geri dönüş bağlantılarıyla tek geçişte çözen klasik çoklu örüntü arama algoritmasıdır.
