هل هناك طريقة لتسريع العودية من خلال تذكر العقد الفرعية؟
https://stackoverflow.com/questions/23962
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
على سبيل المثال ، انظر إلى الكود الذي يحسب رقم N-Th Fibonacci:
fib(int n)
{
if(n==0 || n==1)
return 1;
return fib(n-1) + fib(n-2);
}
المشكلة في هذا الرمز هي أنه سيؤدي إلى إنشاء خطأ تجاوز سعة المكدس لأي رقم أكبر من 15 (في معظم أجهزة الكمبيوتر).
افترض أننا نحسب الألياف (10).في هذه العملية، لنفترض أنه يتم حساب fib(5) كثيرًا من المرات.هل هناك طريقة ما لتخزين هذا في الذاكرة لاسترجاعه بسرعة وبالتالي زيادة سرعة التكرار؟
أنا أبحث عن تقنية عامة يمكن استخدامها في جميع المشاكل تقريبًا.
المحلول
نعم رؤيتك صحيحةهذا يسمي البرمجة الديناميكية.عادةً ما تكون هذه مقايضة شائعة في وقت تشغيل الذاكرة.
في حالة فيبو، لا تحتاج حتى إلى تخزين كل شيء مؤقتًا:
تحرير] يبدو أن مؤلف السؤال يبحث عن طريقة عامة لتخزين ذاكرة التخزين المؤقت بدلاً من طريقة لحساب فيبوناتشي.ابحث في ويكيبيديا أو انظر إلى رمز الملصق الآخر للحصول على هذه الإجابة.هذه الإجابات خطية في الوقت والذاكرة.
** هنا خوارزمية الزمن الخطي O(n)، ثابتة في الذاكرة **
in OCaml:
let rec fibo n =
let rec aux = fun
| 0 -> (1,1)
| n -> let (cur, prec) = aux (n-1) in (cur+prec, cur)
let (cur,prec) = aux n in prec;;
in C++:
int fibo(int n) {
if (n == 0 ) return 1;
if (n == 1 ) return 1;
int p = fibo(0);
int c = fibo(1);
int buff = 0;
for (int i=1; i < n; ++i) {
buff = c;
c = p+c;
p = buff;
};
return c;
};
يتم تنفيذ هذا في الوقت الخطي.ولكن السجل ممكن فعلا !!!برنامج Roo خطي أيضًا، ولكنه أبطأ بكثير، ويستخدم الذاكرة.
هنا خوارزمية السجل O(log(n))
الآن بالنسبة لخوارزمية تسجيل الوقت (بطريقة أسرع بكثير)، إليك الطريقة:إذا كنت تعرف u(n)، u(n-1)، فيمكن إجراء حساب u(n+1)، u(n) عن طريق تطبيق مصفوفة:
| u(n+1) | = | 1 1 | | u(n) |
| u(n) | | 1 0 | | u(n-1) |
بحيث يكون لديك :
| u(n) | = | 1 1 |^(n-1) | u(1) | = | 1 1 |^(n-1) | 1 |
| u(n-1) | | 1 0 | | u(0) | | 1 0 | | 1 |
حساب الأسي للمصفوفة له تعقيد لوغاريتمي.فقط قم بتنفيذ الفكرة بشكل متكرر:
M^(0) = Id
M^(2p+1) = (M^2p) * M
M^(2p) = (M^p) * (M^p) // of course don't compute M^p twice here.
يمكنك أيضًا تحديده قطريًا (ليس بالأمر الصعب)، وستجد الرقم الذهبي ومرافقه في قيمته الذاتية، وستعطيك النتيجة صيغة رياضية دقيقة لـ u(n).فهو يحتوي على قوى تلك القيم الذاتية، بحيث يظل التعقيد لوغاريتميًا.
غالبًا ما يتم أخذ Fibo كمثال لتوضيح البرمجة الديناميكية، ولكن كما ترى، فهو ليس ذو صلة حقًا.
@جون:لا أعتقد أن الأمر له علاقة بالتجزئة.
@جون2:الخريطة عامة بعض الشيء، ألا تعتقد ذلك؟بالنسبة لحالة فيبوناتشي، تكون جميع المفاتيح متجاورة بحيث يكون المتجه مناسبًا، ومرة أخرى هناك طرق أسرع بكثير لحساب تسلسل فيبو، راجع نموذج التعليمات البرمجية الخاص بي هناك.
نصائح أخرى
وهذا ما يسمى الحفظ وهناك مقالة جيدة جدًا عن الحفظ ماثيو بودفيسوكي نشرت هذه الأيام.ويستخدم فيبوناتشي لتجسيد ذلك.ويظهر الكود في C# أيضًا.اقرأها هنا.
إذا كنت تستخدم C#، ويمكنك استخدامه بوستشارب, ، إليك جانب الحفظ البسيط للتعليمات البرمجية الخاصة بك:
[Serializable]
public class MemoizeAttribute : PostSharp.Laos.OnMethodBoundaryAspect, IEqualityComparer<Object[]>
{
private Dictionary<Object[], Object> _Cache;
public MemoizeAttribute()
{
_Cache = new Dictionary<object[], object>(this);
}
public override void OnEntry(PostSharp.Laos.MethodExecutionEventArgs eventArgs)
{
Object[] arguments = eventArgs.GetReadOnlyArgumentArray();
if (_Cache.ContainsKey(arguments))
{
eventArgs.ReturnValue = _Cache[arguments];
eventArgs.FlowBehavior = FlowBehavior.Return;
}
}
public override void OnExit(MethodExecutionEventArgs eventArgs)
{
if (eventArgs.Exception != null)
return;
_Cache[eventArgs.GetReadOnlyArgumentArray()] = eventArgs.ReturnValue;
}
#region IEqualityComparer<object[]> Members
public bool Equals(object[] x, object[] y)
{
if (Object.ReferenceEquals(x, y))
return true;
if (x == null || y == null)
return false;
if (x.Length != y.Length)
return false;
for (Int32 index = 0, len = x.Length; index < len; index++)
if (Comparer.Default.Compare(x[index], y[index]) != 0)
return false;
return true;
}
public int GetHashCode(object[] obj)
{
Int32 hash = 23;
foreach (Object o in obj)
{
hash *= 37;
if (o != null)
hash += o.GetHashCode();
}
return hash;
}
#endregion
}
فيما يلي نموذج لتطبيق فيبوناتشي يستخدمه:
[Memoize]
private Int32 Fibonacci(Int32 n)
{
if (n <= 1)
return 1;
else
return Fibonacci(n - 2) + Fibonacci(n - 1);
}
الحفظ السريع والقذر في C++:
أي طريقة العودية type1 foo(type2 bar) { ... } يتم حفظها بسهولة مع map<type2, type1> M.
// your original method
int fib(int n)
{
if(n==0 || n==1)
return 1;
return fib(n-1) + fib(n-2);
}
// with memoization
map<int, int> M = map<int, int>();
int fib(int n)
{
if(n==0 || n==1)
return 1;
// only compute the value for fib(n) if we haven't before
if(M.count(n) == 0)
M[n] = fib(n-1) + fib(n-2);
return M[n];
}
يحرر:@ كونراد رودولف
يشير كونراد إلى أن std::map ليست أسرع بنية بيانات يمكن أن نستخدمها هنا.هذا صحيح، أ vector<something> ينبغي أن يكون أسرع من أ map<int, something> (على الرغم من أنها قد تتطلب المزيد من الذاكرة إذا لم تكن مدخلات الاستدعاءات المتكررة للوظيفة أعدادًا صحيحة متتالية كما هي في هذه الحالة)، إلا أن الخرائط ملائمة للاستخدام بشكل عام.
وفق ويكيبيديا يجب أن يكون Fib(0) 0 ولكن لا يهم.
فيما يلي حل بسيط لـ C# مع الدورة:
ulong Fib(int n)
{
ulong fib = 1; // value of fib(i)
ulong fib1 = 1; // value of fib(i-1)
ulong fib2 = 0; // value of fib(i-2)
for (int i = 0; i < n; i++)
{
fib = fib1 + fib2;
fib2 = fib1;
fib1 = fib;
}
return fib;
}
إنها خدعة شائعة جدًا لتحويل العودية إليها العودية الذيل ومن ثم إلى حلقة.لمزيد من التفاصيل انظر على سبيل المثال هذا محاضرة (جزء لكل تريليون).
ما هذه اللغة؟لا يفيض على أي شيء في ج...يمكنك أيضًا محاولة إنشاء جدول بحث في الكومة، أو استخدام الخريطة
يعد التخزين المؤقت فكرة جيدة بشكل عام لهذا النوع من الأشياء.بما أن أرقام فيبوناتشي ثابتة، يمكنك تخزين النتيجة مؤقتًا بمجرد قيامك بحسابها.مثال سريع على c/pseudocode
class fibstorage {
bool has-result(int n) { return fibresults.contains(n); }
int get-result(int n) { return fibresult.find(n).value; }
void add-result(int n, int v) { fibresults.add(n,v); }
map<int, int> fibresults;
}
fib(int n ) {
if(n==0 || n==1)
return 1;
if (fibstorage.has-result(n)) {
return fibstorage.get-result(n-1);
}
return ( (fibstorage.has-result(n-1) ? fibstorage.get-result(n-1) : fib(n-1) ) +
(fibstorage.has-result(n-2) ? fibstorage.get-result(n-2) : fib(n-2) )
);
}
calcfib(n) {
v = fib(n);
fibstorage.add-result(n,v);
}
سيكون هذا بطيئًا جدًا، حيث أن كل عملية تكرارية تؤدي إلى 3 عمليات بحث، ولكن هذا يجب أن يوضح الفكرة العامة
هل هذا مثال تم اختياره عمدا؟(على سبيل المثال.حالة متطرفة تريد اختبارها)
نظرًا لأنه O(1.6^n) حاليًا، أريد فقط التأكد من أنك تبحث فقط عن إجابات حول التعامل مع الحالة العامة لهذه المشكلة (قيم التخزين المؤقت، وما إلى ذلك) وليس مجرد كتابة تعليمات برمجية سيئة عن طريق الخطأ: D
بالنظر إلى هذه الحالة المحددة، يمكن أن يكون لديك شيء على غرار:
var cache = [];
function fib(n) {
if (n < 2) return 1;
if (cache.length > n) return cache[n];
var result = fib(n - 2) + fib(n - 1);
cache[n] = result;
return result;
}
الذي ينحط إلى O(n) في أسوأ الحالات :D
[يحرر:* لا يساوي + :D ]
[تعديل آخر:نسخة هاسكل (لأنني مازوشي أو شيء من هذا القبيل)
fibs = 1:1:(zipWith (+) fibs (tail fibs))
fib n = fibs !! n
]
حاول استخدام الخريطة، n هو المفتاح ورقم فيبوناتشي المقابل له هو القيمة.
@ بول
شكرا للمعلومة.لم أكن أعرف ذلك.من رابط ويكيبيديا ذكرت:
تسمى هذه التقنية المتمثلة في توفير القيم التي تم حسابها بالفعل المذكرات
نعم لقد ألقيت نظرة بالفعل على الكود (+1).:)
@ESRogs:
std::map البحث هو يا(سجل ن) مما يجعلها بطيئة هنا.من الأفضل استخدام ناقل.
vector<unsigned int> fib_cache;
fib_cache.push_back(1);
fib_cache.push_back(1);
unsigned int fib(unsigned int n) {
if (fib_cache.size() <= n)
fib_cache.push_back(fib(n - 1) + fib(n - 2));
return fib_cache[n];
}
لقد أجاب الآخرون على سؤالك بشكل جيد ودقيق - فأنت تبحث عن الحفظ.
لغات البرمجة مع تحسين المكالمة الذيل (معظمها من اللغات الوظيفية) يمكنها القيام بحالات معينة من التكرار دون تجاوز سعة المكدس.لا ينطبق هذا بشكل مباشر على تعريفك لفيبوناتشي، على الرغم من وجود حيل.
صياغة سؤالك جعلتني أفكر في فكرة مثيرة للاهتمام.تجنب تجاوز سعة المكدس لوظيفة متكررة خالصة عن طريق تخزين مجموعة فرعية فقط من إطارات المكدس وإعادة البناء عند الضرورة.مفيدة حقا فقط في حالات قليلة.إذا كانت الخوارزمية الخاصة بك تعتمد بشكل مشروط فقط على السياق بدلاً من الإرجاع، و/أو كنت تعمل على تحسين الذاكرة وليس السرعة.
لدى Mathematica طريقة بارعة بشكل خاص للقيام بالحفظ، بالاعتماد على حقيقة أن التجزئات واستدعاءات الوظائف تستخدم نفس البنية:
fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]
هذا كل شيء.يقوم بتخزين (يحفظ) fib[0] وfib[1] بعيدًا عن الخفافيش ويخزن الباقي مؤقتًا حسب الحاجة.إن قواعد استدعاءات وظائف مطابقة الأنماط هي أنها تستخدم دائمًا تعريفًا أكثر تحديدًا قبل تعريف أكثر عمومية.
أحد الموارد الممتازة الأخرى لمبرمجي C# في مجال التكرار، والأجزاء، والحفظ، وأمثالهم، هو مدونة Wes Dyer، على الرغم من أنه لم ينشر منذ فترة.وهو يشرح الحفظ بشكل جيد، مع أمثلة التعليمات البرمجية القوية هنا:http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx
المشكلة في هذا الرمز هي أنه سيؤدي إلى إنشاء خطأ تجاوز سعة المكدس لأي رقم أكبر من 15 (في معظم أجهزة الكمبيوتر).
حقًا؟ما هو الكمبيوتر الذي تستخدمه؟يستغرق الأمر وقتًا طويلاً عند 44، لكن المكدس لا يفيض.في الواقع، ستحصل على قيمة أكبر مما يمكن أن يحمله عدد صحيح (~ 4 مليار غير موقع، ~ 2 مليار موقع) قبل أن يفيض المكدس (Fibbonaci(46)).
قد يعمل هذا مع ما تريد القيام به بالرغم من ذلك (يتم تشغيله بسرعة)
class Program
{
public static readonly Dictionary<int,int> Items = new Dictionary<int,int>();
static void Main(string[] args)
{
Console.WriteLine(Fibbonacci(46).ToString());
Console.ReadLine();
}
public static int Fibbonacci(int number)
{
if (number == 1 || number == 0)
{
return 1;
}
var minus2 = number - 2;
var minus1 = number - 1;
if (!Items.ContainsKey(minus2))
{
Items.Add(minus2, Fibbonacci(minus2));
}
if (!Items.ContainsKey(minus1))
{
Items.Add(minus1, Fibbonacci(minus1));
}
return (Items[minus2] + Items[minus1]);
}
}
إذا كنت تستخدم لغة ذات وظائف من الدرجة الأولى مثل Scheme، فيمكنك إضافة الحفظ دون تغيير الخوارزمية الأولية:
(define (memoize fn)
(letrec ((get (lambda (query) '(#f)))
(set (lambda (query value)
(let ((old-get get))
(set! get (lambda (q)
(if (equal? q query)
(cons #t value)
(old-get q))))))))
(lambda args
(let ((val (get args)))
(if (car val)
(cdr val)
(let ((ret (apply fn args)))
(set args ret)
ret))))))
(define fib (memoize (lambda (x)
(if (< x 2) x
(+ (fib (- x 1)) (fib (- x 2)))))))
توفر الكتلة الأولى وسيلة للحفظ والكتلة الثانية هي تسلسل فيبوناتشي باستخدام تلك المنشأة.يحتوي هذا الآن على وقت تشغيل O(n) (على عكس O(2^n) للخوارزمية بدون حفظ).
ملحوظة:تستخدم أداة الحفظ المتوفرة سلسلة من عمليات الإغلاق للبحث عن الدعوات السابقة.في أسوأ الأحوال يمكن أن يكون O(n).ومع ذلك، في هذه الحالة، تكون القيم المطلوبة دائمًا في أعلى السلسلة، مما يضمن البحث عن O(1).
كما أشارت الملصقات الأخرى، الحفظ هي طريقة قياسية لاستبدال الذاكرة بالسرعة، وإليك بعض التعليمات البرمجية الزائفة لتنفيذ الحفظ لأي وظيفة (شريطة ألا يكون للوظيفة أي آثار جانبية):
رمز الوظيفة الأولية:
function (parameters)
body (with recursive calls to calculate result)
return result
وينبغي أن يتحول هذا إلى
function (parameters)
key = serialized parameters to string
if (cache[key] does not exist) {
body (with recursive calls to calculate result)
cache[key] = result
}
return cache[key]
بالمناسبة بيرل لديه حفظ الوحدة النمطية التي تقوم بذلك لأي وظيفة في التعليمات البرمجية التي تحددها.
# Compute Fibonacci numbers
sub fib {
my $n = shift;
return $n if $n < 2;
fib($n-1) + fib($n-2);
}
من أجل حفظ هذه الوظيفة، كل ما عليك فعله هو بدء البرنامج الخاص بك
use Memoize;
memoize('fib');
# Rest of the fib function just like the original version.
# Now fib is automagically much faster ;-)
@lassevk:
هذا رائع، بالضبط ما كنت أفكر فيه في رأسي بعد أن قرأت عن الحفظ في الكتاب بيرل من أجل العالي.هناك شيئان أعتقد أنهما سيكونان إضافة مفيدة:
- معلمة اختيارية لتحديد طريقة ثابتة أو عضو يتم استخدامها لإنشاء مفتاح ذاكرة التخزين المؤقت.
- طريقة اختيارية لتغيير كائن ذاكرة التخزين المؤقت بحيث يمكنك استخدام ذاكرة تخزين مؤقت مدعومة بقرص أو قاعدة بيانات.
لست متأكدًا من كيفية القيام بهذا النوع من الأشياء باستخدام السمات (أو إذا كان ذلك ممكنًا مع هذا النوع من التنفيذ) ولكني أخطط لمحاولة اكتشاف ذلك.
(خارج الموضوع:كنت أحاول نشر هذا كتعليق، لكنني لم أدرك أن التعليقات لها مثل هذا الطول القصير المسموح به، لذا فإن هذا لا يتناسب حقًا مع "الإجابة")
