كيف يمكنني تغيير بنية الرسم البياني الخاص بي (إدراج بطيء جدًا)؟

Question

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

الآن، هناك العديد من تطبيقات Graph المحتملة ولا أعتقد أنني أستخدم أفضلها.انا املك Graph الهيكل والداخل، هناك مؤشر إلى قائمة مرتبطة من النوع Vertex.كل Vertex العنصر له قيمة، مؤشر إلى التالي Vertex ومؤشر إلى قائمة النوع المرتبطة Edge.كل Edge العنصر له قيمة (حتى أتمكن من تحديد الأوزان وكل ما هو مطلوب)، وهو مؤشر إلى التالي Edge ومؤشر إلى Vertex مالك.

لدي ملفين نموذجيين يحتويان على بيانات للمعالجة (بنمط CSV) وإدراجهما في الرسم البياني.الأول هو بيانات المستخدم (مستخدم واحد لكل سطر)؛والثاني هو علاقات المستخدم (للرسم البياني).يتم إدراج الملف الأول بسرعة في الرسم البياني لأنني أقوم دائمًا بإدراجه في الرأس وهناك ما يقرب من 18000 مستخدم.يستغرق الملف الثاني وقتًا طويلاً ولكني ما زلت أقوم بإدخال الحواف في الرأس.يحتوي الملف على حوالي 520000 سطرًا من علاقات المستخدم ويستغرق ما بين 13 إلى 15 دقيقة لإدراجه في الرسم البياني.لقد أجريت اختبارًا سريعًا وتمت قراءة البيانات بسرعة كبيرة وعلى الفور.المشكلة في الإدراج.

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

كيف يجب أن أحل هذا؟

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

يعد استخدام القوائم المرتبطة مفيدًا لتعقيد المساحة ولكنه سيئ لتعقيد الوقت.واستخدام المصفوفة أمر جيد بالنسبة للتعقيد الزمني ولكنه سيء ​​بالنسبة للتعقيد المكاني.

هل هناك أي أفكار حول هذا الحل؟

الحل 2) يتطلب هذا المشروع أيضًا أن يكون لدي نوع من هياكل البيانات التي تسمح بالبحث السريع بناءً على فهرس الاسم وفهرس المعرف.لهذا قررت استخدام جداول التجزئة.يتم تنفيذ جداولي بتسلسل منفصل كحل للتصادم وعندما يصل عامل التحميل إلى 0.70، أقوم عادةً بإعادة إنشاء الجدول.أنا أبني حجم الجدول التالي على هذا http://planetmath.org/encyclopedia/GoodHashTablePrimes.html.

حاليًا، يحتوي كلا جدولي التجزئة على مؤشر إلى ملف UserProfile بدلاً من تكرار ملف تعريف المستخدم نفسه.سيكون ذلك أمرًا غبيًا، فتغيير البيانات سيتطلب 3 تغييرات ومن الغباء حقًا القيام بذلك بهذه الطريقة.لذلك قمت فقط بحفظ المؤشر في ملف UserProfile.يتم أيضًا حفظ نفس مؤشر ملف تعريف المستخدم كقيمة في كل رسم بياني Vertex.

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

ما أفكر فيه لحل مشكلة الرسم البياني الخاص بي هو، بدلاً من جعل قيمة Hash Tables تشير إلى UserProfile, ، وأشير إلى المقابلة Vertex.لا يزال مؤشرًا، ولا يتم استخدام مساحة أكثر ولا أقل، فقط أغير ما أشير إليه.

وبهذه الطريقة، يمكنني البحث بسهولة وسرعة عن كل قمة أحتاجها وربطها معًا.سيؤدي هذا إلى إدراج العلاقات ~520000 بسرعة كبيرة.

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

لكن هل ترى أي سلبيات في هذا الحل الثاني مقارنة بالحل الأول؟أم فقط الإيجابيات التي تغلب الإيجابيات والسلبيات على الحل الأول؟

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

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

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

Answer 1

النهج الأول هو نظرًا لأن المشكلة الرئيسية هنا هي السرعة، فأنا أفضل نهج المصفوفة.

يجب عليك بالطبع الحفاظ على جدول التجزئة للبحث عن فهرس الأسماء.

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

للتعامل مع مشكلة تخصيص المساحة، أوصي بما يلي:

1- اقرأ الملف مرة واحدة لتحصل على رقم الرأس.

2- تخصيص تلك المساحة

إذا كانت بياناتك ديناميكية، فيمكنك تنفيذ طريقة بسيطة لزيادة حجم المصفوفة بخطوات تبلغ 50%.

3 - في الحواف، استبدل القائمة المرتبطة بمصفوفة.يجب أن تتم زيادة هذا المصفوفة ديناميكيًا بخطوات تبلغ 50%.

حتى مع تخصيص المساحة "الإضافية"، عند زيادة الحجم بخطوات تبلغ 50%، يجب أن يكون الحجم الإجمالي الذي تستخدمه المصفوفة أكبر قليلاً فقط من حجم القائمة المرتبطة.

آمل أن أتمكن من المساعدة.