Algoritmik verimlilik - Algorithmic efficiency

Olarak bilgisayar biliminin , algoritmik etkinliği bir özelliğidir algoritma miktarı ile ilgilidir hesaplama kaynaklarına algoritma tarafından kullanılır. Kaynak kullanımını belirlemek için bir algoritma analiz edilmelidir ve bir algoritmanın verimliliği, farklı kaynakların kullanımına dayalı olarak ölçülebilir. Algoritmik verimlilik, tekrar eden veya sürekli bir süreç için mühendislik üretkenliğine benzer olarak düşünülebilir .

Maksimum verimlilik için kaynak kullanımını en aza indirmek istiyoruz. Bununla birlikte, zaman ve uzay karmaşıklığı gibi farklı kaynaklar doğrudan karşılaştırılamaz, bu nedenle iki algoritmadan hangisinin daha verimli olduğu genellikle hangi verimlilik ölçüsünün en önemli olarak kabul edildiğine bağlıdır.

Örneğin, kabarcık sıralama ve timsort , öğelerin listesini en küçükten en büyüğe sıralamak için kullanılan algoritmalardır . Kabarcık sıralama, listeyi karesi alınan öğelerin sayısıyla orantılı olarak sıralar ( , bkz. Büyük O notasyonu ), ancak yalnızca listenin uzunluğuna göre sabit olan az miktarda fazladan bellek gerektirir ( ). Timsort, listeyi zaman doğrusallığına göre (bir niceliğin logaritmasının logaritması ile orantılı olarak) listenin uzunluğuna göre sıralar ( ), ancak listenin uzunluğunda doğrusal bir boşluk gereksinimi vardır ( ). Belirli bir uygulama için büyük listelerin yüksek hızda sıralanması gerekiyorsa, timsort daha iyi bir seçimdir; ancak, sıralamanın bellek ayak izini en aza indirmek daha önemliyse, kabarcıklı sıralama daha iyi bir seçimdir. ${\displaystyle \scriptstyle {{\mathcal {O}}\sol(n^{2}\sağ)}}$${\textstyle \scriptstyle {{\mathcal {O}}\sol(1\sağ)}}$${\textstyle \scriptstyle {\matematiksel {O\sol(n\log n\sağ)}}}$${\textstyle \scriptstyle {\matematiksel {O\sol(n\sağ)}}}$

Arka fon

Zamana göre verimliliğin önemi Ada Lovelace tarafından 1843'te Charles Babbage'ın mekanik analitik motoruna uygulanarak vurgulanmıştır :

"Neredeyse her hesaplamada, işlemlerin ardışıklığı için çok çeşitli düzenlemeler mümkündür ve çeşitli hususlar, bir hesaplama motorunun amaçları için aralarındaki seçimleri etkilemelidir. Temel bir amaç, azaltma eğiliminde olan düzenlemeyi seçmektir. hesaplamayı tamamlamak için gereken minimum süre"

Erken elektronik bilgisayarlar , hem işlemlerin hızı hem de mevcut bellek miktarı ile ciddi şekilde sınırlıydı. Bazı durumlarda , bir görevin ya oldukça fazla işleyen bellek kullanan hızlı bir algoritma kullanılarak ya da çok az işleyen bellek kullanan daha yavaş bir algoritma kullanılarak gerçekleştirilebileceği bir uzay-zaman değiş tokuşu olduğu fark edildi. . O zaman mühendislik takası, mevcut belleğe sığacak en hızlı algoritmayı kullanmaktı.

Modern bilgisayarlar, eski bilgisayarlardan önemli ölçüde daha hızlıdır ve çok daha büyük miktarda kullanılabilir belleğe sahiptir ( Kigabayt yerine Gigabayt ). Yine de Donald Knuth , verimliliğin hala önemli bir husus olduğunu vurguladı:

"Yerleşik mühendislik disiplinlerinde, kolayca elde edilen %12'lik bir iyileştirme asla marjinal kabul edilmez ve yazılım mühendisliğinde de aynı bakış açısının hakim olması gerektiğine inanıyorum"

genel bakış

Hesaplama maliyeti olarak da bilinen kaynak tüketimi, kabul edilebilir bir düzeyde veya altındaysa, bir algoritma verimli olarak kabul edilir. Kabaca söylemek gerekirse, 'kabul edilebilir' şu anlama gelir: uygun bir bilgisayarda, tipik olarak girdi boyutunun bir fonksiyonu olarak makul bir süre veya yerde çalışacaktır . 1950'lerden beri bilgisayarlar hem kullanılabilir hesaplama gücünde hem de kullanılabilir bellek miktarında çarpıcı artışlar gördü, bu nedenle mevcut kabul edilebilir seviyeler 10 yıl önce bile kabul edilemez olurdu. Aslında, bilgisayar gücünün yaklaşık her 2 yılda bir ikiye katlanması sayesinde , modern akıllı telefonlarda ve gömülü sistemlerde kabul edilebilir derecede verimli olan görevler, 10 yıl önce endüstriyel sunucular için kabul edilemez derecede verimsiz olabilirdi .

Bilgisayar üreticileri sıklıkla daha yüksek performansa sahip yeni modeller ortaya çıkarırlar . Yazılım maliyetleri oldukça yüksek olabilir, bu nedenle bazı durumlarda daha yüksek performans elde etmenin en basit ve en ucuz yolu, mevcut bir bilgisayarla uyumlu olması koşuluyla daha hızlı bir bilgisayar satın almak olabilir .

Bir algoritma tarafından kullanılan kaynakların ölçülebileceği birçok yol vardır: en yaygın iki ölçü hız ve bellek kullanımıdır; Diğer önlemler iletim hızını, geçici disk kullanımı, uzun süreli disk kullanımını, güç tüketimini, içerebilir toplam sahip olma maliyetini , yanıt süresini yani bu tedbirlerin birçoğu algoritmaya girdi büyüklüğüne bağlıdır vb dış uyaranlara, işlenecek veri miktarı. Ayrıca verilerin düzenlenme şekline de bağlı olabilirler; örneğin, bazı sıralama algoritmaları , önceden sıralanmış veya ters sırada sıralanmış veriler üzerinde düşük performans gösterir.

Pratikte, doğruluk ve/veya güvenilirlik gereksinimleri gibi bir algoritmanın verimliliğini etkileyebilecek başka faktörler de vardır. Aşağıda ayrıntılı olarak açıklandığı gibi, bir algoritmanın uygulanma şekli de gerçek verimlilik üzerinde önemli bir etkiye sahip olabilir, ancak bunun birçok yönü optimizasyon sorunlarıyla ilgilidir .

Teorik analiz

Algoritmaların teorik analizinde normal uygulama, karmaşıklıklarını asimptotik anlamda tahmin etmektir. En yaygın olarak kullanılan notasyon kaynak tüketimi ya da "karmaşıklığı" tanımlamaktır Donald Knuth sitesindeki Büyük O gösterimi girişinin büyüklüğünün bir fonksiyonu olarak bir algoritma karmaşıklığı temsil . Big O notasyonu, fonksiyon karmaşıklığının asimptotik bir ölçüsüdür; burada kabaca bir algoritma için zaman gereksiniminin orantılı olduğu anlamına gelir, keyfi olarak büyüdükçe fonksiyonun büyümesine daha az katkıda bulunan daha düşük dereceli terimleri ihmal eder . Bu tahmin küçük olduğunda yanıltıcı olabilir , ancak büyük olduğunda gösterim asimptotik olduğundan genellikle yeterince doğrudur . Örneğin, yalnızca birkaç öğe sıralanacaksa , kabarcık sıralama birleştirme sıralamadan daha hızlı olabilir ; ancak her iki uygulamanın da küçük bir liste için performans gereksinimlerini karşılaması muhtemeldir. Tipik olarak, programcılar büyük girdi boyutlarına verimli bir şekilde ölçeklenen algoritmalarla ilgilenir ve çoğu veri yoğun programda karşılaşılan uzunluk listeleri için kabarcık sıralama yerine birleştirme sıralama tercih edilir. ${\textstyle \scriptstyle n}$${\textstyle \scriptstyle {f\sol(n\sağ)\,=\,{\mathcal {O}}\sol(g\sol(n\sağ)\sağ)}}$${\displaystyle \scriptstyle {g\sol(n\sağ)}}$${\displaystyle \scriptstyle {g\sol(n\sağ)}}$${\displaystyle \scriptstyle n}$ ${\textstyle \scriptstyle n}$${\textstyle \scriptstyle n}$

Algoritmaların asimptotik zaman karmaşıklığına uygulanan bazı Big O notasyonu örnekleri şunları içerir:

gösterim	isim	Örnekler
${\ Displaystyle {\Mathcal {O}}(1)\,}$	sabit	Sıralanmış bir ölçüm listesinden medyanı bulma; Sabit boyutlu bir arama tablosu kullanma ; Bir öğeyi aramak için uygun bir karma işlevi kullanma .
${\ Displaystyle {\Mathcal {O}}(\log {n})\,}$	logaritmik	İkili arama veya dengeli arama ağacının yanı sıra Binom yığınındaki tüm işlemlerle sıralanmış bir dizideki bir öğeyi bulma .
${\görüntüleme stili {\matematiksel {O}}(n)\,}$	doğrusal	Sıralanmamış bir listede veya hatalı biçimlendirilmiş bir ağaçta (en kötü durum) veya sıralanmamış bir dizide bir öğe bulma; Dalgalanma taşıma ile iki n- bit tamsayı ekleme .
${\displaystyle {\mathcal {O}}(n\log n)\,}$	lineerithmic , loglinear veya quasilinear	Hızlı Fourier Dönüşümü Gerçekleştirme ; yığın sıralama , hızlı sıralama ( en iyi ve ortalama durum ) veya birleştirme sıralama
${\displaystyle {\mathcal {O}}(n^{2})\,}$	ikinci dereceden	İki n basamaklı sayıyı basit bir algoritma ile çarpma ; kabarcık sıralama (en kötü durum veya saf uygulama), Kabuk sıralama , hızlı sıralama ( en kötü durum ), seçim sıralama veya ekleme sıralama
${\displaystyle {\mathcal {O}}(c^{n}),\;c>1}$	üstel	Dinamik programlama kullanarak gezgin satıcı problemine optimal ( yaklaşık olmayan ) çözümü bulma ; kaba kuvvet araması kullanarak iki mantıksal ifadenin eşdeğer olup olmadığını belirleme

Kıyaslama: performansı ölçme

Yazılımın yeni sürümleri için veya rakip sistemlerle karşılaştırmalar sağlamak için , bazen bir algoritmanın göreli performansını ölçmeye yardımcı olan kıyaslamalar kullanılır. Örneğin, yeni bir sıralama algoritması üretilirse, herhangi bir işlevsel iyileştirme göz önünde bulundurularak, bilinen verilerle en azından eskisi gibi verimli olmasını sağlamak için öncekilerle karşılaştırılabilir. Müşteriler, işlevsellik ve performans açısından hangi ürünün kendi özel gereksinimlerine en uygun olacağını tahmin etmek için alternatif tedarikçilerden çeşitli ürünleri karşılaştırırken müşteriler tarafından kullanılabilir. Örneğin, ana bilgisayar dünyasında , Syncsort gibi bağımsız yazılım şirketlerinin belirli tescilli sıralama ürünleri, IBM gibi büyük tedarikçilerin ürünleriyle hız için rekabet eder .

Bazı karşılaştırma ölçütleri, örneğin çeşitli derlenmiş ve yorumlanmış dillerin göreli hızlarını karşılaştıran bir analiz üretmek için fırsatlar sağlar ve Bilgisayar Dili Karşılaştırma Oyunu , çeşitli programlama dillerinde tipik programlama sorunlarının uygulamalarının performansını karşılaştırır.

" Kendin yap " kıyaslamaları oluşturmak bile , kullanıcı tarafından belirlenen çeşitli kriterleri kullanarak farklı programlama dillerinin göreli performansını gösterebilir. Christopher W. Cowell-Shah'ın "Dokuz dil performansı toplaması"nın bir örnekle gösterdiği gibi, bu oldukça basittir.

Uygulama endişeleri

Programlama dili seçimi veya algoritmanın gerçekte kodlanma şekli veya belirli bir dil için derleyici seçimi veya kullanılan derleme seçenekleri ve hatta işletim sistemi gibi uygulama sorunlarının da verimlilik üzerinde etkisi olabilir. sistem kullanılıyor. Çoğu durumda, bir yorumlayıcı tarafından uygulanan bir dil, bir derleyici tarafından uygulanan bir dilden çok daha yavaş olabilir. Tam zamanında derleme ve yorumlanan diller hakkındaki makalelere bakın .

Zaman veya mekan sorunlarını etkileyebilecek, ancak bir programcının kontrolü dışında olabilecek başka faktörler de vardır; bunlara veri hizalama , veri ayrıntı düzeyi , önbellek konumu , önbellek tutarlılığı , çöp toplama , talimat düzeyinde paralellik , çoklu iş parçacığı oluşturma (donanım veya yazılım düzeyinde), eşzamanlı çoklu görev ve alt program çağrıları dahildir.

Bazı işlemciler, tek bir komutun birden çok işlenen üzerinde çalışmasına izin veren vektör işleme yeteneklerine sahiptir ; bir programcının veya derleyicinin bu yetenekleri kullanması kolay olabilir veya olmayabilir. Sıralı işleme için tasarlanan algoritmaların, paralel işlemeyi kullanmak için tamamen yeniden tasarlanması gerekebilir veya kolayca yeniden yapılandırılabilirler. Olarak paralel ve dağıtılmış işlem sonunda 2010'larda önemini giderek daha fazla yatırım etkin olarak yapılmaktadır yüksek düzeyde ilaç aktif paralel için ve bu şekilde işlem sistemleri dağıtılmış CUDA'ya , TensorFlow , Hadoop'un , OpenMP ve MPI .

Programlamada ortaya çıkabilecek diğer bir problem, aynı komut seti ( x86-64 veya ARM gibi ) ile uyumlu işlemcilerin bir komutu farklı şekillerde uygulayabilmeleri, bu nedenle bazı modellerde nispeten hızlı olan talimatların diğer modellerde nispeten yavaş olabilmesidir. . Bu genellikle , bir programı performans için en iyi şekilde optimize etmek için belirli CPU ve derleme hedefinde bulunan diğer donanımlar hakkında büyük miktarda bilgiye sahip olması gereken derleyicileri optimize etmek için zorluklar sunar . Aşırı durumda, bir derleyici , bir derleme hedef platformunda desteklenmeyen talimatları taklit etmeye zorlanabilir ve bu, yerel olarak desteklense bile, bu platformda hesaplanamayan bir sonuç üretmek için kod oluşturmaya veya harici bir kitaplık çağrısını bağlamaya zorlayabilir. ve diğer platformlarda donanımda daha verimli. Bu genellikle, küçük ve düşük güçlü mikro denetleyicilerin kayan nokta aritmetiği için donanım desteğinden yoksun olduğu ve bu nedenle kayan nokta hesaplamaları üretmek için hesaplama açısından pahalı yazılım rutinleri gerektirdiği kayan nokta aritmetiğine ilişkin gömülü sistemlerde geçerlidir .

Kaynak kullanım ölçüleri

Ölçüler normalde girdi boyutunun bir fonksiyonu olarak ifade edilir . ${\displaystyle \scriptstyle {n}}$

En yaygın iki önlem şunlardır:

• Süre : Algoritmanın tamamlanması ne kadar sürer?
• Boşluk : Algoritma için ne kadar çalışan belleğe (tipik olarak RAM) ihtiyaç vardır? Bunun iki yönü vardır: kodun ihtiyaç duyduğu bellek miktarı (yardımcı alan kullanımı) ve kodun üzerinde çalıştığı veri için gereken bellek miktarı (iç alan kullanımı).

Gücü bir pille sağlanan bilgisayarlar (örneğin dizüstü bilgisayarlar ve akıllı telefonlar ) veya çok uzun/büyük hesaplamalar (örneğin süper bilgisayarlar ) için diğer ilgi alanları şunlardır:

• Doğrudan güç tüketimi : bilgisayarı çalıştırmak için doğrudan gereken güç.
• Dolaylı güç tüketimi : soğutma, aydınlatma vb. için gereken güç.

2018 itibariyle, güç tüketimi, gömülü nesnelerin interneti cihazlarından çip üzerinde sistem cihazlarına ve sunucu çiftliklerine kadar her türden ve her ölçekteki hesaplama görevleri için önemli bir ölçüm olarak büyüyor . Bu eğilim genellikle yeşil bilgi işlem olarak adlandırılır .

Daha az yaygın olan hesaplama verimliliği ölçütleri de bazı durumlarda ilgili olabilir:

• İletim boyutu : bant genişliği sınırlayıcı bir faktör olabilir. Veri sıkıştırma , iletilecek veri miktarını azaltmak için kullanılabilir. Bir resmin veya görüntünün (örneğin Google logosu ) görüntülenmesi, "Google" metni için altı bayt iletmeye kıyasla on binlerce bayt (bu durumda 48K) iletilmesine neden olabilir. Bu, G/Ç bağlantılı bilgi işlem görevleri için önemlidir .
• Harici alan : bir diskte veya başka bir harici bellek aygıtında ihtiyaç duyulan alan; bu, algoritma yürütülürken geçici depolama için olabilir veya ileride başvurmak üzere ileriye taşınması gereken uzun vadeli depolama olabilir.
• Tepki süresi ( gecikme ): bu, bilgisayar sisteminin bazı harici olaylara hızlı bir şekilde yanıt vermesi gerektiğinde, gerçek zamanlı bir uygulamada özellikle önemlidir .
• Toplam sahip olma maliyeti : özellikle bir bilgisayar belirli bir algoritmaya ayrılmışsa.

Zaman

teori

Giriş verilerinin boyutunun bir fonksiyonu olarak çalışma süresinin bir tahminini elde etmek için tipik olarak zaman karmaşıklığı analizini kullanarak algoritmayı analiz edin . Sonuç normalde Big O notasyonu kullanılarak ifade edilir . Bu, özellikle büyük miktarda veri işlenecek olduğunda, algoritmaları karşılaştırmak için kullanışlıdır. Veri miktarı küçük olduğunda algoritma performansını karşılaştırmak için daha ayrıntılı tahminlere ihtiyaç duyulur, ancak bunun daha az önemli olması muhtemeldir. Paralel işlemeyi içeren algoritmaların analizi daha zor olabilir .

Uygulama

Bir algoritmanın kullanımını zamanlamak için bir kıyaslama kullanın . Birçok programlama dilinde, CPU zaman kullanımını sağlayan bir işlev bulunur . Uzun süre çalışan algoritmalar için geçen süre de ilgi çekici olabilir. Sonuçların genellikle birkaç test üzerinden ortalaması alınmalıdır.

Çalıştırma tabanlı profil oluşturma, donanım yapılandırmasına ve çok işlemli ve çoklu programlama ortamında aynı anda çalışan diğer programların veya görevlerin olasılığına karşı çok hassas olabilir .

Bu tür testler aynı zamanda belirli bir programlama dilinin, derleyicinin ve derleyici seçeneklerinin seçimine de bağlıdır, bu nedenle karşılaştırılan algoritmaların tümü aynı koşullar altında uygulanmalıdır.

Uzay

Bu bölüm, algoritma yürütülürken bellek kaynaklarının ( kayıtlar , önbellek , RAM , sanal bellek , ikincil bellek ) kullanımı ile ilgilidir. Yukarıdaki zaman analizine gelince , giriş verilerinin boyutu olarak bir fonksiyon olarak ihtiyaç duyulan çalışma zamanı belleğinin bir tahminini elde etmek için tipik olarak uzay karmaşıklığı analizini kullanarak algoritmayı analiz edin . Sonuç normalde Big O notasyonu kullanılarak ifade edilir .

Dikkate alınması gereken bellek kullanımının dört yönü vardır:

• Algoritma kodunu tutmak için gereken bellek miktarı.
• Giriş verileri için gereken bellek miktarı .
• Herhangi bir çıktı verisi için gereken bellek miktarı .
  • Sıralama gibi bazı algoritmalar genellikle giriş verilerini yeniden düzenler ve çıkış verileri için ek alana ihtiyaç duymaz. Bu özellik " yerinde " işlem olarak adlandırılır.
• Hesaplama sırasında çalışma alanı olarak ihtiyaç duyulan bellek miktarı.
  • Bu, yerel değişkenleri ve bir hesaplama sırasında çağrılan rutinler tarafından ihtiyaç duyulan herhangi bir yığın alanını içerir ; bu yığın alanı, özyinelemeli teknikleri kullanan algoritmalar için önemli olabilir .

Erken elektronik bilgisayarlar ve erken ev bilgisayarları, nispeten küçük miktarlarda çalışan belleğe sahipti. Örneğin, 1949 Elektronik Gecikme Depolama Otomatik Hesap Makinesi (EDSAC) maksimum 1024 17-bit kelimelik bir çalışma belleğine sahipken, 1980 Sinclair ZX80 başlangıçta 1024 8-bitlik çalışma belleği ile geldi. 2010'ların sonlarında, kişisel bilgisayarların 4 ila 32 GB RAM'e sahip olması tipik bir durumdu, bu da 300 milyon kat daha fazla bellek artışıydı.

Önbelleğe alma ve bellek hiyerarşisi

Mevcut bilgisayarlar nispeten büyük miktarda belleğe (muhtemelen Gigabayt) sahip olabilir, bu nedenle bir algoritmayı sınırlı miktarda belleğe sıkıştırmak, eskisinden çok daha az sorun yaratır. Ancak dört farklı bellek kategorisinin varlığı önemli olabilir:

• İşlemci kayıtları , en az depolama alanına sahip bilgisayar bellek teknolojilerinin en hızlısı. Modern bilgisayarlardaki çoğu doğrudan hesaplama, gerekirse önbelleğe, ana belleğe ve sanal belleğe güncellenmeden önce kayıtlardaki kaynak ve hedef işlenenlerle gerçekleşir. Bir işlemci çekirdeğinde , bir kayıt dosyası komut seti mimarisinde tanımlanan mimari kayıtlardan daha fazla fiziksel kayıt içerebilmesine rağmen, tipik olarak yüzlerce bayt veya daha az kayıt kullanılabilirliği vardır .
• Önbellek , bellek hiyerarşisinde bulunan en hızlı ikinci ve en küçük ikinci bellektir. Önbellekler CPU'larda, GPU'larda, sabit disk sürücülerinde ve harici çevre birimlerinde bulunur ve genellikle statik RAM'de uygulanır . Bellek önbellekleri çok düzeylidir ; düşük düzeyde daha yavaş, daha büyük ve tipik olarak ortak arasındaki işlemci çekirdeği içinde çok çekirdekli işlemci . Önbellekteki işlenenleri işlemek için, bir işlem biriminin verileri önbellekten alması, işlemi kayıtlarda gerçekleştirmesi ve verileri önbelleğe geri yazması gerekir. Bu karşılaştırılabilir (2-10 yaklaşık kat daha yavaş) CPU veya GPU'nun ile hızlarda çalışır aritmetik mantık birimine veya kayan nokta biriminde yer eğer L1 önbelleği . Orada bir L1 ise bu daha yavaş 10 kere olan önbellek Bayan ve alınan ve yazılmalıdır L2 önbellek vardır L2 önbellek Bayan ve bir geri çekilmesi gerekmektedir, eğer başka bir 10 kat daha yavaş ve L3 önbellek ise, mevcut.
• Ana fiziksel bellek çoğunlukla dinamik RAM'de (DRAM) uygulanır. Ana bellek, bir L3 CPU önbelleğinden çok daha büyüktür (genellikle ≈8 megabayta kıyasla gigabayt ), okuma ve yazma gecikmeleri tipik olarak 10-100 kat daha yavaştır. 2018 itibariyle, RAM, CPU veya GPU belleği olarak işlemcilerin çipinde giderek daha fazla uygulanmaktadır .
• Sanal bellek , çoğunlukla sabit disk gibi ikincil depolama açısından uygulanır ve RAM'deki bir değer için tipik olarak bir önbellek eksikliğinden yaklaşık 1000 kat daha yavaş, çok daha büyük depolama alanına ancak çok daha büyük gecikme süresine sahip bellek hiyerarşisinin bir uzantısıdır. . Başlangıçta, gerçekten mevcut olandan daha yüksek miktarda belleğin mevcut olduğu izlenimini yaratmak için motive edilmiş olsa da, sanal bellek, çağdaş kullanımda zaman-uzay değiş tokuşu ve sanal makinelerin kullanımına olanak sağlaması nedeniyle daha önemlidir . Ana bellekteki önbellek hatalarına sayfa hataları denir ve programlarda büyük performans cezalarına neden olur.

Bellek ihtiyacı önbelleğe sığacak bir algoritma, ana belleğe uyan bir algoritmadan çok daha hızlı olacak ve bu da sanal belleğe başvurması gereken bir algoritmadan çok daha hızlı olacaktır. Bu nedenle, önbelleğe duyarlı programlama ve veri hizalama gibi önbellek değiştirme ilkeleri yüksek performanslı bilgi işlem için son derece önemlidir . Sorunu daha da karmaşık hale getirmek için, bazı sistemler değişen etkin hızlara sahip üç adede kadar önbellek düzeyine sahiptir. Farklı sistemler, bu çeşitli bellek türlerinin farklı miktarlarına sahip olacaktır, bu nedenle algoritma belleği ihtiyaçlarının etkisi bir sistemden diğerine büyük ölçüde değişebilir.

Elektronik hesaplamanın ilk günlerinde, bir algoritma ve verileri ana belleğe sığmazsa, algoritma kullanılamazdı. Günümüzde sanal bellek kullanımı çok fazla bellek sağlıyor gibi görünüyor, ancak performans pahasına. Algoritma ve verileri önbelleğe sığarsa çok yüksek hızlar elde edilebilir; bu durumda alanı en aza indirmek, zamanı en aza indirmeye de yardımcı olacaktır. Buna yerellik ilkesi denir ve referansın yerelliği , uzamsal yerellik ve zamansal yerellik olarak alt bölümlere ayrılabilir . Önbelleğe tam olarak sığmayacak ancak referans yeri gösteren bir algoritma oldukça iyi performans gösterebilir.

Programlamanın mevcut durumunun eleştirisi

• David Mayıs bir FRS İngiliz bilgisayar bilimcisi ve halen Profesör ait Bilgisayar Bilimleri at Bristol Üniversitesi'ne ve kurucusu ve CTO ait XMOS Semiconductor , sorunlardan biri üzerinde bir güven olmasıdır inanmaktadır Moore yasasına yetersizlikleri çözmek için. Moore yasasına ( May yasası ) aşağıdaki gibi bir 'alternatif' geliştirdi :

Yazılım verimliliği her 18 ayda bir yarıya inerek Moore Yasasını dengeler

May, şöyle devam ediyor:

Her yerde bulunan sistemlerde, yürütülen talimatların yarıya indirilmesi pil ömrünü ikiye katlayabilir ve büyük veri kümeleri daha iyi yazılım ve algoritmalar için büyük fırsatlar sunar: N x N'den N x log(N)'ye kadar olan işlem sayısını azaltmak, N büyük olduğunda çarpıcı bir etkiye sahiptir. ... N = 30 milyar için, bu değişiklik 50 yıllık teknolojik gelişmeler kadar iyidir.

• Yazılım yazarı Adam N. Rosenburg, " Dijital bilgisayarın başarısızlığı " adlı blogunda , programlamanın mevcut durumunu "Yazılım olay ufkuna" yaklaşmak olarak tanımladı ( Douglas Adams'ın kitabında tarif ettiği hayali " ayakkabı olay ufkuna " atıfta bulunarak ). Otostopçunun Galaksi Rehberi kitabı). 1980'lerden bu yana 70 dB faktör verimlilik kaybı veya "malları teslim etme yeteneğinin yüzde 99,999999'u" olduğunu tahmin ediyor - " Arthur C. Clarke 2001'deki bilgisayar gerçekliğini kendi bilgisayarındaki HAL 9000 bilgisayarla karşılaştırdığında. 2001: A Space Odyssey kitabında , bilgisayarların ne kadar harika küçük ve güçlü olduklarına, ancak bilgisayar programlamanın ne kadar hayal kırıklığı yarattığına dikkat çekti".

En iyi algoritmalar için yarışmalar

Aşağıdaki yarışmalar, hakemler tarafından kararlaştırılan bazı keyfi kriterlere dayalı en iyi algoritmalar için girişleri davet ediyor:

• kablolu dergi

Ayrıca bakınız

• Algoritmaların analizi — bir algoritmanın ihtiyaç duyduğu kaynakların nasıl belirleneceği
• Aritmetik kodlama — verimli veri sıkıştırması için bir değişken uzunluklu entropi kodlama biçimi
• İlişkisel dizi kullanılarak daha etkin bir hale getirilebilir -a veri yapısı Patricia ağaçlar veya Judy dizileri
• Benchmark — tanımlı durumlarda karşılaştırmalı yürütme sürelerini ölçmek için bir yöntem
• En iyi, en kötü ve ortalama durum — üç senaryoda yürütme sürelerini tahmin etmeye yönelik hususlar
• İkili arama algoritması — sıralanmış dizileri aramak için basit ve verimli bir teknik
• Dal tablosu —talimat yolunun uzunluğunu, makine kodunun boyutunu (ve genellikle belleği de) azaltmak için bir teknik
• Programlama paradigmalarının karşılaştırılması — paradigmaya özgü performans değerlendirmeleri
• Derleyici optimizasyonu — derleyiciden türetilen optimizasyon
• Matematiksel işlemlerin hesaplama karmaşıklığı
• Hesaplamalı karmaşıklık teorisi
• Bilgisayar performansı — bilgisayar donanımı ölçümleri
• Veri sıkıştırma — iletim bant genişliğini ve disk depolamayı azaltır
• Veritabanı dizini — bir veritabanı tablosundaki veri alma işlemlerinin hızını artıran bir veri yapısı
• Entropi kodlaması — ikame için bir kriter olarak dizilerin oluşum sıklığını kullanarak verileri verimli bir şekilde kodlama
• Çöp toplama — kullanımdan sonra belleğin otomatik olarak boşaltılması
• Yeşil bilgi işlem — daha az kaynak tüketerek 'daha yeşil' teknolojileri uygulamaya yönelik bir hareket
• Huffman algoritması — verimli veri kodlaması için bir algoritma
• Yönetilen kod Performansını İyileştirme —Microsoft MSDN Kitaplığı
• Başvuru yeri — yerel olmayan bellek erişiminin neden olduğu önbelleğe alma gecikmelerinden kaçınmak için
• Döngü optimizasyonu
• Hafıza yönetimi
• Optimizasyon (bilgisayar bilimi)
• Performans analizi —çalışma zamanında bir algoritmanın gerçek performansını ölçme yöntemleri
• Gerçek zamanlı bilgi işlem — kritik zamanlı uygulamaların diğer örnekleri
• Çalışma zamanı analizi — beklenen çalışma zamanlarının tahmini ve bir algoritmanın ölçeklenebilirliği
• Eşzamanlı çoklu kullanım
• Sıralama algoritması § Algoritmaların karşılaştırılması
• Spekülatif yürütme veya İstekli yürütme
• Şube tahmini
• Süper iş parçacığı
  • Hiper iş parçacığı
• Dişli kod — sanal yöntem tablosuna veya dal tablosuna benzer
• Sanal yöntem tablosu — gönderim için dinamik olarak atanan işaretçilere sahip dal tablosu

Referanslar

Dış bağlantılar

• Boyer-Moore algoritmasının animasyonu ( Java Uygulaması )
• "Algoritmalar dünyamızı nasıl şekillendiriyor". Kevin Slavin'den bir TED (konferans) Konuşması.
• Liselerde algoritmik verimliliğe ilişkin kavram yanılgıları