إعادة ترتيب فعالة لمجموعة البيانات الكبيرة لزيادة فعالية ذاكرة التخزين المؤقت للذاكرة

Question

لقد كنت أعمل على مشكلة اعتقدت أن الناس قد يجدونها مثيرة للاهتمام (وربما يكون شخص ما على علم بالحل الموجود مسبقًا).

لدي مجموعة بيانات كبيرة تتكون من قائمة طويلة من أزواج المؤشرات للكائنات، شيء من هذا القبيل:

[
  (a8576, b3295), 
  (a7856, b2365), 
  (a3566, b5464),
  ...
]

هناك عدد كبير جدًا من الكائنات التي يجب الاحتفاظ بها في الذاكرة في وقت واحد (من المحتمل مئات الجيجابايت)، لذا يجب تخزينها على القرص، ولكن يمكن تخزينها مؤقتًا في الذاكرة (ربما باستخدام ذاكرة التخزين المؤقت LRU).

أحتاج إلى تشغيل هذه القائمة لمعالجة كل زوج، الأمر الذي يتطلب تحميل كلا الكائنين في الزوج إلى الذاكرة (إذا لم يتم تخزينهما مؤقتًا هناك بالفعل).

إذن السؤال:هل هناك طريقة لإعادة ترتيب الأزواج في القائمة لزيادة فعالية ذاكرة التخزين المؤقت في الذاكرة (وبعبارة أخرى:تقليل عدد مرات فقدان ذاكرة التخزين المؤقت)؟

ملحوظات

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

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

3. قد تكون المشكلة مرتبطة بمشكلة العثور على أ الحد الأدنى لقطع الرسم البياني, ، ولكن حتى لو كانت المشكلات متكافئة، فلا أعتقد أن الحلول لتقليص الحد الأدنى تلتقي

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

5. في الواقع، قد لا يكون الأمر مجرد أزواج، بل يمكن أن يكون ثلاثة توائم أو أربعة توائم أو أكثر.آمل أن يكون من السهل تعميم الخوارزمية التي تقوم بذلك للأزواج.

Answer 1

تتعلق مشكلتك بمشكلة مشابهة تتعلق بأجهزة رسومات الكمبيوتر:

عند عرض القمم المفهرسة في شبكة مثلثة، عادةً ما يحتوي الجهاز على ذاكرة تخزين مؤقت لأحدث القمم التي تم تحويلها (حوالي 128 في آخر مرة كان علي أن أقلق بشأنها، ولكني أشك في أن العدد أكبر هذه الأيام).تحتاج القمم التي لم يتم تخزينها مؤقتًا إلى عملية تحويل مكلفة نسبيًا لحسابها.كان "تحسين الشبكة" لإعادة هيكلة الشبكات المثلثة لتحسين استخدام ذاكرة التخزين المؤقت موضوعًا بحثيًا ساخنًا جدًا.قد تجد لك تحسين ذاكرة التخزين المؤقت Vertex Googling (أو التحسين:^) بعض المواد المثيرة للاهتمام لمشكلتك.وكما تشير ملصقات أخرى، أظن أن القيام بذلك بفعالية سيعتمد على استغلال أي تماسك متأصل في بياناتك.

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

Answer 2

للبدء، يمكنك mmap القائمة.يعمل ذلك إذا كانت هناك مساحة عنوان كافية، وليس الذاكرة، على سبيل المثال.على وحدات المعالجة المركزية 64 بت.وهذا يجعل من السهل الوصول إلى العناصر بالترتيب.

يمكنك فرز تلك القائمة وفقًا للحد الأدنى للمسافة في ذاكرة التخزين المؤقت التي تأخذ في الاعتبار كلا العنصرين، وهو ما يعمل بشكل جيد إذا كانت الكائنات في مساحة متجاورة.يمكن أن تكون وظيفة الفرز شيئًا مثل:قارن (أ، ب) بـ (ج، د) = (أ - ج) + (ب - د) (التي تشبه مسافة هامينج).ثم تقوم بسحب شرائح من ملف تخزين العناصر والمعالجة وفقًا للقائمة.

يحرر:إصلاح خطأ في المسافة.

Answer 3

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

Answer 4

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

لذا، فإن إجابتي حقًا هي أنه لا يمكن الإجابة على هذا السؤال في حالة عامة.

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