لماذا يتم مضاعفة مجموعة المتجهات؟

Question

لماذا يضاعف التنفيذ الكلاسيكي لـ Vector (ArrayList for Java) حجم الصفيف الداخلي في كل توسيع بدلاً من مضاعفته ثلاث مرات أو أربعة أضعاف؟

Answer 1

عند حساب متوسط ​​الوقت اللازم للإدراج في المتجه، فإنك تحتاج إلى السماح بالإدراجات غير المتنامية والإدراجات المتنامية.

استدعاء العدد الإجمالي للعمليات لإدراجها ن أغراض س_{المجموع}, ، والمتوسط س_متوسط.

إذا قمت بإدراج ن العناصر، وتنمو بعامل أ كما هو مطلوب، ثم هناك س_{المجموع} = ن + Σأ^أنا [ 0 < ط < 1 + قانون الجنسية_أن ] عمليات.في أسوأ الأحوال تستخدمه 1/أ من مساحة التخزين المخصصة.

حدسي، أ = 2 يعني في أسوأ الأحوال لديك س_{المجموع} = 2ن, ، لذا س_متوسط هو O(1)، وفي أسوأ الحالات تستخدم 50% من مساحة التخزين المخصصة.

لأكبر أ, ، لديك أقل س_{المجموع}, ، ولكن المزيد من التخزين المهدر.

لأصغر أ, س_{المجموع} أكبر، لكنك لا تهدر الكثير من مساحة التخزين.وطالما أنها تنمو بشكل هندسي، فإنها لا تزال O(1) وقت الإدراج المطفأ، ولكن الثابت سوف يرتفع.

بالنسبة لعوامل النمو 1.25 (أحمر)، 1.5 (سماوي)، 2 (أسود)، 3 (أزرق) و4 (أخضر)، توضح هذه الرسوم البيانية كفاءة النقطة ومتوسط ​​الحجم (نسبة الحجم إلى المساحة المخصصة؛المزيد هو الأفضل) على اليسار وكفاءة الوقت (نسبة عمليات الإدراج/العمليات؛المزيد هو الأفضل ) على اليمين لإدخال 400000 عنصر.يتم الوصول إلى كفاءة المساحة بنسبة 100% لجميع عوامل النمو قبل تغيير الحجم مباشرةً؛القضية لاجل أ = 2 تظهر كفاءة الوقت بين 25% و50%، وكفاءة المساحة حوالي 50%، وهو أمر جيد في معظم الحالات:

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

Answer 2

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

ويقول نحن تبدأ مع 10 عناصر هي:

و1-10
2-20
3-40
4-80
5-160

وعندما كنا ثلاثة أضعاف حجم، وتنمو بسرعة كبيرة

و1-10
2-30
3-90
4-270
5-810

في الممارسة سوف تنمو ربما 10 أو 12 مرة. إذا كنت ثلاثة أضعاف كنت ربما تفعل ذلك 7 أو 8 مرات - ضرب وقت لإعادة تخصيص هو هذا عدة مرات هي صغيرة بما فيه الكفاية ما يدعو للقلق ولكن كنت أكثر من المرجح أن يقفز تماما حجم المطلوبة

.

Answer 3

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

Answer 4

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

Answer 5

إذا كنت تسأل عن تنفيذ جافا معين من <لأ href = "http://java.sun.com/javase/6/docs/api/java/util/Vector.html" يختلط = "noreferrer نوفولو "> ناقل و ArrayList ، ثم انها ليست بالضرورة الضعف على كل توسع.

ومن جافادوك للناقل:

<اقتباس فقرة>   

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

واحدة من منشئات للناقل يسمح لك بتحديد حجم وقدرة الزيادة الأولية للناقل. يوفر الطبقة ناقل أيضا ensureCapacity(int minCapacity) وsetSize(int newSize)، لإجراء تعديلات يدوية من الحد الأدنى للحجم ناقلات ولتغيير حجم ناقلات بنفسك.

والطبقة ArrayList هي مشابهة جدا:

<اقتباس فقرة>   

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

     

وتطبيق يمكن أن تزيد من قدرة مثيل ArrayList قبل إضافة عدد كبير من العناصر باستخدام عملية ensureCapacity. هذا قد يقلل من كمية إعادة توزيع تدريجي.

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

Answer 6

وشخصيا، أعتقد أن لها خيارا arbitriary. نحن يمكن ان تستخدم قاعدة البريد بدلا من قاعدة 2 (بدلا من مضاعفة حجم فقط المتعدد بنسبة (1 + ه)).

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

وقاعدة 2 تمثل حلا وسطا.

Answer 7

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