در قسمت های قبلی (, ) در مورد جهانی ها به عنوان درخت صحبت کردیم، در این یکی به جهانی ها به عنوان آرایه های پراکنده نگاه خواهیم کرد.
نوعی آرایه است که در آن بیشتر مقادیر یک مقدار را می گیرند.
در عمل، آرایه های پراکنده اغلب آنقدر بزرگ هستند که استفاده از حافظه با عناصر یکسان فایده ای ندارد. بنابراین، پیاده سازی آرایه های پراکنده به گونه ای منطقی است که حافظه برای ذخیره مقادیر یکسان تلف نشود.
در برخی از زبان های برنامه نویسی، آرایه های پراکنده در خود زبان گنجانده شده است. , . سایر زبان های برنامه نویسی دارای کتابخانه های ویژه ای هستند که به شما امکان پیاده سازی آنها را می دهد. برای C++ - غیره
Global ها کاندیدهای خوبی برای پیاده سازی آرایه های پراکنده هستند زیرا:
- آنها فقط مقادیر گره های خاصی را ذخیره می کنند و مقادیر تعریف نشده را ذخیره نمی کنند.
- رابط برای دسترسی به مقدار یک گره بسیار شبیه به تعداد زبان های برنامه نویسی است که دسترسی به یک عنصر آرایه چند بعدی را اجرا می کنند.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global یک ساختار نسبتاً سطح پایین برای ذخیره داده ها است، بنابراین دارای ویژگی های سرعت برجسته است (از صدها هزار تا ده ها میلیون تراکنش در ثانیه، بسته به سخت افزار، در زیر ببینید). )
از آنجایی که global یک ساختار پایدار است، ایجاد آرایه های پراکنده بر روی آنها منطقی است زمانی که از قبل مشخص شده باشد که مقدار RAM کافی نخواهد بود.
یکی از ویژگی‌های پیاده‌سازی آرایه پراکنده این است که در صورت دسترسی به یک سلول تعریف‌نشده، مقداری پیش‌فرض را برگردانند.
این را می توان با استفاده از تابع پیاده سازی کرد در COS. این مثال یک آرایه 3 بعدی را در نظر می گیرد.
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٪ خواهد بود.
البته هیچ کس نقشه ها را در قالب آرایه های شطرنجی ذخیره نمی کند، از نمایش برداری استفاده می شود.
اما نقشه های برداری چیست؟ این یک نوع قاب و چند خط و چند ضلعی است که از نقاط تشکیل شده است.
اساسا یک پایگاه داده از نقاط و ارتباطات بین آنها.
یکی از جاه طلبانه ترین ماموریت های نقشه برداری، ماموریت تلسکوپ گایا برای نقشه برداری از کهکشان ما است. به بیان تصویری، کهکشان ما، مانند کل جهان، یک آرایه پراکنده پیوسته است: فضاهای خالی عظیمی که در آن نقاط کوچک نادری وجود دارد - ستارگان. فضای خالی 99,999999…….٪ است. برای ذخیره نقشه کهکشان ما، یک پایگاه داده جهانی انتخاب شد - Cache.
من ساختار دقیق جهانی ها در این پروژه را نمی دانم، می توانم حدس بزنم که چیزی شبیه به:
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
...
جایی که b، l، d هستند و فاصله تا خورشید
ساختار انعطاف‌پذیر جهانی‌ها به شما امکان می‌دهد تا هرگونه ویژگی ضروری ستاره‌ها و سیارات را ذخیره کنید، زیرا پایه‌های جهانی‌ها بدون طرح هستند.
برای ذخیره نقشه جهان ما، Cache نه تنها به دلیل انعطاف پذیری، بلکه به دلیل توانایی آن در ذخیره سریع جریانی از داده ها، در حالی که به طور همزمان جهانی های شاخص برای جستجوهای سریع ایجاد می کند، انتخاب شد.
اگر به زمین برگردیم، پروژه های نقشه برداری روی جهانی ها ایجاد شد و یک انشعاب 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 و انواع مختلف حذف
برای انتخاب قطعات فضا با استفاده از شاخص های شناخته شده، می توانید از دستور استفاده کنید .
انتخاب یک ستون ماتریس در متغیر Column:
; Зададим трёхмерный разреженный массив 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
نکته جالب در مورد متغیر Column این است که یک آرایه پراکنده نیز داریم که باید از طریق آن نیز به آن دسترسی داشت. ، زیرا مقادیر پیش فرض در آن ذخیره نمی شود.
انتخاب قطعات فضا نیز می تواند از طریق یک برنامه کوچک با استفاده از تابع انجام شود . این امر به ویژه در فضاهایی که شاخص‌های آنها کوانتیزه نشده است (کارتوگرافی) راحت است.
نتیجه
زمان کنونی وظایف بلندپروازانه جدیدی را مطرح می کند. نمودارها می توانند از میلیاردها رئوس، نقشه ها از میلیاردها نقطه تشکیل شده باشند، و برخی ممکن است حتی بخواهند جهان خود را بر روی اتوماتای سلولی اجرا کنند., ).
وقتی حجم داده‌های آرایه‌های پراکنده دیگر نمی‌تواند در حافظه RAM قرار گیرد، اما باید با آنها کار کنید، پس ارزش اجرای پروژه‌های مشابه در globals و COS را دارد.
با تشکر از توجه شما! منتظر سوالات و خواسته های شما در نظرات هستیم.
سلب مسئولیت: این مقاله و نظرات من در مورد آن نظر من است و هیچ ارتباطی با موضع رسمی InterSystems Corporation ندارد.
منبع: www.habr.com