حياتي مع مكتبة الرسم البياني Boost

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

BGL وما يؤكل بها

مكتبة قوالب BGL ربما تكون معروفة لأي مطور واجه مهام الرسم البياني. ظهرت في دفعة 1.18.1 في عام 2000 ، وحصلت على الفور الموافقة على مراجعات من الكلاسيكية من هذا النوع مثل الكسندر ستيبانوف. نُشر دليل المكتبة ، الذي جمعه جيريمي سيك ولي لاي كوان لي وأندرو لامسدان ، باللغة الروسية عام 2006 من قبل بيتر (الأصل - جيريمي جي سيك ، لي كوان لي وأندرو لومسدان ، "مكتبة بوست غراف" ، 2001 ، أديسون ويسلي). تم تحديث المكتبة بشكل مكثف وتطويرها حتى نهاية عام 2013 (Boost 1.55.0). على وجه الخصوص ، في عام 2005 ، ظهر الإعلان عن نسخته الموزعة (PBGL) ، والذي تم تضمينه في Boost من الإصدار 1.40 في عام 2009 وحتى يومنا هذا لا يزال نوعًا من المعيار الفعلي لحوسبة الرسم البياني على مجموعات عالية الأداء ، على أي حال ، في العالم الأكاديمي. بقدر ما يمكن الحكم على تاريخ الإلتزامات ، حتى عام 2005 ، كان المطور الرئيسي للمكتبة هو جيريمي سيك ، بعد عام 2005 - دوغلاس جريجور ، وبشكل عام في أوقات مختلفة ، كان هناك عدد كبير من الأشخاص المتنوعين يعملون في المكتبة. ظهرت المنشورات المخصصة لها مرارًا على habr.com: أولاً وقبل كل شيء ، تجدر الإشارة إلى سلسلة من المقالات التي كتبها Vadim Androsov: [ 1 ، 2 ، 3 ]. وهكذا ، من حيث المبدأ ، تكرس الأدب الجيد والمتنوع للمكتبة ، ولكن وثائقها الخاصة ، بشكل عام ، واسعة للغاية ، تعاني إلى حد ما بسبب:

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

   توفر BGL حاليًا فئتين بيانيتين ومحول قائمة حافة:
   
   adjacency_list
   adjacency_matrix
   edge_list

   ، بعد بعض الوقت فوجئت بإيجاد تمثيل مضغوط spar_sparse_row_graph (مصفوفة متفرقة) تم تنفيذه في عام 2005. حدثت قصة مماثلة مع خوارزمية برون-كيربوش. لا تصدق جدول المحتويات ، استخدم البحث المباشر في ملفات الرأس ؛
   
2. لا توجد قائمة واحدة مُعلَّقة بالفئات الداخلية للمكتبة (حاوية_الفئة ، وبالتوازي مع_التجربة ، والتكرار_الخ ، وما إلى ذلك) اللازمة لتنفيذ طرق العرض الخاصة بك. يبدو أن هناك مشكلات في فهم ما يحدث ، على ما يبدو ، جميع مستخدمي المكتبة الذين يريدون التنقيب بشكل أعمق ، الأمر الذي يؤدي إلى ظهور "رمز من نوع العمل" ، والذي يستغرق الكثير من الوقت والجهد للوصول به إلى حالة كاملة: انظر ، على سبيل المثال ، مناقشة نموذجية .

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



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

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

وبالتالي ، فإن المشكلات المتعلقة باختيار مكتبة مرجعية لتطبيقات الرسم البياني عند النظر إلى عام 2019 لا تبدو واضحة كما نود ، وعلى مدى السنوات الخمس الماضية ، ازداد عدم اليقين بدلاً من الانخفاض.

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

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

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

1. يعالج المشغل [] للحصول على قائمة المجاورة والمصفوفة المتفرقة الخصائص الداخلية والخارجية للحواف بشكل مختلف (الخصائص الداخلية والمجمعة): الأول يعرض فقط الخصائص الخارجية (الداخلية يمكن الوصول إليها فقط مع property_map) ، أما الثانية فتُرجع خاصية بنية الإطارات التي تحتوي على قائمة مشتركة من الخصائص.
2. الدالة get للحصول على مؤشر الحافة باستخدام التعزيز :: property_map <compressed_sparse_row_graph و boost :: edge_index_t> :: type سقطت في التعزيز :: التفاصيل ، وليس في التعزيز ، كما هو الحال في جميع الحالات الأخرى.

أخيرًا ، في قالب compressed_sparse_row_graph ، بقي تخصص الرسم البياني غير الموجه (التعزيز :: undirectedS) غير مستوفٍ.

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

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

بالإضافة إلى ذلك ، يمكن الإشارة إلى الإزعاجات التالية ، غير المهمة:

• أبعاد الواصفات الداخلية لتمثيلات الرسم البياني لها تأثير كبير على استهلاك الذاكرة اللازمة لتخزين الرسم البياني ، وتؤثر في بعض الأحيان على أداء الخوارزميات.
  
  تسمح لك بعض طرق العرض (نفس compressed_sparse_row_graph) بالتحكم في هذه الأبعاد. آخرون (adjacency_list) ليس لديهم مثل هذه المعلمات ويستخدمون دائمًا الأعداد الصحيحة 64 بت (عادة ما تكون زائدة عن الحاجة) ، والتي لا يمكن استبدالها دون تعديل الكود ؛
  
• على الرغم من حقيقة أن مؤلفي المكتبة وفروا الكثير جدًا ، إلا أنه لم يتم تضمين بعض الأوليات الضرورية بشكل واضح في المكتبة. على سبيل المثال ، لا توجد وظيفة مثل revers_edge التي تؤدي انعكاس الحافة.
  
  يعتمد تنفيذ هذه الوظائف ، بالطبع ، على تمثيل الرسم البياني: في هذه الحالة ، يمكن تنفيذه من خلال التبادل التافه لعناصر الزوج ، أو أكثر أو أقل كفاءة في البحث عن طريق الحاوية ، أو لا على الإطلاق. من الصعب على المستخدم النهائي فهم كل هذه الخيارات المتنوعة ، خاصةً أنه ، وفقًا لإيديولوجية المكتبة ، لا ينبغي أن يكون الأعضاء الداخليون للوصف موضع اهتمام له.
  
• وبالمثل ، سقطت بعض البرامج النصية التي لا قيمة لها خارج المكتبة. على سبيل المثال ، يمكنك تحديد تصحيحات الحافة التي تستخدم filtered_graph لتحويل رسم بياني غير موجه إلى رسم بياني موجه ، ولكن لا توجد وسيلة لجذب انتباه المكتبة إلى هذا التحول. وفقًا لذلك ، لن يتم تجميع الخوارزميات المعتادة للرسوم البيانية الموجهة مع مثل هذا الكائن ، ولن تعمل الخوارزميات للرسوم البيانية غير الموجهة بشكل صحيح معها.
  
  يوجد في مكان ما في الجوار موضوع دعم الرسوم البيانية غير الاتجاهية التي لها علامة اتجاه خدمة على الحواف. ومع ذلك ، فقد يكون الاهتمام المتزايد بهذه النظرة بسبب الطبيعة الخاصة للمهام التي يحلها المؤلف ، كما أن الاهتمام الواسع بدعم هذه الأشياء ليس واضحًا.
  
• بالنسبة إلى وظيفة revers_edge ، على سبيل المثال أعلاه ، لا يوجد على الإطلاق خيار مدهش أن الوظيفة المطلوبة موجودة في مكان ما في أحشاء المكتبة ، لكن لسبب ما ، حصلت على اسم غير واضح. يؤدي هذا إلى المشكلة التالية ، والتي ليست للوهلة الأولى خطيرة ، ولكنها تعمل بشكل كبير على إبطاء العمل مع مكتبات القوالب المعقدة (ليس فقط BGL ، على الرغم من أنها بوضوح من بين رواد هذا المعيار): العمل مع أنظمة واسعة من الوظائف ذات الصلة ضمنيًا دون كتابة معلمة صريحة ومع دلالات الاستخدام غير الواضحة (غالبًا ما تكون أقل شفافية من أكثر مدروسًا) صعبة جسديًا ، ولا توفر بيئات التطوير الحالية أي دعم لهذا في المطور:
  
  
  
  في الواقع ، المساعدين التلقائي:
  
  
  1. مصمم بشكل أساسي لدعم OOP ، عندما تكون مجموعة من الوظائف مرتبطة بالكائن على اليمين وفقًا لنوعه. مع الوظائف العامة التي يمكن أن تكون على يسار نوع (أقل بكثير مجموعة من الأنواع) ، فإنها تساعد بشكل أسوأ بكثير حتى لو كانت جميع الأنواع معروفة.
  2. هم حتى يبعث على السخرية حتى لا يستطيعون العمل مع قوالب بسيطة. إن إصدار المساعد المرئي الذي يستخدمه المؤلف ، والذي يحتوي أمامه تعريف فئة القالب مع المعلمات الافتراضية ، يعرض تحديد "اختبار بديل" من أجل التمكن من توليد تلميح للفئة. إذا قابلتها ، لن يحدث شيء على الإطلاق.
  3. علاوة على ذلك ، فهي أقل قدرة على فهم تصفيات برنامج metaprogram ، حتى أبسطها ، مثل enable_if.
  4. حول سيناريو نموذجي: "نحن داخل دالة قالب يتم استدعاؤها من عدد غير محدد من الطول غير المحدود لسلاسل الوظائف الأخرى ، بما في ذلك القوالب" ، من المستحيل التحدث بدون دموع. في هذه الحالة ، يبقى vim أفضل صديق للمبرمج.
  
  يمكن توضيح جانب آخر من نفس الموقف باستخدام السطر الأول من جزء التعليمات البرمجية الموضح في الشكل السابق. تتم دعوة القارئ لإكمال استعلامات "زيادة الوقت الحالي" مقابل "وقت CRT الحالي" ومقارنة النتائج. نعم ، التعزيز :: date_time (تم نقله جزئيًا الآن إلى الأمراض المنقولة جنسياً) يجعل من الممكن القيام بالكثير من الأمور المعقدة بشكل صحيح ، بينما يسمح لك CRT بإجراء العديد من العمليات التافهة بشكل غير صحيح ، لكن في المواقف المنزلية اليومية الشائعة ، يكون CRT أكثر ملاءمة من جميع وجهات النظر ، ومنظوم كثير الحدود تميل أشكال النموذج posix_time :: second_clock :: local_time (مثال لطيف) إلى التحول إلى الكتابة الهيروغليفية المتجولة في البرنامج. حرم المطور من الوصول إلى المكتبة الشخصية بهذه الهيروغليفية وسرعان ما ستنطلق سرعة التطوير إلى الصفر .
  
  يجعل Boost :: string_algo من الممكن فعل أي شيء بالسلسلة ، ولكن بصراحة ، كل عملية غير تافهة ترافقها جلسة من وثائق إعادة قراءة لتحديث المنطق العام للمكتبة ، وأسماء المسندات ، بالإضافة إلى تمرين منفصل لمعرفة توافق المعلمات. يحدث موقف مماثل مع عمليات الرمز المميز في دفعة :: regexp ، مع المنطق الداخلي لا تشوبه شائبة من الأخير.
  
  في حالة حدوث مثل هذا الموقف مع المكتبات الأكثر استخدامًا ، فليس من المستغرب أن تكون BGL ، كمكتبة أكثر تخصصًا ، حيث توجد ، على سبيل المثال ، make_property_map_function و make_function_property_map وظائف ليست مرتبطة ببعضها البعض ، وكذلك وظيفة get sacramental يتم إعادة تحميلها إلى أي عدد الوسائط من أي نوع يؤدي إلى نفس المشاكل ، ولكن في شكل تضخم. نعم ، يمكن حل أي مهمة عن طريق سلسلة الاتصال ، ولكن للأسف ، لا تحل كل سلسلة سلسلة هذه المشكلة.
  
  يمكن أن تكون قراءة مثل هذا الرمز سهلة وممتعة ، بل قد تبدو كملخص لخوارزمية مكتوبة رسميًا بلغة طبيعية ، ولكن عند كتابتها ، يكون استحالة استبدال الكلمات بالمرادفات ، وما إلى ذلك من مظاهر التصلب ، أمرًا غير مألوف بالنسبة لواحدة حقيقية.
  
• بشكل عام ، لا يمكن للمرء أن يفشل في تكرار المألوف ، ولكن لا يصبح أقل صدقًا ، وهو أن مخطط البرمجة في لغة C ++ لا يزال يعتمد حرفيًا على الآثار الجانبية لأدوات اللغة ، التي كان الغرض الأصلي منها مختلفًا ، وحتى أبسط الأفكار على أساس نتيجة لذلك ، من الصعب التعبير عن metalanguage وقراءته ، وربط رمز القالب بالنظام القديم للملفات المضمّنة لا يسهل على مطور البرنامج ولا يقلل من مقدار الكود الذي تتم معالجته بواسطة المترجم.
  
  (من ناحية أخرى ، تجلب التحديثات التي تحدث بانتظام للدفع والانتشار الكثير من الحلول غير التافهة والمفيدة للغاية في كثير من الأحيان والحلول غير المتوقعة ، والتي تتيح حقًا كتابة تعليمات برمجية أكثر وضوحًا وصغيرًا بتكلفة أقل. ومع ذلك ، فإن دفق المنتجات الجديدة واسع جدًا وغير متكافئ ومنظم بشكل سيئ للغاية الإضافات إلى المكتبة القياسية ، حتى تلك الواضحة مثل الخيارات / application_visitor أو أي المذكورة أدناه ، إذا كانت المزايا المفاهيمية لتطبيقها في سياق مشروع معين ليست ذات صلة بديهيًا ، وبدون مساعدة من حدث سعيد ، يمكن أن تقع خارج نطاق التركيز لفترة طويلة ، إذا كنت لا تقضي جزءًا كبيرًا من وقت العمل في تتبع منتجات جديدة بشكل مدروس مباشرة ، ودراسة أمثلة غير تافهة لاستخدامها والمحاولات العقلية لتطبيقها على رمز موجود. للتعامل مع هذه المشكلة - للحفاظ على كل خمسة من مبرمجي C ++ يمارسون C ++ واحدًا - منظري لا يشغل سوى قضايا ذات أولوية المنتجات الجديدة ، وتنفيذها ستعقد في المشروع والممارسين التعليم انتقائي. الخلاصة: لا تقم بتشغيل C ++ - مشاريع مع عدد أقل من المطورين ).
  
• أخيرًا ، موضوعيًا ، المشكلة الأكثر خطورة التي تحدث عند العمل برمز BGL boilerplate . افترض أننا نستخدم بعض خوارزميات القوالب التي تجعل المرور عبر رسم بياني ويأخذ تمثيل الرسم البياني G كوسيطة. في الحالة النموذجية ، يعتمد هذا التمثيل على المرشحات المتراكبة على الرؤوس والحواف $$$F_v$. $$$F_e$ونظام الوزن $$$W$. للعمل مع الرسوم البيانية التي تمت تصفيتها ، تقدم BGL فئة قالب filter_graph المذكورة أعلاه ، وطريقة إرفاق نظام الوزن بها وفقًا لتقدير المستخدم. ممثلون يمثلون $$$F_v$. $$$F_e$و $$$W$قد تشمل المشاهدات التالية على الأقل:
  
  
  • مباشرة غلاف لدالة تمثل مخطط الترجيح ويتوقع تمثيل المرشحات (ببطء ، دون فقدان التهيئة) ؛
  • ذاكرات التخزين المؤقت فوق هذه الأغلفة ، ورسم خرائط واصفات الحافة / العقدة لمؤشرات الحافة / العقدة ، ومعالجة الصورة النقطية ومجموعة القيم (بدون خسائر التهيئة ، مع زيادة تدريجية في السرعة كما هو مستخدم) ؛
  • التعيين المباشر للواصف / الحافة واصفات القيمة المملوءة (يتطلب التهيئة ، ولكن يمكن بناؤه على أساس التمثيل السابق ؛ تصل السرعة إلى الحد الأقصى).
  
  وبالتالي ، إذا تمت كتابة هذه الخوارزمية بأسلوب تقليدي ، فإن ثلاثة محددات مع ثلاثة فروع على الأقل في كل منها ستظهر في نصها (والحاجة إلى ضبط الجسم عند ظهور تمثيلات جديدة). نظرًا لأن كل فرع من فروع الخوارزمية ، والذي ينفذ عددًا كبيرًا من المرات عند المرور بالرسم البياني ، يؤدي إلى ضياع ملحوظ للوقت ، فإن الرغبة في تجنب هذه الخسائر مع الحفاظ على الكود من نفس النمط التقليدي يمكن أن تؤدي إلى 27 تطبيقًا من الخوارزمية لمختلف مجموعات التمثيلات.
  
  يجب أن ينقذك نمط metaprogram من هذه المشاكل ، مما يسمح لك بدعم ملف تعريف واحد يصف الخوارزمية التي تنشئ ضمنيًا جميع التطبيقات الضرورية (وكذلك ، ربما ، وربما الكثير من التطبيقات غير الضرورية ، إذا كانت هياكل وقت تشغيل الكود لا تنشئ فعلًا بعض مجموعات الكتابة ، والتي ), .
  
  , , inline- , –O2. - ( 1:3 1:5, – , , ).
  
  , . . , ( ) , «» «» . , . : «» «» , «» , «» .
  
  , : , 100% , , «» . ( , , - , , , , , ).
  
• , , , . C++ , -, , .
  
  , , :
  
  

  void type_selector_fun(type_a a, type_b b, ...) { if (condition_1(a, b, ...)) { auto arg = get_type_1_obj(a, b, ...); run_calc(arg, a, b, ...); } else if (condition_1(a, b, ...)) { auto arg = get_type_2_obj(a, b, ...); run_calc(arg, a, b, ...); } else ... } 

  
  يمكن إعادة كتابتها بشكل أكثر إحكاما باستخدام المتغير <...> في النموذج التالي تقريبًا:
  
  

    void type_selector_fun(type_a a, type_b b, ...) { variant<type_1, type_2, ...> arg; if (condition_1(a, b, ...)) { arg = get_type_1_obj(a, b, ...); } else if ... ... apply_visitor([&](auto arg_){run_calc(arg_, a, b, ...); }, arg); } 

  
  عيب هذا النوع من الكتابة هو الحاجة إلى تعداد صريح لأنواع type_1 ، type_2 ، ... في الإعلان البديل. هذه الأنواع يمكن أن تكون مرهقة ، والتسجيل باستخدام decval / result_of_t يمكن أن يكون أقل تعقيدًا.
  
  عند استخدام أي ، ليست هناك حاجة لسرد أنواع ، ولكن لا توجد وسيلة للحصول على تطبيق التناظرية.
  
  استخدام بعض وظائف القالب make_variant ، والذي يسمح لك بكتابة كود من النوع التالي ، يوحي بنفسه:
  
  

    auto arg = make_variant ( bind(condition_1, a, b, ...), bind(get_type_1_obj, a, b, ...), bind(condition_2, a, b, ...), bind(get_type_2_obj, a, b, ...), ... ); 

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

    //   variant<...>      //  ,   : type_1, type_2 etc. variant<auto...> get_type_obj(typa_a a, type_b b, ...) { if (condition_1(a, b, ...)) { return get_type_1_obj(a, b, ...); } else if (condition_2(a, b, ...)) { return get_type_2_obj(a, b, ...); } else ... } 

  
  أو حتى:
  
  

    select_value_type(arg) { if (condition_1(a, b, ...)) { arg = get_type_1_obj(a, b, ...); } else ... ... } run_calc(arg, a, b, …); 

  
  الخيار الأخير ، على الرغم من أنه تم إزالته تمامًا من نمط C ++ ، إلا أنه يبدو الأكثر عملية ، حيث يمكن أن يكون هناك أكثر من متغير وسيط محدد للنوع ، ولا يوجد سبب لتوقع منطق بنائه .
  
• الجانب الآخر من نفس الموقف هو استخدام الهياكل المساعدة (على سبيل المثال ، التخزين المؤقت) التي تقوم بتنفيذ برنامج نصي يستحق اسم "متغير القالب" ، ولكنه يختلف عن الامتداد القياسي C ++ 14 الذي يحمل نفس الاسم.
  
  قد يبدو الرمز المقابل كالتالي:
  
  

    struct CacheHolder { boost::variant< container<T1>, container<T2>, // ... container<TN>> ct; template<typename T> struct result_type_selector { typedef typename if_c<is_compatible<T, T1>::value, T1, if_c<is_compatible<T, T2>::value, T2, // ... if_c<is_compatible<T, TN>::value, TN, std::decay_t<T>>>>::type type; }; template<typename T> auto get() const -> const container<typename result_type_selector<T>::type>& { return boost::get<container<typename result_type_selector<T>::type>>(ct); } }; 

  
  هنا ، كما ذكر أعلاه ، تعبر الإنشاءات الطويلة عن فكرة بسيطة للوصول إلى متغير يمثل ذاكرة التخزين المؤقت باسم محدد ، بغض النظر عن بُعد القيمة المخزنة مؤقتًا (المرور بشفرة عبر رمز الاتصال).
  
  للإيجاز ، يتم تقديم الكود للحالة عندما يكون هناك نوع واحد فقط يمكن أن يكون نشطًا ، ولكن في الممارسة العملية يكون الموقف أكثر شيوعًا عندما يمكن أن توجد عدة حاويات في وقت واحد (يمكن تنفيذه بسهولة بنفس الأسلوب باستخدام tuple واختياري).
  
  يفترض تطبيق الدالة get <...> أن رمز الاستدعاء لديه فكرة عن نوع القيمة المخزنة مؤقتًا التي يريد الوصول إليها (على سبيل المثال ، عدد صحيح أو نقطة عائمة).
  
  ليس أقل شيوعًا هو الموقف الذي لا تكون فيه قيمة النوع الدقيق مهمة للمتصل. في هذه الحالة ، يتم تشغيل البرنامج النصي select_value_type / application_visitor من الفقرة السابقة (تم ضبطه لتعدد القيم المحتمل ، مما يعني عرض الأنواع بترتيب تنازلي للأولوية).
  
• حتى الآن ، لم يتم ذكر أي PBGL تقريبًا في هذا النص. هذا ما يفسره تجربة المؤلف الصغيرة الضئيلة في التعامل مع هذا الجزء من المكتبة (فيما يتعلق يشير المؤلف نفسه ، مع بعض الشك ، إلى كل ما هو مكتوب أدناه في هذه الفقرة ، ويدعو الآخرين إلى نفس الشيء). في الواقع ، تتلخص هذه التجربة في العديد من التجارب ، على نفس النوع من مشاكل البحث التي أظهرت أن البيانات العملية تفقد نسخة موزعة إلى حل محلي 3-5 مرات في الذاكرة و 15-20 مرة في الأداء الكلي (تم توضيح أصل هذا الرقم المخيف هنا وتم التعليق عليه أيضًا في الفقرات التالية) . بالنظر إلى التعقيد الكبير للعمل مع الهياكل الموزعة ، كان الاختيار لصالح النسخة المحلية بديهيًا في مثل هذه الحالة.
  
  دعونا نوضح آليات عملية PBGL باستخدام مثال نموذجي لخوارزمية المشي دلتا. في هذه النسخة المتوازية من خوارزمية ديكسترا ، يتم استبدال قائمة الانتظار ذات الأولوية بمجموعة من "الجرافات". تتم معالجة العناصر التي تقع في "دلو" واحد بالتوازي. في شكله الأصلي ، يعد delta pacing خوارزمية نموذجية لأنظمة الذاكرة المشتركة.
  
  في الإصدار الموزع ، يحدث ما يلي: في PBGL ، عند التحميل ، يكون الرسم البياني مبعثرًا بين العمليات ، ولكل عملية نطاق متواصل من أرقام الرأس. وبالتالي ، من خلال رقم قمة الرأس العالمي ، من السهل معرفة العملية التي ينتمي إليها. وفقًا لذلك ، تخزن كل عملية في كل منعطف من الخوارزمية جزءًا من "الجرافة" التي تحتوي على الرؤوس التابعة لهذه العملية. تقوم جميع العمليات في وقت واحد بتحديد ومعالجة الرؤوس من أجزائها من "الجرافات" واحدًا تلو الآخر ، أثناء إرسال رسائل حول الحاجة إلى تحديث "الجرافات" التالية للعمليات التي تمتلك القمم المجاورة. من السهل أن نرى أن زيادة عدد العمليات تؤدي إلى زيادة عدد الرسائل التي يرسلونها. نتيجة لذلك ، لا يمكن تقليل وقت تنفيذ الخوارزمية فحسب ، بل يمكن زيادته أيضًا. على وجه الخصوص ، لن يؤدي إطلاق العديد من عمليات MPI لحل هذه المشكلة على جهاز فعلي واحد باحتمال معين إلا إلى زيادة في إجمالي حمل المعالج دون أي مكسب زمني.
  
  تجدر الإشارة إلى أن سرعة دلتا هي أسرع خوارزمية البحث الموزعة (من أصل ثلاثة تدعمها المكتبة).
  
  وبالتالي ، إذا لم يتم إعداد الرسم البياني مسبقًا ، فيجب تقسيمه إلى كتل ذات حجم أقصى ، كتلة واحدة لكل جهاز فعلي. من خلال التحضير الأولي ، نعني هنا إعادة ترقيم رؤوس الرسم البياني بحيث تتوافق النطاقات المستمرة للأرقام التي تستخدمها PBGL ، إن أمكن ، مع المخططات الفرعية المتصلة بشكل فضفاض. يتم استخدام حزم مثل METIS و paraMETIS و Zoltan لهذه الأغراض. من الصعب التعامل مع الرسوم البيانية الديناميكية في هذا الوضع.
  
  بشكل عام ، وفقًا لنتائج التجارب الموصوفة ، كان لدى المؤلف انطباع بأن التشغيل العادي لمجموعة PBGL لا يمكن تحقيقه إلا مع معدات اتصال خاصة ، ومن المنطقي استخدام الآلات مع أقل عدد ممكن من النوى وإنتاجية الخيوط القصوى كقنوات لهذه المجموعة. يجادل مؤلفو Trinity في مقالتهم بأن تخزينهم الموزع يعمل بكفاءة أكبر بكثير - ويجد المؤلف صعوبة في التعليق على هذا البيان ، ولكن ، في ضوء الظروف المذكورة أعلاه ، يجد أنه من الممكن تمامًا: تحمل بنية PBGL ختمًا مميزًا في الوقت الذي لم تتلق فيه الأجهزة متعددة النواة توزيعًا واسعًا بعد.
  
  تشارك PBGL أيضًا مشاكل الإصدار المفرد: بعض مزامنة الكود ، والوثائق والأمثلة ، التي تفاقمت بسبب التعقيد الأكبر للنظام وعدد أقل من المستخدمين الراغبين في تبادل الخبرات المفيدة.
  

BGL وغيرها من الحيوانات

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

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

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

بالنسبة للبدائل المحتملة ، تتضمن قائمتهم العناصر التالية على الأقل:

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

1. Graph DBMS (neo4j ، إلخ).
   
   تركز الأنظمة من هذا النوع على إجراء عمليات المعاملات على الرسوم البيانية الكبيرة (القرص الموزع). على الرغم من إمكانية تطوير واجهة برمجة التطبيقات لمثل هذا النظام بشكل كبير ، إلا أن سرعة تنفيذ خوارزميات الرسم البياني نفسها ، بقدر ما يمكن للمرء أن يحكم ، ليست هي الأولوية الأولى. قد لا يحاول النظام حتى تحميل الرسم البياني بأكمله في الذاكرة. لتعديل الرسم البياني والإجتياز ، يتم دعم اللغات التعريفية (SPARQL ، Cypher ، Gremlin). تعلق أهمية كبيرة على ضمان الاستمرارية مع أنظمة SQL التقليدية.
2. امتدادات الرسم البياني لأنظمة معالجة البيانات الكبيرة التي تعمل في الخريطة / تقلل من النموذج (GraphX ​​في Spark و Pegasus و Giraph for Hadoop) وأنظمة الكتلة المستقلة ( MS Trinity / MS Graph Engine ، GraphLab). يقوم أول من يقوم بتنفيذ عمليات على الرسم البياني بتطبيق نموذج Google Pregel (وليس فقط) ، ويمكن تهيئته للاستخدام بما في ذلك عقد الحوسبة المتوازية الهائلة. يمكن استخدام كل من هؤلاء والآخرين ، من بين أشياء أخرى ، كأساس لمشاريع برامج الشركات.
   
   على الرغم من إمكانية تطوير واجهة برمجة التطبيقات (API) لمثل هذه الأنظمة تمامًا (من بين أشياء أخرى ، يدعم GraphX ​​SPARQL و Cypher) ، ينصب التركيز الرئيسي عند العمل على حل مشكلات البنية الأساسية. يتميز GraphX ​​بعدم ثبات البيانات والتحيز في خطوط الأنابيب لجميع العمليات. لا يشتمل MS Trinity حاليًا على طرق رفيعة المستوى ولا يوفر سوى مجموعة من البدائل للعمل مع العقد والحواف. الأنظمة التي تعمل على قمة Hadoop ، من حيث المبدأ ، لا تُستخدم إلا قليلاً في حل مشاكل الرسم البياني التعسفي.
   
3. في الواقع مكتبات الأدوات العالمية التي تنفذ مجموعات أكثر أو أقل من الطرق (BGL / PBGL ، LEMON إلخ) ، بما في ذلك تلك المتوازية بشكل كبير (nvGraph ، Gunrock).
   
   بناءً عليها ، يمكن إنشاء أنظمة تطبيق تعمل على تكييف خوارزميات الرسم البياني مع مجالات مواضيع محددة.
4. الأنظمة والمكتبات المتخصصة في المشكلات المعقدة ذات الأهمية العالمية (METIS ، و PARMETIS ، و Zoltran: تقسيم الرسم البياني ، و GraphViz ، و Gephi: التصور ، و GraphBLAS: الخوارزميات الجبرية للعمل مع الرسوم البيانية ، إلخ).
   
   يمكن تعيين العديد من تطبيقات الرسوم البيانية المستقلة بشكل مشروط لهذه الفئة ، حيث يتطلب التحليل المفصل الكثير من الوقت. هذا الأخير يحتوي على تطبيقات من جميع الأصناف التي يمكن تصورها: الأكاديمية والتجارية ، المستخدم المفرد والمتعدد المستخدمين ، ظهرت مؤخراً ومتواجدة منذ أكثر من عقد ، إلخ.

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

الملاحظات

1. BGL ليست مكتبة رأس بحتة ، ولكن في الوقت الحالي ، الوظيفة الوحيدة التي تحتاج إلى الربط هي (اختياري إلى حد ما) العمل مع ملفات GraphViz DOT. لذلك ، في الغالبية العظمى من الحالات ، ليست هناك حاجة للربط والربط التلقائي مع الإصدار الصحيح من libbost-graph لتضمين رؤوس BGL في تكوين Boost غير متوفر. وبالتالي ، من أجل التناسق مع مكتبة libboost-regex المستخدمة من قبل وظائف BGL غير الرأسية ، من السهل توصيل رأس التعزيز \ regex.hpp من رمز المشروع ، حتى إذا كانت الأخيرة لا تستخدم التعبيرات العادية.
2. يتم تقديم فوضى إضافية من خلال وجود كيانات يشجع تكافؤها الواضح البحث عن القطط السوداء (ربما غائبة) في الغرف المظلمة .
3. قبل متابعة وصفه (باستخدام مثال محدد ، حيث تجلى بشكل خاص وبقوة غير سارة) ، نلاحظ أن المؤلف هو من بين الأشخاص المحظوظين القلائل نسبيًا الذين يعملون مع مشروع تم تحميله في نظام تشغيل Windows قوي وخط حفظه الله من مترجمي MSVC. من المحتمل أن تكون المشكلات الموضحة أدناه عبارة عن قطع أثرية من هذا النوع من المترجمين: مجموعة متنوعة من الظروف الخاصة تجعل من الصعب إجراء تجربة مقارنة مع gcc / clang في بيئة * nix. إذا كان الأمر كذلك ، يمكنك فقط تهنئة مستخدمي برامج التحويل البرمجي الأخرى.
4. لتليين أي في بعض الحالات ، ظهر في الآونة الأخيرة إذا كان من المحتمل أن يساعد.
5. في حالتنا ، أدى هذا إلى إيلاء اهتمام خاص لوظيفة توفير الحالة ، والتي تتيح تصحيح الأخطاء مع الراحة ، أوصل النظام أولاً إلى الحالة الأولية المطلوبة في تجميع محسن.
6. في ممارستي ، لأسباب مختلفة ، كانت هناك حاجة لتحويل معلمات وقت التشغيل إلى وسيطات قوالب ، وفي كثير من الأحيان اضطررت إلى اللجوء إلى طرق معقدة للغاية بدقة (مستوحاة من التطبيقات التي عفا عليها الزمن الآن لتعزيز typeof وتعزيز لامدا ل C ++ 98 ، والتي ضربت مباشرة تعامل مع تقنية البرمجة في C ++ كحل للحذف) ، من بينها النجم يسلط الضوء على اختيار الوسيطة بتقسيمها إلى نصفين ، ولكن بشكل عام ، كانت المشاكل الرئيسية في مثل هذه العمليات مرتبطة دائمًا بعدم القدرة على التصدير النوع المحدد خارج النطاق ، مما أدى إلى أنماط غريبة.
7. ( — 80 4 50 200 , ) ( ) - . , . , 6-8 — , .
8. , . ( , - , . , , , , , , , ).
9. , , – , , «» (-- ..) . ( , ), , «» , — ( ). , , , - . , , : «» ( ) , «» ( ), , . . , - , « », . , « » ? , , , : – , , , , .
10. . , , .
11. «LIBNAME C++ graph» , stackoverflow. , BGL 500 [boost-graph].