Tek geçişli algoritma - One-pass algorithm
Hesaplamada, tek geçişli algoritma veya tek geçişli algoritma , girişini tam olarak bir kez okuyan bir akış algoritmasıdır . Bunu, sınırsız arabelleğe alma olmadan öğeleri sırayla işleyerek yapar ; girdi arabelleğine bir blok okur , onu işler ve işlemin her adımı için sonucu bir çıktı arabelleğine taşır. Tek geçişli bir algoritma genellikle O ( n ) (bkz. 'büyük O' notasyonu ) süresi ve O ( n ) depolamadan (tipik olarak O (1)) daha kısa gerektirir; burada n , girdinin boyutudur. Tek geçişli bir algoritmanın bir örneği, Sondik kısmen gözlemlenebilir Markov karar sürecidir .
Tek geçişli algoritmalarla çözülebilen örnek problemler
Giriş olarak herhangi bir liste verildiğinde:
- Elemanların sayısını sayın.
Bir numara listesi verildi:
- Bul k en büyük veya en küçük elemanları, k önceden verilmiş.
- Listenin elemanlarının toplamını , ortalamasını , varyansını ve standart sapmasını bulun . Varyansı hesaplamak için Algoritmalar'a da bakın .
Önceden verilen , k sembollü bir alfabeden bir sembol listesi verildi.
- Girişte her sembolün kaç kez göründüğünü sayın.
- En çok veya en az sıklıkta bulunan öğeleri bulun.
- Listeyi sembollere göre sıralayın (simge sayısı sınırlı olduğu için mümkündür).
- Belirli bir sembolün iki görünümü arasındaki maksimum boşluğu bulun.
Tek geçişli algoritmalarla çözülemeyen örnek problemler
Giriş olarak herhangi bir liste verildiğinde:
- Bul n (liste daha az olduğunu veya raporu inci ucundan elemanı n elemanları).
- Listenin orta öğesini bulun. Ancak, bu iki geçişle çözülebilir: Geçiş 1 öğeleri sayar ve geçiş 2 ortadakini seçer.
Bir numara listesi verildi:
- Ortancayı bulun .
- Modları bulun (Bu, sınırlı bir alfabeden en sık kullanılan sembolü bulmakla aynı şey değildir).
- Listeyi sıralayın.
- Ortalamadan büyük veya küçük olan öğeleri sayın . Ancak bu, sabit bellekte iki geçişle yapılabilir: Geçiş 1 ortalamayı bulur ve geçiş 2 sayımı yapar.
Yukarıdaki iki geçişli algoritmalar hala akış algoritmalarıdır, ancak tek geçişli algoritmalar değildir.
Referanslar
- ^ Schweikardt, Nicole. "Tek Geçişli Algoritma" (PDF) . 2021-07-01 alındı .
- ^ Pollett, Chris (2005-03-14). "Bir ve İki Geçişli Algoritmalar" (PDF) . 2021-07-01 alındı .
- ^ Schweikardt, Nicole (2009), LIU, LING; ÖZSU, M. TAMER (ed.), "One-Pass Algorithm" , Encyclopedia of Database Systems , Boston, MA: Springer US, s. 1948–1949, doi : 10.1007/978-0-387-39940-9_253 , ISBN 978-0-387-39940-9, alındı 2021-04-13
- ^ "Sondik'in Tek Geçişli Algoritması" . www.pomdp.org .
 |
Bu bilgisayar bilimi makale bir taslaktır . Vikipedi'yi genişleterek yardımcı olabilirsiniz . |