MATLAB kuyruk arama optimizasyonunu gerçekleştiriyor mu?

Question

Kısa bir süre önce Haskell'i öğrendim ve mümkün olduğunda diğer işlevsel kodlarımı saf kodlarıma taşımaya çalışıyorum. Bunun önemli bir yönü, tüm değişkenleri değişmez, yani sabitler olarak ele almaktır. Bunu yapmak için, döngülere zorunlu bir tarzda uygulanacak pek çok hesaplama, her bir işlev çağrısı için yeni bir istif çerçevesinin tahsis edilmesi nedeniyle tipik olarak bir bellek cezasına neden olan özyineleme kullanılarak gerçekleştirilmelidir. Bir kuyruk çağrısının özel durumunda (çağrılan fonksiyonun dönüş değeri hemen arayan kişinin arayıcısına geri döndüğünde), bu ceza kuyruk arama optimizasyonu adı verilen bir işlemle atlanabilir (bir yöntemde, bu bir temel olarak yığının düzgünce ayarlanmasından sonra bir aramanın jmp ile değiştirilmesi). MATLAB varsayılan olarak TCO yapıyor mu, yoksa söyleyecek bir yolu var mı?

Answer 1

basit bir kuyruk özyinelemeli fonksiyon tanımlarsanız:

function tailtest(n) 
    if n==0; feature memstats; return; end 
    tailtest(n-1); 
end 

ve oldukça derinden recurse böylece diyoruz:

set(0,'RecursionLimit',10000); 
tailtest(1000); 

o zaman yığın çerçeveler sanki görünmüyor Çok fazla bellek yiyor. Ben yaparsanız Ancak, çok daha derin Recurse:

set(0,'RecursionLimit',10000); 
tailtest(5000); 

sonra (benim makinede, bugün) MATLAB basitçe çöküyor

: süreç kabaca ölür.

Bunun herhangi bir TCO yapan MATLAB ile tutarlı olduğunu düşünmüyorum; Tek bir argümandan başka hiçbir yerel değişken olmaksızın, sadece bir yerde, bir fonksiyonun kuyruğunu çağırdığı durum, herkesin umduğu kadar basittir.

Yani: Hayır, MATLAB'ın en azından varsayılan olarak hiç bir şekilde TCO yapmadığı anlaşılıyor. Etkinleştirebilecek seçenekleri aramamıştım (şimdiye kadar). Varsa şaşırırdım.

Yığını dışarı üflemediğimiz durumlarda, özyineleme maliyeti ne kadardır? Bill Cheatham'ın cevabına yaptığım yorumu görüyorum: zamanın tepkisi, mantıksız değil, deli gibi görünüyor.

... Bill Cheatham bu yorumu bıraktıktan sonra cevabını silmişti. TAMAM. Bu nedenle, Fibonacci fonksiyonunun basit bir yinelemeli uygulamasını ve her ikisinde de esas olarak aynı hesaplama yapan basit bir kuyruk özyinelemesini uygulamıştım ve her ikisini de fib(60)'da zamanladım. Yinelemeli uygulama, iteratif olandan çalıştırmak için 2.5 kat daha uzun sürdü. Tabii ki, göreli yük, bir ekleme ve iterasyon başına bir çıkarma işleminden daha fazla iş yapan işlevler için daha küçük olacaktır.

(Ben de delnan en açıklamalarla hemfikir. Haskell doğal hissediyor tür yüksek özyinelemeli kod MATLAB'da unidiomatic olması tipik muhtemeldir) durup dururken için iterasyon kaçınmak