Ön hesaplama - Precomputation

20. yüzyılın önceden hesaplanmış bir parçası matematiksel tablo nın-nin ortak logaritmalar.

İçinde algoritmalar, ön hesaplama bir başlangıç ​​yapma eylemidir hesaplama önce Çalışma süresi oluşturmak için arama tablosu bu, her yürütüldüğünde tekrarlanan hesaplamayı önlemek için bir algoritma tarafından kullanılabilir. Ön hesaplama genellikle, algoritmanın girdisine bağlı olmayan pahalı hesaplamaların sonuçlarına bağlı olan algoritmalarda kullanılır. Ön hesaplamanın önemsiz bir örneği, kodlanmış matematiksel sabitler, örneğin π ve e, tahminlerini çalışma zamanında gerekli hassasiyete göre hesaplamak yerine.

İçinde veritabanları, dönem maddileştirme bir ön hesaplamanın sonuçlarının depolanmasına atıfta bulunmak için kullanılır,[1][2] gibi somut görünüm.[3][4]

Genel Bakış

Bir algoritmanın yürütmesinin başlangıcında bir dizi ara sonucun önceden hesaplanması, genellikle artabilir algoritmik verimlilik esasen. Bu, bir veya daha fazla giriş, sonuçların makul büyüklükte bir bellek bloğunda saklanabileceği kadar küçük bir aralıkla sınırlandırıldığında avantajlı hale gelir. Çünkü bellek erişimi, zaman karmaşıklığı açısından esasen sabittir ( Önbelleğe almak gecikmeler), küçük bir girdi aralığında sabit verimlilikten daha kötü olan bir bileşene sahip herhangi bir algoritma, değerlerin önceden hesaplanmasıyla geliştirilebilir. Bazı durumlarda verimli yaklaşım algoritmaları, bir ayrık değerlerin alt kümesi ve enterpolasyon ara giriş değerleri için, çünkü enterpolasyon aynı zamanda doğrusal bir işlemdir.

Tarih

Bilgisayarların ortaya çıkmasından önce, basılı arama tabloları değerler, insanlar tarafından karmaşık fonksiyonların elle hesaplanmasını hızlandırmak için kullanıldı. trigonometrik tablolar, logaritma tabloları ve tablolar istatistiksel yoğunluk fonksiyonları[5] Okul çocuklarına genellikle ezberlemeleri öğretilir "çarpım tabloları "en sık kullanılan sayıların hesaplanmasından kaçınmak için (9 x 9 veya 12 x 12'ye kadar). 493 A.D. gibi erken bir zamanda bile, Aquitaine Victorius 98 sütunlu bir çarpım tablosu yazdı (içinde Roma rakamları ) 2'den 50'ye kadar her sayının çarpımı ve satırlar "bin ile başlayan, yüzler ile yüz arasında azalan, sonra ondan ona kadar azalan, sonra bire bir ve sonra da aşağıya doğru azalan sayıların bir listesi idi. 1/144 "e kadar [6]

Örnekler

Dijitalin modern bilgisayar uygulamaları bile trigonometrik fonksiyonlar katsayıları sağlamak için genellikle önceden hesaplanmış arama tablolarını kullanır. interpolasyon algoritmaları veya ardışık başlatmak için yaklaşım algoritmaları.

Birçok saldırı şifreleme sistemleri ön hesaplamayı içerir.

Modern verimli algoritmaların bir parçası olarak büyük ölçekli ön hesaplama örnekleri şunları içerir:

Derleyiciler Ön hesaplamayı, sonuçta ortaya çıkan kodun çalışma zamanı hızını artırmanın bir yolu olarak yaygın bir şekilde kullanın: bu ön hesaplama, gerçekte bir biçim olarak kabul edilebilir. kısmi değerlendirme program kodunun kendisi. Bu tür bir ön hesaplamanın örnekleri şunları içerir: veri akışı analizi ve güç azalması adımlar.

Ayrıca bakınız

Referanslar

  1. ^ Jiawei Han; Micheline Kamber (9 Haziran 2011). Veri Madenciliği: Kavramlar ve Teknikler: Kavramlar ve Teknikler. Elsevier. s. 159. ISBN  978-0-12-381480-7.
  2. ^ Sven Groppe (29 Nisan 2011). Anlamsal Web Veritabanlarında Veri Yönetimi ve Sorgu İşleme. Springer Science & Business Media. s. 178. ISBN  978-3-642-19357-6.
  3. ^ Karen Morton; Kerry Osborne; Robyn Sands; Riyaj Shamsudeen; Jared Still (28 Ekim 2013). Pro Oracle SQL. Apress. s. 48. ISBN  978-1-4302-6220-6.
  4. ^ Marie-Aude Aufaure; Esteban Zimányi (16 Ocak 2012). Business Intelligence: First European Summer School, EBISS 2011, Paris, Fransa, 3-8 Temmuz 2011, Tutorial Lectures. Springer Science & Business Media. s. 43. ISBN  978-3-642-27357-5.
  5. ^ Campbell-Kelly, Martin; Croarken, Mary; Sel, Raymond; ve diğerleri, eds. (2003). Sümerden Elektronik Tablolara Matematik Tablolarının Tarihi. Oxford University Press. ISBN  978-0-19-850841-0.
  6. ^ Maher, David. W. J. ve John F. Makowski. "Kesirli Roma Aritmetiği için Edebi Kanıt", "Klasik Filoloji" (2001) Cilt. 96 No. 4 (2001) s. 376–399. (Bkz. Sayfa s. 383.)