RAM modelini ne motive eder?
Görünüşe göre günümüz algoritma analizlerinin çoğu, RAM modeli gibi sabit zamanlı rastgele erişimli modellerde yapılıyor. Fizik hakkında pek bir şey bilmiyorum ama popüler kaynaklardan, hacim başına bilgi depolamada ve bilgi seyahat hızında bir sınır olması gerektiğini duydum, bu nedenle RAM'ler fiziksel olarak gerçekleştirilebilir görünmüyor. Modern bilgisayarlar tüm bu önbellek seviyelerine sahiptir ki bu da onları RAM benzeri olmadıklarını söyleyebilirim. Öyleyse neden teorik algoritmalar RAM'de ayarlanmalıdır?
Yanıtlar
Bunu vonbrand'dan farklı bir şekilde ele alayım. Söylediğiniz her şey doğrudur: RAM modeli birkaç nedenden dolayı gerçekçi değildir ve farklı yönlerini savunmak mümkün olsa da, böyle bir savunma konunun özüne pek girmez.
Konunun özü - ve sorunuzun cevabı - RAM modelinin sahip olduğumuz en iyi şey olmasıdır. Kabul edilen diğer modellerle karşılaştırıldığında, gerçek hayattaki hesaplamayı daha doğru bir şekilde modeller. Özellikle, RAM modelini benimsememizin nedeni, Turing makinelerinin kullanımının zaman karmaşıklığı açısından yapay olarak çözülmesi zor olan problemlere yol açtığını bulduğumuz için, öncelikle Turing makinelerine bir cevaptı. RAM modeli bu göze batan sorunu açıkça çözüyor ve bu nedenle mükemmel olmaktan uzak kalsa da kabul edildi.
Turing makinelerinde göze çarpan sorunu gösteren klasik bir örnek, dizi eşitliği sorunudur: verilen girdi
$$ w_1 \# w_2$$
nerede $w_1, w_2$ ikili dizilerdir ve $\#$ ayırıcı olup olmadığını belirleyen $w_1 = w_2$. Eşitlik problemi için herhangi bir Turing makinesinin$O(n^2)$zaman. Bu rahatsız edici, çünkü Turing makineleri herkesin evrensel hesaplama modeli olarak düşündüğü şeydir - ancak hiçbir yazılım mühendisi veya algoritma araştırmacısı dizgi eşitliğinin gerçekten gerektirdiğine inanmaz.$O(n^2)$zaman. Peki ne verir? Dize eşitliği doğrusal olmalıdır, bu yüzden olduğu yerde yeni bir model icat ediyoruz ve şu anda mevcut olan en iyi çözüm kelime RAM makineleridir.
Belki ileride bir gün daha iyi bir model bulacağız - basit, kavramsal olarak net ve gerçek hayattaki hesaplama karmaşıklığını modelleme becerisinde RAM'i geliştiren bir model. Şimdilik sadece sahip olduğumuz en iyi şeyle idare edebiliriz.
İlk, kaba bir yaklaşım olarak, önceki erişimlerden bağımsız olarak, bellekteki bir kelimeye sabit olarak erişmek için zaman ayırabilirsiniz. Yani, RAM modeli.
Haklısınız, bugünün makineleri RAM benzeri değil, veri erişimini olabildiğince sıralı olacak şekilde düzenlemek veya (kısa!) Bir bellek bölümünden son bilgi parçasını elle işlemeden önce ezmek (hatta cömertçe) işe yarıyor. sonraki. Ancak bunu yapmak için nadiren boş alanınız olur, hafıza erişiminiz esasen rastgele ve model gerçeklerden o kadar da uzak değildir. Üstelik bugünün makinelerinde birden fazla CPU var, modelde sadece bir CPU var. Ve sonra, "multimedya talimatlarının" (ve hatta daha çok işlem için grafik kartlarının kullanılması) yaptığı gibi vektör işleme (aynı işlemi bir veri vektörü üzerinde tek tek değil) vardır.
Örneğin Khoung'un Binary araması önbellekler için patolojik bir durumdur . Gördüğünüz gibi, daha gerçekçi bellek erişim süresi modelleri altında basit, iyi anlaşılmış algoritmaları bile analiz etmek göz korkutucu.
RAM modeli, tek iş parçacıklı bellek içi hesaplamalar olarak tasarlanmış algoritmaların asimptotik analizi ile motive edilir.
Belirli komut seti, önbellekler ve başka şeyler için performansı optimize etmek bir şeydir. Diğeri ise problem boyutunun büyümesine hazırlıklı olmaktır. Bellek içi algoritmanızın ne kadar iyi ölçeklendiğini tahmin etmek için, muhtemelen küçük faktörleri görmezden gelmek ve büyüklere odaklanmak istersiniz.$\mathcal{O}$gösterim. Büyük$\mathcal{O}$ sizin için her şeyi optimize etmeyecektir, ancak en azından çözümünüzün iyi ölçeklendiğini (veya farklı bir şey denemeniz gerektiğini) söyleyebilir.
RAM, her işlemin çalıştığı küçük sabit komut kümesini varsayar. $\mathcal{O}(1)$. Sadece asimptotik büyümeyi önemsiyorsak, bunun iyi bir model olduğunu unutmayın:
Modern bir CPU'nun komut seti küçük değildir, ancak gerçekte öyle olduğunu varsayabiliriz. Bu ek işlem kodları büyük bir fark yaratmaz$\mathcal{O}$ gösterim.
CPU'ların çalışma zamanı girdiye bağlı olan talimatları olabilir. Yine, onları görmezden gelebiliriz, çünkü onları daha basit talimatlar kullanarak büyük$\mathcal{O}$karmaşıklık. Aynısı önbellek seviyeleri için de geçerlidir: performansları hala küçük bir sabitle sınırlıdır, bu nedenle$\mathcal{O}(1)$ tanım olarak.
Evet, büyümeye devam ederse, sabit zamanda belleğe erişemezsiniz. Neyse ki, sağduyu sayesinde bu asla gerekli değildir. Hiç kimse tüm interneti yalnız tek iş parçacıklı bir makinenin kalıcı olmayan belleğine endekslemiyor.