Algoritmik verimlilik - Algorithmic efficiency

İçinde bilgisayar Bilimi, algoritmik verimlilik bir mülkiyettir algoritma sayısı ile ilgili olan hesaplama kaynakları algoritma tarafından kullanılır. Bir algoritma olmalı analiz edildi kaynak kullanımını belirlemek için ve bir algoritmanın verimliliği farklı kaynakların kullanımına bağlı olarak ölçülebilir. Algoritmik verimlilik, mühendisliğe benzer olarak düşünülebilir üretkenlik tekrar eden veya sürekli bir işlem için.

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

Örneğin, kabarcık sıralama ve zaman sıralaması ikisi de bir listeyi sıralamak için algoritmalar en küçüğünden en büyüğüne kadar öğe sayısı. Kabarcık sıralaması, listeyi kare içindeki öğelerin sayısıyla orantılı olarak sıralar (${ displaystyle scriptstyle {{ mathcal {O}} sol (n ^ {2} sağ)}}$, görmek Büyük O gösterimi ), ancak yalnızca az miktarda ekstra hafıza listenin uzunluğuna göre sabit olan (${ textstyle scriptstyle {{ mathcal {O}} sol (1 sağ)}}$). Timsort, listeyi zamanında sıralar linearitmik (bir miktarın logaritması ile orantılı) listenin uzunluğunda (${ textstyle scriptstyle { mathcal {O sol (n log n sağ)}}}$), ancak bir alan gereksinimi var doğrusal listenin uzunluğunda (${ textstyle scriptstyle { mathcal {O sol (n sağ)}}}$). 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, balonlu sıralama daha iyi bir seçimdir.

Arka fon

Zaman açısından verimliliğin önemi, Ada Lovelace 1843'te Charles Babbage mekanik analitik motoru:

"Hemen hemen her hesaplamada, süreçlerin birbirini izlemesi için çok çeşitli düzenlemeler mümkündür ve bir hesaplama motorunun amaçları doğrultusunda bunlar arasındaki seçimleri çeşitli hususlar etkilemelidir. Temel amaçlardan biri, azaltma eğiliminde olacak düzenlemeyi seçmektir. Hesaplamanın tamamlanması için gereken minimum süre "^[1]

erken elektronik bilgisayarlar hem işlemlerin hızı hem de kullanılabilir bellek miktarı ile ciddi şekilde sınırlıydı. Bazı durumlarda bir uzay-zaman değiş tokuşu, böylece a görev ya oldukça fazla çalışan bellek kullanan hızlı bir algoritma kullanılarak ya da çok az çalışma belleği kullanan daha yavaş bir algoritma kullanılarak işlenebilir. Mühendislik ödünleşimi, 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 (Kilobayt 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 gelişme asla marjinal olarak görülmez ve aynı bakış açısının yazılım mühendisliğinde de geçerli olması gerektiğine inanıyorum."^[2]

Genel Bakış

Hesaplama maliyeti olarak da bilinen kaynak tüketimi, kabul edilebilir bir düzeyde veya daha düşükse, bir algoritmanın verimli olduğu kabul edilir. Kabaca konuşursak, 'kabul edilebilir' şu anlama gelir: uygun bir bilgisayarda, tipik olarak bir işlevi giriş boyutunun. 1950'lerden beri bilgisayarlar hem mevcut hesaplama gücünde hem de kullanılabilir bellek miktarında çarpıcı artışlar gördüklerinden, şu anki kabul edilebilir seviyeler 10 yıl önce bile kabul edilemezdi. Aslında teşekkürler bilgisayar gücünün her 2 yılda bir yaklaşık ikiye katlanması, modern üzerinde kabul edilebilir derecede verimli olan görevler akıllı telefonlar ve gömülü sistemler endüstriyel için kabul edilemez derecede verimsiz olabilir sunucular 10 yıl önce.

Bilgisayar üreticileri sıklıkla, genellikle daha yüksek verim. 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, sadece daha hızlı bir bilgisayar satın almak olabilir. uyumlu mevcut bir bilgisayarla.

Bir algoritma tarafından kullanılan kaynakların ölçülmesinin birçok yolu vardır: en yaygın iki ölçü hız ve bellek kullanımıdır; diğer önlemler arasında iletim hızı, geçici disk kullanımı, uzun süreli disk kullanımı, güç tüketimi, toplam sahip olma maliyeti, Tepki Süresi dış uyaranlara, vb. Bu önlemlerin çoğu, algoritmaya girdinin boyutuna, yani işlenecek veri miktarına bağlıdır. Ayrıca verilerin düzenlenme şekline de bağlı olabilirler; örneğin, bazıları sıralama algoritmaları önceden sıralanmış veya ters sırada sıralanmış veriler üzerinde kötü performans gösterir.

Uygulamada, 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ıları verildiği gibi, bir algoritmanın uygulanma şekli de gerçek verimlilik üzerinde önemli bir etkiye sahip olabilir, ancak bunun birçok yönü aşağıdakilerle ilgilidir: optimizasyon sorunlar.

Teorik analiz

Teorik olarak algoritmaların analizi Normal uygulama, asimptotik anlamda karmaşıklıklarını tahmin etmektir. Kaynak tüketimini veya "karmaşıklığı" açıklamak için en yaygın kullanılan gösterim Donald Knuth 's Büyük O gösterimi, bir algoritmanın karmaşıklığını girdinin boyutunun bir fonksiyonu olarak temsil eder ${ textstyle scriptstyle n}$. Big O notasyonu bir asimptotik fonksiyon karmaşıklığının ölçüsü, burada ${ textstyle scriptstyle {f sol (n sağ) , = , { mathcal {O}} sol (g sol (n sağ) sağ)}}$ kabaca, bir algoritma için zaman gereksiniminin orantılı olduğu anlamına gelir ${ displaystyle scriptstyle {g sol (n sağ)}}$, ihmal düşük mertebeden terimler daha az katkıda bulunan ${ displaystyle scriptstyle {g sol (n sağ)}}$ olarak işlevin büyümesine ${ displaystyle scriptstyle n}$ keyfi olarak büyür. Bu tahmin yanıltıcı olabilir ${ textstyle scriptstyle n}$ küçüktür, ancak genel olarak yeterince doğrudur ${ textstyle scriptstyle n}$ gösterim asimptotik olduğundan büyüktür. Örneğin, kabarcıklı sıralama daha hızlı olabilir sıralamayı birleştir sadece birkaç öğe sıralanacağı zaman; ancak her iki uygulama da küçük bir liste için performans gereksinimlerini karşılayacaktır. Tipik olarak, programcılar, ölçek verimli bir şekilde büyük girdi boyutlarına ve birleştirme sıralaması, çoğu veri yoğun programda karşılaşılan uzunluk listeleri için balonlu sıralamaya tercih edilir.

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

Gösterim	İsim	Örnekler
${ displaystyle { mathcal {O}} (1) ,}$	sabit	Sıralanmış bir ölçüm listesinden medyanı bulma; Sabit boyut kullanma arama tablosu; Uygun bir Özet fonksiyonu bir öğeyi aramak için.
${ displaystyle { mathcal {O}} ( log {n}) ,}$	logaritmik	Sıralanmış bir dizide bir öğeyi bir Ikili arama veya dengeli bir arama ağaç yanı sıra bir Binom yığını.
${ displaystyle { mathcal {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 öğeyi bulmak; İki ekleniyor n-bit tamsayılar dalgalanma taşıma.
${ displaystyle { mathcal {O}} (n log n) ,}$	linearitmik, loglinear veya quasilinear	Yapmak Hızlı Fourier dönüşümü; yığın, hızlı sıralama (en iyi ve ortalama durum ) veya sıralamayı birleştir
${ displaystyle { mathcal {O}} (n ^ {2}) ,}$	ikinci dereceden	Çarpma iki nbasamaklı sayılar basit bir algoritma; kabarcık sıralama (en kötü durum veya saf uygulama), Kabuk sıralaması, hızlı sıralama (En kötü durumda ), seçim sıralaması veya ekleme sıralaması
${ displaystyle { mathcal {O}} (c ^ {n}), ; c> 1}$	üstel	Optimal olanı bulmak (yaklaşık ) çözüm seyyar satıcı sorunu kullanma dinamik program; iki mantıksal ifadenin eşdeğer olup olmadığını belirleme kullanma kaba kuvvet arama

Kıyaslama: performans ölçümü

Yazılımın yeni sürümleri için veya rakip sistemlerle karşılaştırmalar sağlamak için, kıyaslamalar bazen algoritmaların göreceli performansının ölçülmesine yardımcı olan kullanılır. Eğer yeni sıralama algoritması örneğin, herhangi bir işlevsel iyileştirme göz önünde bulundurularak, bilinen verilerle en azından daha önce olduğu gibi verimli olmasını sağlamak için öncekilerle karşılaştırılabilir. Karşılaştırmalar, alternatif tedarikçilerden alınan çeşitli ürünleri karşılaştırırken, işlevsellik ve performans açısından hangi ürünün kendi özel gereksinimlerine en iyi şekilde uyacağını tahmin etmek için müşteriler tarafından kullanılabilir. Örneğin, ana bilgisayar dünya belirli tescilli çeşit gibi bağımsız yazılım şirketlerinin ürünleri Eşitleme gibi büyük tedarikçilerin ürünleriyle rekabet etmek IBM hız için.

Bazı kıyaslamalar, örneğin çeşitli derlenmiş ve yorumlanmış dillerin göreceli hızını karşılaştıran bir analiz üretmek için fırsatlar sağlar.^[3][4]ve Bilgisayar Dili Benchmark Oyunu çeşitli programlama dillerinde tipik programlama problemlerinin uygulamalarının performansını karşılaştırır.

Hatta yaratmak "kendin Yap "Kıyaslamalar, kullanıcı tanımlı çeşitli ölçütler kullanarak farklı programlama dillerinin göreceli performansını gösterebilir. Christopher W. Cowell-Shah'ın örnekle gösterdiği" Dokuz dil performansı özetinin "gösterdiği gibi, bu oldukça basittir.^[5]

Uygulama endişeleri

Uygulama sorunları, programlama dili seçimi veya algoritmanın gerçekte kodlanma şekli gibi verimlilik üzerinde de bir etkiye sahip olabilir.^[6] veya bir seçim derleyici belirli bir dil için veya derleme seçenekleri kullanılmış, hatta işletim sistemi Kullanılan. Çoğu durumda, bir çevirmen bir derleyici tarafından uygulanan bir dilden çok daha yavaş olabilir.^[3] İle ilgili makalelere bakın tam zamanında derleme ve yorumlanmış diller.

Zaman veya mekan sorunlarını etkileyebilecek, ancak programcının kontrolü dışında olabilecek başka faktörler de vardır; bunlar şunları içerir veri hizalama, veri ayrıntı düzeyi, önbellek yeri, önbellek tutarlılığı, çöp toplama, öğretim düzeyinde paralellik, çoklu iş parçacığı (donanım veya yazılım düzeyinde), eşzamanlı çoklu görev, ve altyordam aramalar.^[7]

Bazı işlemcilerin şu özellikleri vardır: vektör işleme izin veren birden çok işlenen üzerinde çalışmak için tek komut; bir programcı veya derleyicinin bu yetenekleri kullanması kolay olabilir veya olmayabilir. Sıralı işleme için tasarlanan algoritmaların, aşağıdakilerden yararlanmak için tamamen yeniden tasarlanması gerekebilir. paralel işlem veya kolayca yeniden yapılandırılabilirler. Gibi paralel ve dağıtılmış hesaplama son zamanlarda önemi artmak 2010'lar, verimli hale getirmek için daha fazla yatırım yapılıyor yüksek seviye API'ler paralel ve dağıtılmış bilgi işlem sistemleri için CUDA, TensorFlow, Hadoop, OpenMP ve MPI.

Programlamada ortaya çıkabilecek diğer bir sorun, işlemcilerin aynı komut seti (gibi x86-64 veya KOL ) bir talimatı farklı şekillerde uygulayabilir, böylece bazı modellerde nispeten hızlı olan talimatlar diğer modellerde nispeten yavaş olabilir. Bu genellikle derleyicileri optimize etme, belirli konularda büyük miktarda bilgiye sahip olması gerekir İşlemci ve performans için bir programı en iyi duruma getirmek için derleme hedefinde bulunan diğer donanımlar. Olağanüstü bir durumda, bir derleyici, benzemeye çalışmak derleme hedef platformunda desteklenmeyen talimatlar, kodunu oluşturun veya bağlantı harici kütüphane çağrısı doğal olarak desteklense ve diğer platformlarda donanımda daha verimli olsa bile, o platformda başka şekilde hesaplanamayan bir sonuç üretmek. Bu genellikle gömülü sistemler göre kayan nokta aritmetiği nerede küçük ve düşük güç mikrodenetleyiciler genellikle kayan nokta aritmetiği için donanım desteğinden yoksundur ve bu nedenle kayan nokta hesaplamaları üretmek için hesaplama açısından pahalı yazılım rutinleri gerektirir.

Kaynak kullanım ölçüleri

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

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

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

Gücü bir pille sağlanan bilgisayarlar için (ör. dizüstü bilgisayarlar ve akıllı telefonlar ) veya çok uzun / büyük hesaplamalar için (ör. süper bilgisayarlar ), 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üncelleme]}güç tüketimi, her türden ve tüm ölçeklerdeki hesaplama görevleri için önemli bir metrik olarak büyüyor. gömülü nesnelerin interneti cihazlar çip üzerinde sistem cihazlar sunucu çiftlikleri. Bu eğilim genellikle şu şekilde anılır: çevreci Bilişim.

Daha az yaygın hesaplama verimliliği ölçüleri 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 resim veya görüntünün görüntülenmesi (ör. Google logosu ), "Google" metni için altı bayt iletmeye kıyasla on binlerce baytın (bu durumda 48K) aktarılmasına neden olabilir. Bu için önemlidir G / Ç bağlantılı bilgi işlem görevler.
• Dış alan: bir diskte veya başka bir harici bellek aygıtında gereken 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, özellikle bir gerçek zamanlı uygulama bilgisayar sistemi ne zaman bazı harici olaylara hızlı yanıt ver.
• Toplam sahip olma maliyeti: özellikle bir bilgisayar belirli bir algoritmaya adanmışsa.

Zaman

Teori

Analiz et algoritma, tipik olarak zaman karmaşıklığı giriş verilerinin boyutunun bir fonksiyonu olarak çalışma süresinin bir tahminini elde etmek için analiz. Sonuç normalde şu şekilde ifade edilir: Büyük O gösterimi. Bu, özellikle büyük miktarda veri işlenecekse, algoritmaları karşılaştırmak için kullanışlıdır. Veri miktarı az olduğunda algoritma performansını karşılaştırmak için daha ayrıntılı tahminlere ihtiyaç vardır, ancak bu muhtemelen daha az önemli olacaktır. Paralel işlemeyi içeren algoritmalar olabilir analiz etmesi daha zor.

Uygulama

Kullanın kıyaslama zaman zaman bir algoritmanın kullanımı. Birçok programlama dilinin, aşağıdakileri sağlayan bir işlevi vardır: CPU zaman kullanımı. 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 aynı anda çalışan diğer programların veya görevlerin olasılığına karşı çok hassas olabilir. çoklu işlem ve çoklu programlama çevre.

Bu tür testler ayrıca büyük ölçüde belirli bir programlama dili, derleyici ve derleyici seçeneklerinin seçimine 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 bellek kaynaklarının kullanımıyla ilgilidir (kayıtlar, önbellek, Veri deposu, sanal bellek, Ikincil bellek ) algoritma yürütülürken. Yukarıdaki zaman analizine gelince, analiz etmek algoritma, tipik olarak uzay karmaşıklığı Girdi verilerinin boyutu olarak bir fonksiyon olarak ihtiyaç duyulan çalışma zamanı belleğinin bir tahminini elde etmek için analiz. Sonuç normalde şu şekilde ifade edilir: Büyük O gösterimi.

Bellek kullanımının dikkate alınması gereken dört yönü vardır:

• Algoritma kodunu tutmak için gereken bellek miktarı.
• İçin gereken bellek miktarı giriş verileri.
• Herhangi biri için gereken bellek miktarı çıktı verileri.
  • Sıralama gibi bazı algoritmalar genellikle giriş verilerini yeniden düzenleyin ve çıktı verileri için herhangi bir ek alana ihtiyaç duymaz. Bu özelliğe "yerinde " operasyon.
• Hesaplama sırasında çalışma alanı olarak ihtiyaç duyulan bellek miktarı.
  • Bu içerir yerel değişkenler Ve herhangi biri yığın alanı gerekli tarafından rutinler çağrıldı bir hesaplama sırasında; bu yığın alanı, kullanan algoritmalar için önemli olabilir. yinelemeli teknikleri.

İlk elektronik bilgisayarlar ve ilk ev bilgisayarları nispeten küçük miktarlarda çalışma belleğine sahipti. Örneğin, 1949 Elektronik Gecikme Depolama Otomatik Hesaplayıcı (EDSAC), 1024 17 bitlik maksimum çalışma belleğine sahipken, 1980 Sinclair ZX80 başlangıçta 1024 8 bitlik çalışma belleği ile geldi. Geç 2010'lar için tipiktir kişisel bilgisayarlar 4 ile 32 arasında olması GB RAM, 300 milyon katın üzerinde bir bellek artışı.

Önbelleğe alma ve bellek hiyerarşisi

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

• İşlemci kayıtları, en az depolama alanına sahip en hızlı bilgisayar bellek teknolojileri. Modern bilgisayarlardaki çoğu doğrudan hesaplama, gerekirse önbelleğe, ana belleğe ve sanal belleğe güncellenmeden önce yazmaçlardaki kaynak ve hedef işlenenlerle gerçekleşir. Bir işlemci çekirdeği genellikle yüzlerce bayt veya daha az sayıda kayıt kullanılabilirliği vardır, ancak kayıt dosyası daha fazla fiziksel kayıt içerebilir mimari komut kümesi mimarisinde tanımlanan yazmaçlar.
• Ön bellek bellek hiyerarşisinde bulunan ikinci en hızlı ve ikinci en küçük bellektir. Önbellekler CPU'larda, GPU'larda, sabit disk sürücülerinde ve harici çevre birimlerinde bulunur ve tipik olarak statik RAM. Bellek önbellekleri çok düzeylidir; daha düşük seviyeler daha büyük, daha yavaş ve tipik olarak paylaşılan arasında işlemci çekirdekleri içinde çok çekirdekli işlemciler. Önbellekteki işlenenleri işlemek için, bir işleme ünitesi verileri önbellekten almalı, işlemi kayıtlarda gerçekleştirmeli ve verileri önbelleğe geri yazmalıdır. Bu, CPU veya GPU'larla karşılaştırılabilir hızlarda (yaklaşık 2-10 kat daha yavaş) çalışır. aritmetik mantık Birimi veya kayan nokta birimi eğer içinde L1 önbelleği.^[8] Bir L1 varsa yaklaşık 10 kat daha yavaştır önbellekte eksik ve buradan alınmalı ve L2 önbelleği ve eğer bir L2 önbelleği eksikse ve bir L2 önbelleğinden geri alınması gerekiyorsa 10 kat daha yavaş L3 önbelleği varsa.
• Ana fiziksel bellek çoğunlukla dinamik RAM (DRAM). Ana hafıza çok daha büyüktür (tipik olarak gigabayt ≈8 ile karşılaştırıldığında megabayt ) tipik olarak 10-100 kat daha yavaş okuma ve yazma gecikmeleri ile bir L3 CPU önbelleğinden.^[8] 2018 itibariyle^{[Güncelleme]}RAM giderek daha fazla uygulanıyor çip üzerinde işlemci olarak, CPU veya GPU belleği.
• Sanal bellek çoğu zaman açısından uygulanır ikincil depolama gibi hard disk ve bir uzantısıdır bellek hiyerarşisi çok daha büyük depolama alanına sahip ancak çok daha büyük gecikme süresine sahip, tipik olarak bir önbellekte eksik RAM'deki bir değer için.^[8] 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 daha önemlidir. zaman-uzay değiş tokuşu ve kullanımının sağlanması Sanal makineler.^[8] Ana bellekteki önbellek eksiklikleri çağrılır sayfa hataları ve programlarda büyük performans cezalarına neden olur.

Bellek ihtiyacı ön belleğe sığacak bir algoritma, ana belleğe uyan bir algoritmadan çok daha hızlı olacaktır ve bu da sanal belleğe başvurmak zorunda olan bir algoritmadan çok daha hızlı olacaktır. Bu nedenle, önbellek değiştirme politikaları yüksek performanslı bilgi işlem için son derece önemlidir önbelleğe duyarlı programlama ve veri hizalama. Sorunu daha da karmaşık hale getirmek için, bazı sistemlerde değişen etkili hızlarda üç seviyeye kadar önbellek vardır. Farklı sistemler bu çeşitli bellek türlerinden farklı miktarlara 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, o zaman algoritma kullanılamazdı. Günümüzde sanal bellek kullanımı, çok fazla bellek sağlıyor gibi görünmektedir, ancak bu performans pahasına. Bir algoritma ve verileri önbelleğe sığacaksa, çok yüksek hız elde edilebilir; bu durumda alanı en aza indirmek, zamanı en aza indirmeye de yardımcı olacaktır. Bu denir yerellik ilkesi ve alt bölümlere ayrılabilir referans yeri, mekansal yerellik ve zamansal yerellik. Önbelleğe tam olarak sığmayan, ancak referans yerelliği sergileyen bir algoritma makul ölçüde iyi çalışabilir.

Mevcut programlama durumunun eleştirisi

• David May FRS a ingiliz bilgisayar uzmanı ve şu anda Profesör nın-nin Bilgisayar Bilimi -de Bristol Üniversitesi ve kurucu ve CTO nın-nin XMOS Yarı İletken, sorunlardan birinin güven duyulması olduğuna inanıyor Moore yasası verimsizlikleri çözmek için. Moore yasasına bir 'alternatif' geliştirdi (Mayıs kanunu ) aşağıdaki gibidir:^[9]

Moore Yasasını telafi ederek her 18 ayda bir yazılım verimliliği yarıya iner

Mayıs şunu belirtiyor:

Her yerde bulunan sistemlerde, yürütülen talimatların yarıya indirilmesi pil ömrünü iki katına çıkarabilir ve büyük veri kümeleri, daha iyi yazılım ve algoritmalar için büyük fırsatlar sunar: İşlem sayısını N x N'den N x log (N) 'ye düşürmek, N büyük olduğunda dramatik 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 blogunda "Dijital bilgisayarın arızası", mevcut programlama durumunu" Yazılım olay ufkuna "yakın olarak tanımladı (hayali olanı kastederek"ayakkabı olay ufku" Tarafından tanımlanan Douglas Adams onun içinde Otostopçunun Galaksi Rehberi kitap^[10]). 1980'lerden beri 70 dB faktör verimlilik kaybı veya "malları teslim etme kabiliyetinin yüzde 99,99999'u" olduğunu tahmin ediyor - " Arthur C. Clarke 2001'deki bilgi işlem gerçekliğini bilgisayarla karşılaştırdı HAL 9000 kitabında 2001: Bir Uzay Macerası, bilgisayarların ne kadar harika küçük ve güçlü olduklarını, ancak bilgisayar programlamanın ne kadar hayal kırıklığı yarattığını belirtti. "

En iyi algoritmalar için yarışmalar

Aşağıdaki yarışmalar, jüri tarafından karar verilen bazı rastgele kriterlere göre en iyi algoritmalar için girişleri davet etmektedir:

• Kablolu dergi^[11]

Ayrıca bakınız

• Algoritmaların analizi - bir algoritmanın ihtiyaç duyduğu kaynaklar nasıl belirlenir
• Aritmetik kodlama -bir çeşit değişken uzunluk entropi kodlaması verimli veri sıkıştırma için
• İlişkisel dizi —Kullanılarak daha verimli hale getirilebilecek bir veri yapısı Patricia ağaçları veya Judy dizileri
• Kıyaslama - belirli 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ürelerinin tahmin edilmesine ilişkin hususlar
• İkili arama algoritması — Sıralı dizileri aramak için basit ve etkili bir teknik
• Dal tablosu - talimat yolu uzunluğunu, boyutunu azaltmak için bir teknik makine kodu, (ve çoğu zaman hafıza)
• Programlama paradigmalarının karşılaştırılması —Paradigmaya özel performans konuları
• Derleyici optimizasyonu - derleyiciden türetilmiş 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 depolamasını azaltmak
• Veritabanı dizini - bir veritabanı tablosunda veri alma işlemlerinin hızını artıran bir veri yapısı
• Entropi kodlaması - yerine koyma ölçütü olarak dizelerin oluşum sıklığını kullanarak verileri verimli bir şekilde kodlamak
• Çöp toplama - kullanımdan sonra hafızanın otomatik olarak boşaltılması
• Çevreci Bilişim - daha az kaynak tüketerek daha 'çevreci' teknolojileri uygulamaya yönelik bir hamle
• Huffman algoritması - verimli veri kodlaması için bir algoritma
• Yönetilen kod Performansını İyileştirme —Microsoft MSDN Kitaplığı
• Başvuru yeri - kaçınmak için Önbelleğe almak yerel olmayan bellek erişiminin neden olduğu gecikmeler
• Döngü optimizasyonu
• Hafıza yönetimi
• Optimizasyon (bilgisayar bilimi)
• Performans analizi —Bir algoritmanın çalışma zamanında gerçek performansını ölçme yöntemleri
• Gerçek zamanlı bilgi işlem —Zaman açısından kritik uygulamalara ilişkin diğer örnekler
• Çalışma zamanı analizi - beklenen çalışma sürelerinin tahmini ve bir algoritmanın ölçeklenebilirliği
• Eşzamanlı çoklu okuma
• Sıralama algoritması § Algoritmaların karşılaştırılması
• Spekülatif uygulama veya Hevesli yürütme
• Dal tahmini
• Süper iş parçacığı
  • Hiper iş parçacığı
• Dişli kod - sanal yöntem tablosu veya dal tablosuna benzer
• Sanal yöntem tablosu - dağıtım için dinamik olarak atanmış işaretçiler içeren dal tablosu

Referanslar

Dış bağlantılar

• Boyer-Moore algoritmasının animasyonu (Java Uygulaması )
• "Algoritmalar dünyamızı nasıl şekillendiriyor". Bir TED (konferans) Kevin Slavin tarafından konuşun.
• Liselerde algoritmik verimlilikle ilgili yanılgılar