it-swarm-tr.com

Özyinme veya yineleme?

Her ikisinin de aynı amaca hizmet edebileceği algoritmalarda özyineleme yerine bir döngü veya tersi kullanılırsa performans çarpması var mı? Örn: Verilen dizginin bir palindrom olup olmadığını kontrol edin. Basit bir yineleme algoritmasının faturaya ne zaman uyabileceğini göstermek için özyinelemeyi kullanan birçok programcı gördüm. Derleyici ne kullanılacağına karar vermede hayati bir rol oynuyor mu?

210
Omnipotent

Özyinelemeli fonksiyonun kuyruk özyinelemeli (son satır özyinelemeli çağrıdır) olmasına bağlı olarak özyinelemenin daha pahalı olması mümkündür. Kuyruk özyineleme derleyici tarafından tanınmalı ve yinelemeli muadili için en iyi duruma getirilmelidir (özlü tutarken kodunuzda açık bir şekilde uygulayın).

Algoritmayı, kodu birkaç ay veya yıl içinde sürdürmesi gereken en basit ve fakir enayi (kendin ya da başkası olabilir) için en net ve en açık olan şekilde yazardım. Performans sorunlarıyla karşılaşırsanız, kodunuzu girin ve ardından ve yalnızca o zaman yinelemeli bir uygulamaya geçerek optimizasyona bakın. belleğe alma ve dinamik programlama içine bakmak isteyebilirsiniz.

176
Paul Osborne

Döngüler, programınız için bir performans kazancı sağlayabilir. Özyineleme, programlayıcınız için bir performans kazancı sağlayabilir. Durumunuzda hangisinin daha önemli olduğunu seçin!

309
Leigh Caldwell

Özyinelemenin yinelemeyle karşılaştırılması, yıldız uçlu bir tornavidanın düz uçlu bir tornavidayla karşılaştırılması gibidir. Çoğunlukla düz başlı herhangi bir phillips başlı vidayı çıkarabilirsiniz, ancak bu vida için tasarlanan tornavidayı kullanmanız daha kolay olur mu?

Bazı algoritmalar tasarlandıkları için kendilerini özyinelemeye ödünç veriyorlar (Fibonacci dizileri, ağaca benzer bir yapıyı geçiyorlar, vb.). Özyineleme algoritmayı daha özlü ve anlaşılır hale getirir (bu nedenle paylaşılabilir ve tekrar kullanılabilir).

Ayrıca, bazı özyinelemeli algoritmalar, onları yineleyen kardeşlerinden daha verimli yapan "Tembel Değerlendirme" yi kullanır. Bu, döngünün her çalışması yerine yalnızca ihtiyaç duyduklarında pahalı hesaplamaları yaptıkları anlamına gelir.

Başlamanız için bu yeterli olmalı. Ben de sizin için bazı makaleler ve örnekler bulacağım.

Bağlantı 1: Haskel'e karşı _ PHP (Yinelemeye Karşı Yineleme)

Programcının PHP kullanarak büyük bir veri setini işlemesi gerektiği bir örnek. Haskel'de özyineleme kullanarak ne kadar kolay başa çıkabileceğini gösterir, ancak PHP aynı yöntemi başarmanın kolay bir yolu olmadığından, sonucu elde etmek için yinelemeyi kullanmak zorunda kaldı.

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

Bağlantı 2: Mastering Recursion

Özyinelemenin kötü itibarının çoğu, zorunlu dillerdeki yüksek maliyetler ve verimsizlikten kaynaklanmaktadır. Bu makalenin yazarı, özyinelemeli algoritmaları daha hızlı ve daha verimli hale getirmek için nasıl optimize edileceği hakkında konuşur. Aynı zamanda geleneksel bir döngüyü özyinelemeli bir işleve nasıl dönüştüreceğini ve kuyruk ucu özyinelemesini kullanmanın faydalarını anlatıyor. Kapanış sözleri, sanırım kilit noktalarımdan bazılarını özetledi:

"özyinelemeli programlama, programcıya hem bakımı kolay hem de mantıksal olarak tutarlı bir şekilde kod düzenlemek için daha iyi bir yol sağlar."

https://developer.ibm.com/articles/l-recurs/

Bağlantı 3: Özyineleme döngüden daha hızlı mı? (Cevap)

İşte sizinkine benzer bir yığın akışı sorusunun cevabına bir link. Yazar, özyinelemeyle ya da döngüle ilişkilendirilen ölçütlerin birçoğunun çok dile özgü olduğunu belirtmektedir. Zorunlu diller tipik olarak bir döngü kullanarak daha hızlıdır ve işlevsel diller için özyinelemeli ya da tam tersi daha yavaştır. Sanırım bu bağlantıdan almamız gereken asıl nokta, soruyu bir dilde agnostik/durum kör anlamında cevaplamanın çok zor olduğudur.

Özyineleme, döngüden daha hızlı mıdır?

76
Swift

Her bir özyinelemeli çağrı genellikle yığına basılması gereken bir bellek adresi gerektirdiğinden, özyineleme daha maliyetlidir, böylece program daha sonra bu noktaya geri dönebilir.

Yine de, özyinelemenin döngülerden çok daha doğal ve okunabilir olduğu birçok durum vardır - ağaçlarla çalışırken olduğu gibi. Bu gibi durumlarda özyinelemeye bağlı kalmanızı tavsiye ederim.

16
Doron Yaacoby

Genellikle, bir kişi performans cezasının diğer yöne uzanmasını bekler. Özyinelemeli aramalar ekstra yığın çerçevelerin oluşturulmasına yol açabilir; Bunun için ceza değişir. Ayrıca, Python gibi bazı dillerde (daha doğrusu, bazı dillerin bazı uygulamalarında ...), yinelemeli olarak belirleyeceğiniz görevler için kolayca maksimum değeri bulmak gibi yığın sınırlarıyla karşılaşabilirsiniz. Bir ağaç veri yapısı. Bu gibi durumlarda, gerçekten döngü ile sopa istiyorum.

İyi özyinelemeli işlevler yazmak, kuyruk özyinelemelerini optimize eden bir derleyiciniz olduğunu varsayarsak, performans cezalarını bir miktar azaltabilir (Ayrıca, işlevin gerçekten özyinelemeli olduğundan emin olmak için iki kez kontrol --- bu, birçok kişinin hata yaptığı şeylerden biridir. üzerinde.)

"Edge" kasaların dışında (yüksek performanslı bilgi işlem, çok büyük özyineleme derinliği vb.), Niyetinizi en açık şekilde ifade eden, iyi tasarlanmış ve korunabilir bir yaklaşım benimsemek tercih edilir. Yalnızca bir gereksinimi belirledikten sonra optimize edin.

11
zweiterlinde

Özyineleme, çokl, daha küçük parçalara bölünebilecek problemler için yinelemeden daha iyidir.

Örneğin, özyinelemeli bir Fibonnaci algoritması yapmak için, fib (n) 'i fib (n-1) ve fib (n-2)' ye parçalar ve her iki parçayı hesaplarsınız. Yineleme, yalnızca tek bir işlevi tekrar tekrar tekrarlamanıza izin verir.

Ancak, Fibonacci aslında kırılmış bir örnek ve yinelemenin aslında daha verimli olduğunu düşünüyorum. Fib (n) = fib (n-1) + fib (n-2) ve fib (n-1) = fib (n-2) + fib (n-3) olduğuna dikkat edin. fib (n-1) iki kere hesaplanır!

Daha iyi bir örnek, bir ağaç için özyinelemeli bir algoritmadır. Ana düğümü analiz etme sorunu çokl her bir alt düğümü analiz etme konusundaki daha küçük problemlere bölünebilir. Fibonacci örneğinin aksine, daha küçük problemler birbirinden bağımsızdır.

Yani evet - özyineleme, birden çok, daha küçük, bağımsız, benzer sorunlara bölünebilecek problemler için yinelemeden daha iyidir.

8
Ben

Bir yöntemi çağırmak, herhangi bir dilde çok fazla hazırlık gerektirdiğinden, özyinelemeyi kullanırken performansınız düşmektedir: arama kodu bir dönüş adresi gönderir, arama parametreleri, işlemci kayıtları gibi diğer bazı içerik bilgileri bir yere kaydedilebilir ve iade zamanında çağrılan yöntem, daha sonra arayan tarafından alınan bir dönüş değeri gönderir ve daha önce kaydedilmiş olan içerik bilgileri geri yüklenir. yinelemeli ve özyinelemeli bir yaklaşım arasındaki performans farkı bu işlemlerin gerçekleştiği zaman yatmaktadır.

Bir uygulama bakış açısıyla, çağıran bağlamı işlemek için geçen sürenin, yönteminizin yürütülmesi için geçen süreyle karşılaştırılabilir olduğunda farkı gerçekten fark etmeye başlarsınız. Özyinelemeli yönteminizin çağıran içerik yönetimi bölümünün çalıştırılması daha uzun sürerse, kod genellikle daha okunaklı ve anlaşılması kolay olduğundan ve performans kaybını farketmeyeceğinizden yinelemeli yoldan geçin. Aksi halde, verimlilik nedenleriyle tekrarlanır.

7
entzik

Java öğesindeki kuyruk özyinelemesinin şu anda optimize edilmediğine inanıyorum. Detaylar, b LtU ve ilgili linklerle ilgili tartışmalara serpiştirilir. gelecek sürüm 7'de bir özellik olabilir ancak belirli kareler eksik olacağından Yığın Muayenesi ile birleştirildiğinde bazı zorluklar ortaya çıkar. Java 2'den bu yana ince taneli güvenlik modellerini uygulamak için Stack Inspection kullanılmıştır.

http://lambda-the-ultimate.org/node/13

6
Mike Edwards

Çoğu durumda özyineleme, önbelleğe alma nedeniyle daha hızlıdır ve bu da performansı artırır. Örneğin, burada geleneksel birleştirme yordamını kullanarak birleştirme sıralamasının yinelemeli bir sürümüdür. Gelişmiş performansların önbelleğe alınması nedeniyle, yinelemeli uygulamadan daha yavaş çalışacaktır.

Yinelemeli uygulama

public static void sort(Comparable[] a)
{
    int N = a.length;
    aux = new Comparable[N];
    for (int sz = 1; sz < N; sz = sz+sz)
        for (int lo = 0; lo < N-sz; lo += sz+sz)
            merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}

Özyinelemeli uygulama

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);
}

PS - Profesör Kevin Wayne (Princeton Üniversitesi) tarafından Coursera'da sunulan algoritmalar hakkında söylenenler bu.

5
Nikunj Banka

Yinelemeli yöntem üzerinde çok daha zarif bir çözüm sağladığı birçok durum vardır; buradaki ortak örnek, ikili bir ağacın geçişidir, bu nedenle bakımı zorunlu olarak daha zor değildir. Genel olarak, yinelemeli sürümler genellikle biraz daha hızlıdır (ve optimizasyon sırasında özyinelemeli sürümü değiştirebilir), ancak özyinelemeli sürümlerin doğru anlaşılması ve uygulanması daha kolaydır.

5
Felix

Özyineleme çok yararlıdır, bazı durumlar. Örneğin, faktörü bulma kodunu düşünün

int factorial ( int input )
{
  int x, fact = 1;
  for ( x = input; x > 1; x--)
     fact *= x;
  return fact;
}

Şimdi özyinelemeli işlevi kullanarak düşünün

int factorial ( int input )
{
  if (input == 0)
  {
     return 1;
  }
  return input * factorial(input - 1);
}

Bu ikisini gözlemleyerek, özyinelemenin anlaşılmasının kolay olduğunu görebiliriz. Ancak dikkatle kullanılmazsa, hataya da çok açık olabilir. if (input == 0) öğesini kaçırırsak, kodun bir süre çalıştırılacağını ve genellikle bir yığın taşmasıyla sona ereceğini varsayalım.

5
Harikrishnan

Dile bağlıdır. Java öğesinde döngü kullanmalısınız. İşlevsel diller özyinelemeyi optimize eder.

4
mc

Özyinelemeyi kullanarak, her "yinelemeyle" işlev çağrısının maliyetini düşürürsünüz, ancak bir döngü ile genelde ödediğiniz tek şey bir artış/azalış olur. Dolayısıyla, döngü için kod özyinelemeli çözüm kodundan çok daha karmaşık değilse, döngü genellikle özyinelemeden daha üstün olur.

4
MovEaxEsp

Özyineleme ve yineleme, uygulamak istediğiniz iş mantığına bağlıdır, ancak çoğu zaman birbiriyle değiştirilebilir. Çoğu geliştirici özyinelemeye gider çünkü anlaşılması daha kolaydır.

4
Warrior

Özyineleme, bir yinelemenin olası tanımlarından daha basittir (ve dolayısıyla daha temeldir). Turing-complete sistemini sadece bir birleştirici çifti ile tanımlayabilirsiniz (evet, bir özyinelemenin kendisi bile böyle bir sistemde türevsel bir kavramdır). Lambda matematik hesabı, özyinelemeli fonksiyonlara sahip, eşit derecede güçlü bir temel sistemdir. Ancak bir yinelemeyi doğru tanımlamak istiyorsanız, başlamak için daha fazla ilkel gerekir.

Kod gelince - hayır, özyinelemeli kodun anlaşılması ve sürdürülmesi tamamen yinelemeli olandan daha kolaydır, çünkü çoğu veri yapısı özyinelemelidir. Tabii ki, onu doğru bir şekilde elde etmek için, en azından tüm standart birleştiricileri ve yineleyicileri düzgün bir şekilde elde etmek için yüksek dereceli işlevler ve kapanışlar için destek olan bir dile ihtiyaç duyacaksınız. Elbette C++ 'ta karmaşık özyinelemeli çözümler, FC++ ve benzeri sert bir kullanıcı değilseniz, biraz çirkin görünebilir.

3
SK-logic

Sadece bir listeyi yineliyorsanız, emin olun, uzağa yineleyin.

Birkaç başka cevap (derinlik ilk önce) ağaç geçişinden bahsetti. Bu gerçekten harika bir örnek, çünkü çok yaygın bir veri yapısına yapılacak çok yaygın bir şey. Özyineleme bu sorun için son derece sezgiseldir.

Buradaki "bulma" yöntemlerine bakın: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

3
Joe Cheng

(Kuyruksuz) özyinelemede, fonksiyonun çağrıldığı her seferinde (elbette dile bağlı olarak) yeni bir yığın tahsis etmek için bir performans vurgusu olacağını düşünüyorum.

2
metadave

Özyinelemeli işlevi şablonlu bir işlemse, C++ 'da, derleyici, tüm türden kesinti ve işlev başlatmaları derleme zamanında gerçekleşeceğinden, derleyicinin onu daha iyi hale getirme şansı vardır. Modern derleyiciler, mümkünse bu işlevi de sıralayabilir. Dolayısıyla, -O3 veya -O2 gibi g++ gibi optimizasyon bayrakları kullanıyorsa, özyineleme yinelemelerden daha hızlı olma şansına sahip olabilir. Yinelemeli kodlarda, derleyicinin daha az ya da çok optimal durumda olduğu için (yeterince iyi yazılmışsa) optimize etme şansı azalıyor.

Benim durumumda, Armadillo matrix nesnelerini hem özyinelemeli hem de yinelemeli şekilde kullanarak kareler alarak matris üstelemesi yapmaya çalışıyordum. Algoritma burada bulunabilir ... https://en.wikipedia.org/wiki/Exponentiation_by_squaring . İşlevlerim ayarlandı ve güce yükseltilmiş 1,000,00012x12 matrisleri 10 olarak hesapladım. Aşağıdaki sonucu aldım:

iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec

iterative + No-optimisation flag  -> 2.83.. sec
recursive + No-optimisation flag  -> 4.15.. sec

Bu sonuçlar c ++ 11 bayraklı gcc-4.8 (-std=c++11) ve Intel mkl'li Armadillo 6.1 kullanılarak elde edildi. Intel derleyici de benzer sonuçlar gösteriyor.

2
Titas Chanda

Özyineleme? Nereden başlayacağım, wiki size “öğelerin benzer şekilde yinelenmesi süreci” diyecek

Gündüzleri C yaparken C++ özyinelemesi bir tanrının yoluydu, "Kuyruk özyinimi" gibi şeylerdi. Ayrıca özyinelemeyi kullanan birçok sıralama algoritması bulacaksınız. Hızlı sıralama örneği: http://alienryderflex.com/quicksort/

Özyineleme, belirli bir problem için faydalı olan başka bir algoritma gibidir. Belki de derhal veya sık sık bir kullanım bulamayabilirsiniz ancak kullanımınıza memnun olacağınız bir sorun olabilir.

2
Nickz

“özyineleme derinliğine” bağlıdır. genel arama çağrısının toplam yürütme süresini ne kadar etkileyeceğine bağlıdır.

Örneğin, klasik faktörün özyinelemeli bir şekilde hesaplanması aşağıdakilerden dolayı çok verimsizdir: - veri taşması riski - yığın taşması riski - fonksiyon çağrısı yükü yürütme süresinin% 80'ini kaplar

daha sonraki N hamleleri analiz edecek satranç oyununda pozisyon analizi için bir min-max algoritması geliştirilirken, sonraki analizleri "analiz derinliği" üzerinde yinelemeyle uygulanabilir (yaptığım gibi ^ _ ^)

2
ugasoft

Mike haklı. Kuyruk özyineleme değil Java derleyicisi veya JVM tarafından optimize edilmiştir. Her zaman böyle bir şeyle yığın taşması elde edersiniz:

int count(int i) {
  return i >= 100000000 ? i : count(i+1);
}
1
noah

Özyineleme, özyineleme kullanarak yazdığınız algoritmanın O(n) boşluk karmaşıklığına sahip olması bir dezavantajı vardır. Yinelemeli yaklaşımı O (1) 'in uzay karmaşıklığına sahipken, yinelemede yineleme kullanmanın avantajı budur. Öyleyse neden özyinelemeyi kullanıyoruz?

Aşağıya bakınız.

Bazen yineleme kullanarak bir algoritma yazmak daha kolaydır, yinelemeyi kullanarak aynı algoritmayı yazmak biraz daha zordur.

1

Çok derin özyineleme kullanmanın, izin verilen yığın boyutuna bağlı olarak Yığın Taşması ile karşılaşacağınızı aklınızda bulundurmanız gerekir. Bunu önlemek için, özyinelemeyi sona erdiren bazı temel durumlar sağladığınızdan emin olun.

1
Grigori A.

Bildiğim kadarıyla Perl, kuyruk özyinelemeli aramaları optimize etmiyor, ancak sahte yapabilirsiniz.

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

İlk çağrıldığında yığında boşluk bırakacaktır. Ardından, argümanlarını değiştirecek ve alt yordamı yığına daha fazla bir şey eklemeden yeniden başlatacaktır. Bu nedenle, asla kendi kendini aramadığını, yinelemeli bir sürece dönüştürdüğünü iddia edecek.

Eğer daha fazla işe yaramazsa, "my @_;" veya "local @_;" olmadığını unutmayın.

0
Brad Gilbert

Yinelemeler atomik ve büyüklük sırasına göre yeni bir küme çerçevesine basmaktan daha pahalıysa ve yeni bir iş parçacığı oluşturmak ve birden fazla çekirdeğiniz vardır ve çalışma zamanı ortamı hepsini kullanabilir, sonra özyinelemeli bir yaklaşım çoklu okuma ile birleştirildiğinde büyük bir performans artışı sağlayabilir. Ortalama yineleme sayısı tahmin edilemezse, o zaman iş parçacığı tahsisini kontrol edecek ve işleminizin çok fazla iş parçacığı yaratmasını ve sistemi sallamasını engelleyecek bir iş parçacığı havuzu kullanmak iyi bir fikir olabilir.

Örneğin, bazı dillerde özyinelemeli çok iş parçacıklı birleştirme sıralama uygulamaları vardır.

Ancak yine, çoklu okuma özyineleme yerine döngü ile kullanılabilir, bu yüzden bu kombinasyonun ne kadar iyi çalışacağı işletim sistemi ve iş parçacığı ayırma mekanizması da dahil olmak üzere daha fazla faktöre bağlıdır.

0
ccpizza

Sadece Chrome 45.0.2454.85 m kullanarak, özyineleme daha hızlı Güzel bir miktar gibi görünüyor.

İşte kod:

(function recursionVsForLoop(global) {
    "use strict";

    // Perf test
    function perfTest() {}

    perfTest.prototype.do = function(ns, fn) {
        console.time(ns);
        fn();
        console.timeEnd(ns);
    };

    // Recursion method
    (function recur() {
        var count = 0;
        global.recurFn = function recurFn(fn, cycles) {
            fn();
            count = count + 1;
            if (count !== cycles) recurFn(fn, cycles);
        };
    })();

    // Looped method
    function loopFn(fn, cycles) {
        for (var i = 0; i < cycles; i++) {
            fn();
        }
    }

    // Tests
    var curTest = new perfTest(),
        testsToRun = 100;

    curTest.do('recursion', function() {
        recurFn(function() {
            console.log('a recur run.');
        }, testsToRun);
    });

    curTest.do('loop', function() {
        loopFn(function() {
            console.log('a loop run.');
        }, testsToRun);
    });

})(window);

SONUÇLARI

// 100 döngü için standart kullanarak çalışır

Döngü çalışması için 100x. Tamamlanma zamanı: 7.683ms

// 100 özyinelemeli işlevsel özyinelemeli yaklaşımı kullanarak çalışır

100x özyineleme çalışması. Tamamlanma zamanı: 4.841ms

Aşağıdaki ekran görüntüsünde, test başına 300 döngüde çalıştırıldığında özyineleme tekrar daha büyük bir farkla kazanır

Recursion wins again!

0
Alpha G33k