في الأجزاء السابقة, ) تحدثنا عن الكرات الأرضية كأشجار ، في هذا واحد سننظر إلى الكرات الأرضية كمصفوفات متفرقة.
هو نوع من المصفوفة تأخذ فيه معظم القيم نفس القيمة.
من الناحية العملية ، غالبًا ما توجد مصفوفات ضخمة متفرقة بحيث لا معنى لاحتلال الذاكرة بنفس العناصر. لذلك ، من المنطقي تنفيذ المصفوفات المتناثرة بطريقة لا تنفق فيها الذاكرة على تخزين قيم متطابقة.
في بعض لغات البرمجة ، تعتبر المصفوفات المتفرقة جزءًا من اللغة نفسها ، , . لغات البرمجة الأخرى لها مكتبات خاصة تسمح لك بتنفيذها. لـ C ++ - وآخرون.
تعد Globals مرشحة جيدة لتنفيذ المصفوفات المتفرقة للأسباب التالية:
- إنهم يخزنون قيم العقد المحددة فقط ولا يخزنون قيم غير محددة ؛
- تشبه واجهة الوصول إلى قيمة العقدة إلى حد كبير عدد لغات البرمجة التي تنفذ الوصول إلى عنصر من مصفوفة متعددة الأبعاد.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global عبارة عن بنية منخفضة المستوى إلى حد ما لتخزين البيانات ، وبالتالي فهي تتمتع بخصائص سرعة متميزة (من مئات الآلاف إلى عشرات الملايين من المعاملات في الثانية ، اعتمادًا على الأجهزة ، انظر أدناه). )
نظرًا لأن الهيكل العالمي عبارة عن بنية ثابتة ، فمن المنطقي إنشاء مصفوفات متفرقة عليها عندما يكون معروفًا مسبقًا أن حجم ذاكرة الوصول العشوائي لن يكون كافياً.
تتمثل إحدى خصائص تطبيقات الصفيف المتفرقة في إرجاع بعض القيم الافتراضية إذا كان الوصول إلى خلية غير محددة.
يمكن القيام بذلك باستخدام الوظيفة في COS. في هذا المثال ، يتم اعتبار المصفوفة ثلاثية الأبعاد.
SET a = $GET(^a(x,y,z), defValue)ما المهام التي تتطلب مصفوفات متفرقة وكيف يمكن أن تساعد الكرة الأرضية؟
مصفوفة الجوار (التوصيل)
تستخدم لتمثيل الرسوم البيانية:
من الواضح أنه كلما كان التمثيل البياني أكبر ، زاد عدد الأصفار في المصفوفة. على سبيل المثال ، إذا أخذنا رسمًا بيانيًا لشبكة اجتماعية وقمنا بتمثيلها في شكل مصفوفة مماثلة ، فكلها تقريبًا ستتكون من الأصفار ، أي سيكون مجموعة متفرقة.
Set ^m(id1, id2) = 1
Set ^m(id1, id3) = 1
Set ^m(id1, id4) = 1
Set ^m(id1) = 3
Set ^m(id2, id4) = 1
Set ^m(id2, id5) = 1
Set ^m(id2) = 2
....
في هذا المثال ، نقوم بحفظ ملفات ^m مصفوفة الاتصال ، وكذلك عدد الحواف في كل عقدة (من هو الأصدقاء مع من وعدد الأصدقاء).
إذا كان عدد العناصر في الرسم البياني لا يزيد عن 29 مليون (يتم أخذ هذا الرقم على أنه حاصل ضرب 8 * ) ، أي أن الطريقة الأكثر اقتصادا لتخزين مثل هذه المصفوفات هي سلاسل بت ، حيث يتم تحسين الفجوات الكبيرة بطريقة خاصة في تنفيذها.
يتم تنفيذ التلاعب بسلاسل البت بواسطة الوظيفة .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
دولة آلة القفز الجدول
نظرًا لأن الرسم البياني لانتقال آلة الحالة هو رسم بياني عادي ، فإن جدول انتقال آلة الحالة هو نفس مصفوفة التقارب التي تمت مناقشتها أعلاه.
خلية مستقلة
أشهر الروبوتات الخلوية ، والتي ، بسبب قواعدها (عندما يكون للخلية العديد من الجيران ، تموت) هي مجموعة متفرقة.
ستيفن ولفرام ، يعتقد أن الأوتوماتا الخلوية كذلك . في عام 2002 ، نشر نوعًا جديدًا من العلوم ، وهو كتاب من 1280 صفحة ، حيث يجادل على نطاق واسع بأن التطورات في الأوتوماتا الخلوية ليست معزولة ، ولكنها مستقرة جدًا وذات أهمية كبيرة لجميع مجالات العلوم.
ثبت أن أي خوارزمية يمكن تنفيذها على جهاز كمبيوتر يمكن تنفيذها باستخدام جهاز آلي خلوي. تُستخدم الأتمتة الخلوية لنمذجة البيئات والأنظمة الديناميكية ، لحل المشكلات الخوارزمية ، ولأغراض أخرى.
إذا كان لدينا مجال ضخم واحتجنا إلى تسجيل جميع الحالات الوسيطة من الإنسان الخلوي ، فمن المعقول تمامًا استخدام الكرات الأرضية.
رسم الخرائط
أول ما يتبادر إلى ذهني عندما يتعلق الأمر باستخدام المصفوفات المتناثرة هو تعيين المهام.
كقاعدة عامة ، هناك الكثير من المساحات الفارغة على البطاقات. إذا تم تمثيل الخريطة على أنها وحدات بكسل كبيرة ، فسيشغل المحيط 71٪ من بكسلات الأرض. مجموعة متفرقة. وإذا قمت بتطبيق أعمال أيدي البشر فقط ، فسيكون هناك أكثر من 95٪ من المساحة الفارغة.
بالطبع ، لا أحد يخزن الخرائط كمصفوفات نقطية ، يتم استخدام تمثيل متجه.
لكن ما هي خرائط المتجهات؟ هذا نوع من الإطارات والخطوط المتعددة والمضلعات التي تتكون من نقاط.
في الواقع قاعدة بيانات للنقاط والتواصل فيما بينها.
واحدة من أكثر مهام رسم الخرائط طموحًا هي مهمة رسم خرائط تلسكوب Gaia لمجرتنا. من الناحية المجازية ، مجرتنا ، مثل الكون بأسره ، عبارة عن مجموعة متفرقة متواصلة: مساحات شاسعة من الفراغ ، حيث توجد نقاط صغيرة نادرة - نجوم. مساحة فارغة 99,999999 …….٪. لتخزين خريطة مجرتنا ، تم اختيار قاعدة بيانات على globals - Caché.
لا أعرف الهيكل الدقيق للكرة الأرضية في هذا المشروع ، يمكنني أن أفترض أنه شيء مشابه لـ:
Set ^galaxy(b, l, d) = 1; Номер звезды по каталогу, если есть
Set ^galaxy(b, l, d, "name") = "Sun"
Set ^galaxy(b, l, d, "type") = "normal" ; варианты blackhole, quazar, red_dwarf и т.д.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercury"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
أين ب ، ل ، د والبعد عن الشمس.
يسمح لك الهيكل المرن للكرة الأرضية بحفظ أي خصائص مرغوبة للنجوم والكواكب ، نظرًا لأن القواعد الموجودة على الكواكب لا تحتوي على مخطط.
لتخزين خريطة لكوننا ، تم اختيار Caché ليس فقط بسبب مرونته ، ولكن أيضًا بسبب قدرته على حفظ تدفق البيانات بسرعة كبيرة ، أثناء إنشاء فهرس عالمي على طول الطريق لإجراء عمليات بحث سريعة.
إذا عدنا إلى الأرض ، فقد تم إنشاء مشاريع رسم الخرائط على الكرة الأرضية وشوكة من OpenStreetMap - .
في الآونة الأخيرة تم تنفيذ الفهارس الجغرافية المكانية . نحن في انتظار مقالات مع تفاصيل التنفيذ من المؤلفين.
تنفيذ الفهارس المكانية العالمية في OpenStreetMap XAPI
الصور مأخوذة من .
تنقسم الكرة الأرضية بأكملها إلى مربعات ، ثم مربعات فرعية ، ومربعات فرعية إلى مربعات فرعية فرعية ، وهكذا. بشكل عام ، نحصل على هيكل هرمي لتخزين الكرات الأرضية التي تم إنشاؤها.
في أي وقت ، يمكننا طلب المربع المطلوب على الفور تقريبًا أو مسحه ، بينما سيتم أيضًا إرجاع أو مسح جميع المربعات الفرعية.
يمكن تنفيذ مثل هذا المخطط على الكرة الأرضية بعدة طرق.
الخيار 1:
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idПервойТочки
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idВторойТочки
...الخيار 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...في كلتا الحالتين ، ليس من الصعب طلب نقاط تقع في مربع من أي مستوى في COS / M. سيكون من الأسهل إلى حد ما مسح قطع مربعة من المساحة من أي مستوى في الخيار الأول ، لكن هذا نادرًا ما يكون ضروريًا.
مثال على أحد المربعات ذات المستوى الأدنى:
وإليك بعض الكرات الأرضية من مشروع XAPI: تمثيل الفهرس على الكرة الأرضية:
عالمي ^ الطريق تستخدم لتخزين النقاط (الطرق والأنهار الضحلة وما إلى ذلك) والمضلعات (المناطق المغلقة: المباني والغابات وما إلى ذلك).
تصنيف تقريبي لاستخدام المصفوفات المتفرقة على الكرة الأرضية.
- نقوم بتخزين إحداثيات كائنات معينة وحالاتها (الخرائط ، الأوتوماتا الخلوية)
- نقوم بتخزين المصفوفات المتفرقة.
بالنسبة للحالة 2) عند طلب إحداثيات معينة حيث لا يتم تعيين قيمة للعنصر ، يجب أن نحصل على قيمة عنصر المصفوفة المتفرقة افتراضيًا.
المكافآت التي نحصل عليها عند تخزين المصفوفات متعددة الأبعاد في الكرة الأرضية
حذف سريع و / أو اختيار قطع من المساحة ، ومضاعفات الأوتار ، والطائرات ، والمكعبات ، إلخ. بالنسبة للحالات التي يتم فيها استخدام فهارس الأعداد الصحيحة ، قد يكون من المفيد أن تكون قادرًا على إزالة و / أو تحديد أجزاء من المساحة التي تكون مضاعفات السلاسل والمستويات والمكعبات وما إلى ذلك.
فريق يمكننا حذف كل من عنصر واحد وسطر ، وحتى مستوى كامل. بفضل خصائص الكرة الأرضية ، هذا سريع جدًا - أسرع بآلاف المرات من حذف عنصر تلو الآخر.
يوضح الشكل مصفوفة ثلاثية الأبعاد في المستوى العالمي ^a وأنواع مختلفة من عمليات الحذف.
لتحديد أجزاء من المسافة بواسطة فهارس معروفة ، يمكنك استخدام الأمر .
تحديد عمود مصفوفة في متغير العمود:
; Зададим трёхмерный разреженный массив 3x3x3
Set ^a(0,0,0)=1,^a(2,2,0)=1,^a(2,0,1)=1,^a(0,2,1)=1,^a(2,2,2)=1,^a(2,1,2)=1
Merge Column = ^a(2,2)
; Выведем переменную Column
Zwrite Column
الخلاصة:
Column(0)=1
Column(2)=1
ما هو مثير للاهتمام في متغير العمود ، لدينا أيضًا مصفوفة متفرقة ، والتي يجب أيضًا الوصول إليها من خلال ، لأنه لا يتم تخزين القيم الافتراضية فيه.
يمكن أيضًا أخذ عينات من أجزاء من المساحة من خلال برنامج صغير باستخدام الوظيفة . هذا مناسب بشكل خاص في المساحات التي لم يتم تحديد مؤشراتها كميًا (رسم الخرائط).
اختتام
تحدد الأوقات الحالية مهام جديدة طموحة. يمكن أن تحتوي الرسوم البيانية على بلايين من الرؤوس ، ويمكن أن تحتوي الخرائط على بلايين النقاط ، وقد يرغب شخص ما في تشغيل كونه الخاص على الأوتوماتا الخلوية (, ).
عندما لا يمكن أن تتناسب كمية بيانات المصفوفات المتناثرة مع ذاكرة الوصول العشوائي ، وتحتاج إلى العمل معها ، فإن الأمر يستحق النظر في إمكانية تنفيذ مثل هذه المشاريع على الكرة الأرضية و COS.
شكرًا لكم على اهتمامكم! نحن في انتظار أسئلتك ورغباتك في التعليقات.
إخلاء المسئولية: هذه المقالة وتعليقاتي عليها هي رأيي ولا تمثل الموقف الرسمي لشركة InterSystems Corporation.
المصدر: www.habr.com