Resmi rehber · Finding Needle in the Stack
Bilgisayar bilimlerinde samanlıkta iğne
Yazılımcılar «samanlıkta iğne»yi sürekli söyler. Bir milyar kayıt arasında tek bir kaydı bulmak, devasa bir programdaki tek bir hatalı satırı, trafik selindeki tek bir paketi bulmak: samanın içindeki çelik iğneyle aynı sorundur. Bir samanlık oyunu, çözümlerin nasıl çalıştığını görmek için güzel bir yol çıkıyor.
Yavaş yol: her şeye bakmak
İğnenin nerede olduğu hakkında hiçbir şey bilmiyorsanız tek seçenek, bulana kadar her saman parçasına bakmaktır. Bilgisayar bilimlerinde buna doğrusal arama denir. Ortalamada başarıya ulaşmadan önce her şeyin yarısına bakarsınız, en kötü durumda hepsine. Her zaman çalışır ama süre yığının büyüklüğüyle orantılı artar.
Sıralama her şeyi değiştirir
Şimdi samanın bir sözlükteki kelimeler gibi sıraya dizildiğini düşünün. Daha akıllı bir yöntem olan ikili arama, ortadan açar, cevabın hangi yarıda olduğuna karar verir ve diğer yarıyı atar. Bunu tekrarlayın, bir milyon öğe yaklaşık 20 adımda taranır. Püf nokta, yığının önce sıralı olması gerektiğidir; bir samanlık ise hiçbir zaman öyle değildir.
İndeksler: hazırlanarak hile yapmak
Veritabanları ve arama motorları, zor işi önceden yaparak sorunu aşar. Bir kitabın arkasındaki, bir kelimenin hangi sayfada olduğunu söyleyen liste gibi bir indeks kurarlar. Aramak hızlanır, çünkü zaman önceden harcanmıştır. Gerçek bir samanlık için indeks yoktur ve deyimin var olmasının sebebi tam olarak budur.
Bir sinyali izlemek
Bir metal dedektörü farklıdır. İğnenin nerede olduğunu söylemez ama yaklaşıp yaklaşmadığınızı söyler. Yaklaştıkça yükselen bir sayı hayal edin. O zaman basit bir kural kullanabilirsiniz: bir adım atın, sinyalin güçlenip güçlenmediğine bakın ve onu iyileştiren yönde devam edin. Yazılımcılar bunun bir sürümüne tepe tırmanma (hill climbing) der ve birçok pratik eniyilemenin arkasındadır.
Oyunda sinyal, en yakın metal parçasına olan uzaklığınızın dedektörün menziline oranıyla hesaplanır. Bu sayı 1'e yaklaştıkça bip sesleri hızlanır, yani tepe tırmanmayı sizin yerinize kulağınız yapar. Daha fazlası Metal dedektörü nasıl çalışır yazısında.
Sinyaller başarısız olduğunda
Tepe tırmanma takılabilir. İğnenin yakınında çok fazla hurda metal varsa, en güçlü sinyal sizi bir çiviye götürebilir. Oyun bunu, üst seviye dedektörlere iğneyi ayırt etme yeteneği vererek çözer. Gerçek aramalar da aynı sorunla karşılaşır ve daha iyi sensörler ya da ek filtreler kullanır.
Veri olarak samanlık
Oyundaki samanlığın kendisi de bir veri yapısıdır: her biri samanın yoğunluğu için bir sayı tutan 88 x 40 x 88 hücrelik bir ızgara. Kazmak sayıları değiştirmektir ve 16 hücrelik chunk'lar işi küçük tutar. Nasıl çalıştığı Samanlık nasıl çalışır yazısında.
Kazmaya hazır mısın?
Tarayıcında ücretsiz, bilgisayarda ve telefonda. İlerlemen otomatik olarak kaydedilir.
Hemen ücretsiz oyna