أفضل طريقة لتنفيذ نوع مكدس ديناميكي؟ أو هل أنا إساءة استخدام Reallec؟

Question

أنا أستخدم لغة غامضة لا تحتوي على نوع مكدس أصلي لذلك قمت بتنفيذ بلدي. الآن، القراءة على الشبكة لقد وجدت بعض الأساليب المختلفة للقيام بذلك.

هذا هو تطبيقي (رمز PSuDo)

//push method
function Push(int)
{
    Increase (realloc) stack by 4 bytes;
    Push int into the new memory area;
}

//pop method
function Pop()
{
    collect int from the top of the stack;
    reallocate (realloc) the stack to shrink it by 4 bytes;
    return int;
}

الآن يقول بعض الناس أن استخدام دعوة RealLoc () لتغيير حجم المكدس بعد ظهرت قيمة سيئة للأداء لذلك لدي بعض الأسئلة:

1. هل من الأفضل أن تنمو فقط المكدس باستخدام malloc ثم حر في نهاية البرنامج؟
2. لتغيير حجم المكدس (دفع) هل من الأفضل أن تزداد بنسبة 4 بايت أو أكثر؟
3. هل هي أفضل الممارسات لزيادة المكدس عن طريق مضاعفة الذاكرة المخصصة عند شغلها؟
4. ما هي أفكارك في الكود أعلاه؟

Answer 1

الأسلوب القياسي هو أن تنمو الحجم فقط بموجب عامل 2، وتقليصه فقط عندما يكون استخدام الذاكرة الفعالة أقل من الربع.

بهذه الطريقة يمكنك التأكد من أنك لا تستخدم أكثر من O (الذاكرة التي تحتاجها)، ويمكنك أيضا إثبات أن المكدس يتم إطفاء الوقت المستمر.

(انظر إليها بهذه الطريقة: يمكنك دفع ثلاثة سنتات لكل عنصر يدخل أو الخروج من المكدس. سيتم استخدام اثنين منهم خلال النسخ التالي الذي سيحدث.)

ربط مقالة ويكيبيديا موضحة في مزيد من التفاصيل

Answer 2

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

اختر "حجم الصفحة"، وزيادة هذا المبلغ. من الشائع أن تنصح بمضاعفة الحجم، لكنني لست متأكدا من السبب في ذلك. ربما تعرف المزيد حول كيفية استخدام المكدس لفهم أفضل السبل لزيادة الحجم.

Answer 3

تقريبا كل هيكل متغير الحجم المنفذ في المكتبات الشعبية يقوم ببعض الأمليات الصغيرة لتجنب إعادة الترويج طوال الوقت. تذكر أنه يتعين عليه عادة نسخ البيانات لجعلها أكبر.

عادة ما ينمو بمبالغ أكبر. تتمثل استراتيجية شائعة في ضعف الحجم حتى إذا وصلت إلى حد ما، ثم تنمو بمبلغ ثابت هناك. وتقلص، لا تقلق لتغيير حجمها حتى يضيع أكثر من نصف الحجم.

Otoh، بعض التطبيقات Reallec () تفعل بالفعل ذلك بالنسبة لك وراء الستائر. للأسف، أشك في "لغتك الغامضة" هل يفعل ذلك ...