ما هو معدل النمو المثالي للحصول على صفيف مخصص ديناميكيا؟

Question

C ++ قد STD :: متجه وجافا لديه قائمة صفيف، والعديد من اللغات الأخرى لها شكل خاصاتها الخاصة من مجموعة مخصصة ديناميكيا. عند نفاد صفيف ديناميكي من المساحة، يتم إعادة تخصيصها إلى منطقة أكبر ويتم نسخ القيم القديمة في الصفيف الجديد. سؤال أساسي لأداء هذه الصفيف هو مدى سرعة تنمو الصفيف. إذا كنت دائما تنمو كبيرا بما يكفي لتناسب الدفعة الحالية، فسوف ينتهي الأمر بالريان في كل مرة. لذلك من المنطقي مضاعفة حجم الصفيف، أو اضربها عن طريق القول 1.5x.

هل هناك عامل نمو مثالي؟ 2x؟ 1.5x؟ حسب المثالي، أقصد ما يبرره رياضيا، أفضل أداء موازنة وأهدر الذاكرة. أدرك أن ذلك نظريا، بالنظر إلى أن التطبيق الخاص بك يمكن أن يكون له أي توزيع محتمل للدفعات أن هذا يعتمد على تطبيق إلى حد ما. لكنني فضولي لمعرفة ما إذا كانت هناك قيمة "عادة"، أو تعتبر أفضل ضمن بعض القيود الصارمة.

سمعت أن هناك ورقة في مكان ما في مكان ما، لكنني لم أتمكن من العثور عليها.

Answer 1

سوف تعتمد تماما على حالة الاستخدام. هل تهتم بالمزيد في الوقت الذي يضيع فيه نسخ البيانات حولها (وإعادة تخصيص صفائف) أو الذاكرة الإضافية؟ كم من الوقت ستستمر الصفيف؟ إذا لم يكن الأمر موجودا لفترة طويلة، فقد يكون استخدام المخزن المؤقت أكبر فكرة جيدة - العقوبة قصيرة الأجل. إذا كان سيشنق (على سبيل المثال في جافا، في الفترة السنوية والأجيال الأكبر سنا) من الواضح أن المزيد من العقوبة.

لا يوجد شيء مثل "عامل نمو مثالي". انها ليست مجرد نظريا يعتمد التطبيق، إنه بالتااكيد تطبيق يعتمد.

2 عامل نمو شائع جدا - أنا متأكد من أن هذا ما ArrayList و List<T> في استخدامات .NET. ArrayList<T> في جافا يستخدم 1.5.

تحرير: كما يشير إريك، Dictionary<,> في .NET يستخدم "مضاعفة الحجم ثم تزيد إلى الرقم الرئيسي التالي" بحيث يمكن توزيع قيم التجزئة بشكل معقول بين الدلاء. (أنا متأكد من أنني شهدت مؤخرا وثائق تشير إلى أن الأعداد الأولية ليست في الواقع كبيرة لتوزيع دلاء التجزئة، ولكن هذه حجة لإجابة أخرى.)

Answer 2

أتذكر قراءة منذ سنوات عديدة لماذا 1.5 يفضل أكثر من اثنين، على الأقل كما هو مطبق على C ++ (ربما لا ينطبق على اللغات المدارة، حيث يمكن لنظام وقت التشغيل نقل الكائنات في الإرادة).

المنطق هو هذا:

1. قل أنك تبدأ بتخصيص 16 بايت.
2. عندما تحتاج إلى المزيد، تخصص 32 بايت، ثم تحرير 16 بايت. هذا يترك ثقب 16 بايت في الذاكرة.
3. عندما تحتاج إلى المزيد، تخصص 64 بايت، وتحرير 32 بايت. هذا يترك ثقب 48 بايت (إذا كان 16 و 32 مجاورة).
4. عندما تحتاج إلى المزيد، تخصص 128 بايت، وتحرير 64 بايت. هذا يترك ثقب 112 بايت (على افتراض أن جميع المخصصات السابقة مجاورة).
5. وهكذا وما إلى ذلك.

الفكرة هي أنه، مع توسيع 2X، لا توجد نقطة في الوقت المناسب أن يكون الثقب الناتج كبيرا كبيرا بما يكفي لإعادة استخدامه للتخصيص التالي. باستخدام تخصيص 1.5x، لدينا هذا بدلا من ذلك:

1. ابدأ ب 16 بايت.
2. عندما تحتاج إلى المزيد، تخصيص 24 بايت، ثم تحرير 16، وترك حفرة 16 بايت.
3. عندما تحتاج إلى المزيد، تخصيص 36 بايت، ثم حرر 24، وترك ثقب 40 بايت.
4. عندما تحتاج إلى المزيد، قم بتخصيص 54 بايت، ثم حرر 36، تاركين ثقب 76 بايت.
5. عندما تحتاج إلى المزيد، تخصيص 81 بايت، ثم تحرير 54، تاركين ثقب 130 بايت.
6. عندما تحتاج إلى المزيد، استخدم 122 بايت (تقريب) من ثقب 130 بايت.

Answer 3

من الناحية المثالية (في الحد كما ن → ∞), إنه النسبة الذهبية: ϕ = 1.618...

في الممارسة العملية، تريد شيئا قريبا، مثل 1.5.

السبب هو أنك تريد أن تكون قادرا على إعادة استخدام كتل الذاكرة القديمة، للاستفادة من التخزين المؤقت وتجنب جعل نظام التشغيل باستمرار يمنحك المزيد من صفحات الذاكرة. المعادلة التي تحلها لضمان ذلك هذا يقلل عاشر^{ن − 1} − 1 = عاشر^{ن + 1} − عاشر^ن, ، الذي يقترب الحل عاشر = ل ن.

Answer 4

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

حتى مجرد التحقق بسرعة كبيرة، يظهر Ruby (1.9.1-P129) لاستخدام 1.5X عند إلحاق الصفيف، والبيثون (2.6.2) يستخدم 1.125x بالإضافة إلى ثابت (في Objects/listobject.c):

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

newsize أعلاه هو عدد العناصر في الصفيف. لاحظ جيدا ذلك newsize يضاف إلى new_allocated, ، وبالتالي فإن التعبير مع bitshifts ومشغل ternary يعد حقا حساب التخصيص الإفراط في التخصيص.

Answer 5

دعنا نقول أنك تنمو حجم الصفيف من قبل x. وبعد حتى نفترض أنك تبدأ بحجم T. وبعد في المرة القادمة التي تنمو فيها مجموعة حجمها سيكون T*x. وبعد ثم سيكون T*x^2 وما إلى ذلك وهلم جرا.

إذا كان هدفك هو أن تكون قادرا على إعادة استخدام الذاكرة التي تم إنشاؤها من قبل، فأنت تريد التأكد من أن الذاكرة الجديدة التي تخصصها هي أقل من مجموع الذاكرة السابقة التي تم إلغاؤها. لذلك، لدينا هذا عدم المساواة:

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2)

يمكننا إزالة ر من كلا الجانبين. لذلك نحصل على هذا:

x^n <= 1 + x + x^2 + ... + x^(n-2)

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

على سبيل المثال، إذا كنا نريد أن نكون قادرين على القيام بذلك في الخطوة الثالثة (أي n=3)، إذن لدينا

x^3 <= 1 + x 

هذه المعادلة صحيحة لجميع X بحيث 0 < x <= 1.3 (بقسوة)

نرى ما س نحصل عليه بمختلف N:

n  maximum-x (roughly)

3  1.3

4  1.4

5  1.53

6  1.57

7  1.59

22 1.61

لاحظ أن العامل المتنامي يجب أن يكون أقل من 2 حيث x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2.

Answer 6

انها تعتمد حقا. بعض الناس يحللون حالات الاستخدام المشتركة للعثور على الرقم الأمثل.

لقد رأيت 1.5x 2.0x Phi X، وقوة 2 تستخدم من قبل.

Answer 7

إذا كان لديك توزيع على أطوال الصفيف، ولديك وظيفة فائدة تقول إلى أي مدى تحب إضاعة المساحة مقابل إضاعة الوقت، فيمكنك بالتأكيد اختيار استراتيجية أعلى مستوىية (وتحجيمات أولية).

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

في Scala، يمكنك تجاوز Loadfactor لجداول Hash Library القياسية ذات الوظيفة التي تنظر إلى الحجم الحالي. الغريب، والمصفوفات القابلة للتغيير مزدوجة فقط، وهو ما يفعله معظم الناس في الممارسة العملية.

لا أعرف من صفائف مضاعفة (أو 1.5 * جي) التي أخرجت في الواقع أخطاء الذاكرة وتنمو أقل في هذه الحالة. يبدو أنه إذا كان لديك مجموعة واحدة ضخمة، فأنت تريد أن تفعل ذلك.

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

Answer 8

وأنا أتفق مع JON SKEET، حتى صديقي TheoryCrafter يصر على أن هذا يمكن إثبات أنه سين (1) عند تحديد العامل إلى 2x.

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

Answer 9

أعلم أنه سؤال قديم، ولكن هناك العديد من الأشياء التي يبدو أن الجميع مفقود.

أولا، هذا هو الضرب حسب 2: الحجم << 1. هذا هو الضرب من قبل اي شى بين 1 و 2: int (تعويم (الحجم) * x)، حيث x هو الرقم، و * هي الرياضيات النقطة العائمة، ويتعين على المعالج تشغيل تعليمات إضافية للصب بين تعويم و int. وبعبارة أخرى، على مستوى الماكينة، يتضاعف مضاعفة تعليمات واحدة وسريعة للغاية للعثور على الحجم الجديد. ضرب بشيء ما بين 1 و 2 يتطلب على الاكثر تعليمات واحدة لإلقاء حجمها على تعويم، تعليمة واحدة مضاعفة (وهي تعويم الضرب، لذلك ربما يستغرق ضعف عدد الدورات على الأقل، إن لم يكن 4 مرات أو حتى 8 مرات)، وتعليمات واحدة لإعادتها إلى INT، وهذا يفترض أن منصةك يمكن أن تؤدي الرياضيات العائمة على سجلات الأغراض العامة، بدلا من طلب استخدام السجلات الخاصة. باختصار، يجب أن تتوقع الرياضيات لكل تخصيص أن يستغرق 10 مرات على الأقل طالما تحول بسيطا بسيطا. إذا كنت تقوم بنسخ الكثير من البيانات أثناء إعادة التوزيع، فقد لا يصنع ذلك الكثير من الفرق.

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

إجابتي على السؤال؟ كلا، لا يوجد رقم مثالي. إنه أمر محدد للغاية أنه لا أحد يحاول حقا. إذا كان هدفك هو استخدام الذاكرة المثالي، فأنت بعيد جدا. بالنسبة للأداء، تكون المخصصات الأقل تكرارا أفضل، ولكن إذا ذهبنا فقط مع ذلك، يمكننا أن نضاعف بنسبة 4 أو حتى 8! بالطبع، عندما يقفز Firefox من استخدام 1GB إلى 8GB في طلقة واحدة، سوف يشكو الناس، بحيث لا معنى له. فيما يلي بعض قواعد الإبهام وأود أن أذهب على الرغم من:

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

لا تهتم بذلك. إذا كنت قد أمضيت 4 ساعات فقط في محاولة لمعرفة كيفية القيام بشيء ما تم بالفعل، فقد أهدرت وقتك. بصراحة تماما، إذا كان هناك خيار أفضل من * 2، فقد تم ذلك في فئة C ++ ناقلات (والعديد من الأماكن الأخرى) منذ عقود.

أخيرا، إذا كنت حقا تريد تحسين، لا تعرق الأشياء الصغيرة. الآن أيام، لا أحد يهتم بنحو 4 كيلو بايت من الذاكرة، إلا إذا كان يعملون على الأنظمة المضمنة. عندما تصل إلى 1 جيجابايت من الكائنات التي تتراوح بين 1 ميغابايت و 10 ميغابايت لكل منهما، فإن المضاعفة ربما هو أكثر من ذلك بكثير (أعني، أي ما بين 100 و 1000 كائنات). إذا كنت تستطيع تقدير معدل التوسع المتوقع، فيمكنك تنقيحه بمعدل نمو خطي في نقطة معينة. إذا كنت تتوقع حوالي 10 كائنات في الدقيقة، فإن النمو عند 5 إلى 10 أحجام كائن في كل خطوة (مرة واحدة كل 30 ثانية إلى دقيقة واحدة) على الأرجح على ما يرام.

ما ينزله جميعا هو، لا تتفق عليه، قم بتحسين ما يمكنك، وتخصيصه وفقا للتطبيق الخاص بك (ومنصة) إذا كان يجب عليك.

Answer 10

آخر سنتان

• معظم أجهزة الكمبيوتر لديها ذاكرة افتراضية! في الذاكرة الفعلية، يمكنك الحصول على صفحات عشوائية في كل مكان يتم عرضها كمساحة متجاورة واحدة في الذاكرة الظاهرية لبرنامج البرنامج. يتم حل الحساب من قبل الأجهزة. كان استنفاد الذاكرة الظاهري مشكلة في أنظمة 32 بت، لكنها ليست مشكلة بعد الآن. لذلك ملء الفجوة ليس مصدر قلق بعد الآن (باستثناء البيئات الخاصة). نظرا لأن Windows 7 حتى تدعم Microsoft 64 بت دون جهد إضافي. @ 2011.
• يتم الوصول إلى (1) مع أي رديئة > 1 عامل. يعمل نفس الدليل الرياضي ليس فقط لمدة 2 كمعلمة.
• رديئة = 1.5 يمكن حسابها مع old*3/2 لذلك ليست هناك حاجة لعمليات النقطة العائمة. (انا اقول /2 نظرا لأن الجوائيات سوف تحل محلها تتحول قليلا في رمز التجميع الذي تم إنشاؤه إذا أرى مناسبا.)
• ذهب MSVC ل رديئة = 1.5، لذلك هناك مترجم واحد على الأقل لا يستخدم 2 كنسبة.

كما ذكر من قبل شخص ما يشعر أفضل من 8. وأيضا يشعر 2 أفضل من 1.1.

شعوري هو أن 1.5 هو افتراضي جيد. بخلاف ذلك يعتمد على القضية المحددة.