كيف هذا C++ وظيفة استخدام التحفيظ?

Question

#include <vector>
std::vector<long int> as;

long int a(size_t n){
  if(n==1) return 1;
  if(n==2) return -2;
  if(as.size()<n+1)
    as.resize(n+1);
  if(as[n]<=0)
  {
    as[n]=-4*a(n-1)-4*a(n-2);
  }
  return mod(as[n], 65535);
}

نموذج التعليمات البرمجية أعلاه باستخدام التحفيظ لحساب العودية الصيغة استنادا إلى بعض المدخلات n.وأنا أعلم أن هذا يستخدم التحفيظ, لأنني قد كتبت بحتة وظيفة العودية التي تستخدم نفس الصيغة لكن هذا بكثير أسرع أكبر بكثير من القيم n.أنا لم تستخدم ناقلات من قبل ولكني قمت ببعض البحوث و فهم مفهوم لهم.أنا أفهم أن التحفيظ من المفترض أن تخزين لكل حساب القيمة ، بحيث بدلا من أداء نفس الحسابات مرة أخرى ، فإنه يمكن ببساطة استرداد تلك التي تم حسابها.

سؤالي هو:كيف هو هذا التحفيظ, و كيف يعمل ؟ لا أستطيع أن أرى في المدونة وعند هذه النقطة يتحقق إذا كانت قيمة n موجود بالفعل.أيضا, أنا لا أفهم الغرض من if(as[n]<=0).هذه الصيغة يمكن أن تسفر عن قيم إيجابية وأخرى سلبية ، لذلك أنا لست متأكدا ما هذا الاختيار هو يبحث عن.

---

شكرا لك, أعتقد أنني على مقربة من فهم كيف يعمل هذا في الواقع قليلا أكثر بساطة مما كنت أفكر كان.

أنا لا أعتقد القيم في تسلسل يمكن أن يكون من أي وقت مضى 0, لذا يجب العمل بالنسبة لي, كما أعتقد أن ن أن تبدأ في 1.

ومع ذلك ، إذا صفر كانت قابلة للتطبيق رقم في التسلسل ما هو طريقة أخرى يمكنني حلها ؟ على سبيل المثال ، ما إذا كان خمسة لا يمكن أبدا أن تظهر ؟ سوف تحتاج فقط إلى ملء بلدي ناقلات مع الأطفال دون سن الخامسة ؟

تحرير:لدي الكثير من الردود الأخرى أثناء التحقق من رمز كتابة هذا واحد.شكرا على مساعدة الجميع ، أعتقد أنني أفهم الآن.

Answer 1

if (as[n] <= 0) هو الاختيار.إن القيم الصالحة يمكن أن تكون سلبية كما قلت ثم أنت بحاجة مختلفة الحارس للتحقق ضد.يمكن أن قيم صالحة من أي وقت مضى أن الصفر ؟ إن لم يكن, ثم جعل مجرد اختبار if (as[n] == 0).هذا يجعل التعليمات البرمجية الخاصة بك أسهل في الكتابة ، لأن بشكل افتراضي ناقلات ints مليئة أصفار.

Answer 2

الكود يظهر بشكل غير صحيح فحص (مثل[n] <= 0), و يعيد حساب القيم السلبية من الوظيفة(التي تظهر أن ما يقرب من كل قيمة أخرى).هذا يجعل العمل على نطاق خطيا مع n بدلا من 2^n مع متكررة الحل ، لذلك فإنه يعمل على نحو أسرع كثيرا.

لا يزال أفضل تحقق سيكون لاختبار ما إذا كان (كما[n] == 0) ، الذي يظهر لتشغيل 3x أسرع على نظام بلدي.حتى لو كانت وظيفة يمكن العودة 0, 0 قيمة فقط يعني أنه سوف يستغرق وقتا أطول قليلا لحساب (على الرغم من أن إذا 0 هو كثرة إرجاع القيمة ، قد ترغب في النظر في فصل المتجهات التي الأعلام إذا كانت القيمة المحسوبة أو لا بدلا من استخدام واحد ناقلات لتخزين الدالة قيمة ما إذا كان قد تم حسابها)

Answer 3

إذا كانت الصيغة يمكن أن تسفر عن كل القيم الإيجابية والسلبية ثم العمل علة خطيرة.الاختيار if(as[n]<=0) هو من المفترض يتم التحقق من إذا كان بالفعل مؤقتا هذه القيمة من حساب.ولكن إذا كانت الصيغة يمكن أن تكون سلبية هذه الوظيفة يعيد حساب هذه القيمة المخزنة مؤقتا الكثير...

ما هو حقا ربما أراد كان vector<pair<bool, unsigned> >, حيث منطقي يقول إذا كانت القيمة المحسوبة أو لا.

Answer 4

مدونة, كما شارك فقط memoizes حوالي 40% من الوقت (على وجه التحديد عندما نتذكر قيمة موجبة).كما كريس مهرج-الشباب أشار الصحيح التنفيذ بدلا الاختيار if(as[n]==0).بدلا من ذلك, يمكن للمرء أن تغيير التحفيظ القانون نفسه على قراءة as[n]=mod(-4*a(n-1)-4*a(n-2),65535);

(حتى ==0 تحقق من أن تنفق الجهد عندما memoized القيمة 0.لحسن الحظ, في هذه الحالة, هذا لم يحدث!)

Answer 5

هناك خلل في هذا القانون.وسوف تستمر في حساب قيم مثل[ن] كما[n] <= 0.وسوف memoize القيم من أن تتحول إلى أن تكون إيجابية.يعمل الكثير أسرع من الشفرة دون التحفيظ لأن هناك ما يكفي من القيم الإيجابية مثل[] بحيث العودية هو إنهاؤها بسرعة.يمكنك تحسين ذلك من خلال استخدام قيمة أكبر من 65535 كما بمشروع رصد.القيم الجديدة من ناقلات تهيئة إلى الصفر عندما ناقلات توسع.