גלובלים הם חרבות אוצר לאחסון נתונים. מערכים דלילים. חלק 3

בחלקים הקודמים (1, 2) דיברנו על גלובלים כעצים, בזה נסתכל על גלובלים כעל מערכים דלילים.

מערך דליל הוא סוג של מערך שבו רוב הערכים מקבלים את אותו הערך.

בפועל, מערכים דלילים הם לרוב כה ענקיים שאין טעם לכבוש את הזיכרון באלמנטים זהים. לכן, הגיוני ליישם מערכים דלילים בצורה כזו שהזיכרון לא יתבזבז על אחסון ערכים זהים.
בשפות תכנות מסוימות, מערכים דלילים כלולים בשפה עצמה, למשל ב-J, MATLAB. לשפות תכנות אחרות יש ספריות מיוחדות המאפשרות לך ליישם אותן. עבור C++ - איגן וכו '

גלובלים הם מועמדים טובים להטמעת מערכים דלילים מכיוון:

1. הם מאחסנים את הערכים של צמתים מסוימים בלבד ואינם מאחסנים את הערכים של לא מוגדרים;
2. הממשק לגישה לערך של צומת דומה מאוד לכמה שפות תכנות מיישמות גישה לאלמנט מערך רב מימדי.

   Set ^a(1, 2, 3)=5
   Write ^a(1, 2, 3)

3. גלובל הוא מבנה ברמה נמוכה למדי לאחסון נתונים, ולכן יש לו מאפייני מהירות יוצאי דופן (ממאות אלפי עד עשרות מיליוני עסקאות בשנייה, תלוי בחומרה, ראה להלן). 1)

מכיוון שהגלובל הוא מבנה מתמשך, הגיוני ליצור עליהם מערכים דלילים כאשר ידוע מראש שכמות ה-RAM לא תספיק.

אחד המאפיינים של יישומי מערך דל הוא החזרת ערך ברירת מחדל כלשהו אם מתבצעת גישה לתא לא מוגדר.

ניתן ליישם זאת באמצעות הפונקציה $GET ב-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 עמודים, A New Kind of Science, שבו הוא טוען בהרחבה שההתקדמות באוטומטים הסלולריים אינה מבודדת, אלא מתמשכת ויש לה השלכות גדולות על כל תחומי המדע.

הוכח שניתן ליישם כל אלגוריתם בר הפעלה במחשב באמצעות אוטומט סלולרי. אוטומטיות סלולריות משמשות למודל של סביבות ומערכות דינמיות, לפתרון בעיות אלגוריתמיות ולמטרות אחרות.

אם יש לנו שדה ענק ואנחנו צריכים לתעד את כל מצבי הביניים של אוטומט סלולרי, אז הגיוני להשתמש בגלובלים.

קַרטוֹגרָפִיָה

הדבר הראשון שעולה לי בראש כשזה מגיע לשימוש במערכים דלילים הוא משימות מיפוי.

ככלל, יש הרבה מקום ריק במפות. אם המפה מיוצגת כפיקסלים גדולים, אז 71% מהפיקסלים של כדור הארץ יהיו תפוסים על ידי האוקיינוס. מערך דליל. ואם אתה מיישם רק עבודות של ידיים אנושיות, אז החלל הריק יהיה יותר מ-95%.

כמובן, אף אחד לא מאחסן מפות בצורה של מערכי רסטר; נעשה שימוש בייצוג וקטור.
אבל מהן מפות וקטוריות? זהו מעין מסגרת ופולי קווים ומצולעים המורכבים מנקודות.
בעצם מסד נתונים של נקודות וקשרים ביניהן.

אחת ממשימות המיפוי השאפתניות ביותר היא משימת טלסקופ גאיה למיפוי הגלקסיה שלנו. באופן פיגורטיבי, הגלקסיה שלנו, כמו היקום כולו, היא מערך דליל מתמשך: מרחבים עצומים של ריקנות שבהם יש נקודות קטנות נדירות - כוכבים. שטח ריק הוא 99,999999…….%. לאחסון מפת הגלקסיה שלנו, נבחר מסד נתונים גלובלי - 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
...

איפה b, l, d קואורדינטות גלקטיות קו רוחב, קו אורך והמרחק לשמש.

המבנה הגמיש של גלובלים מאפשר לך לשמור את כל המאפיינים הדרושים של כוכבים וכוכבי לכת, מכיוון שהבסיסים על גלובלים הם חסרי סכמה.

כדי לאחסן את מפת היקום שלנו, Caché נבחר לא רק בגלל הגמישות שלו, אלא גם בגלל היכולת שלו לאחסן זרם של נתונים במהירות רבה, ובו זמנית ליצור אינדקס גלובלי לחיפושים מהירים.

אם נחזור לכדור הארץ, אז נוצרו פרויקטים קרטוגרפיים על גלובלים OpenStreetMap XAPI ומזלג של OpenStreetMap - FOSM.

לאחרונה על מטמון האקאתון הוטמעו אינדקסים גיאו-מרחביים Geospatial. אנו מחכים למאמר מהכותבים עם פרטי יישום.

יישום אינדקסים מרחביים על גלובלי ב-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: ייצוג של אינדקס על גלובלים:

גלוֹבָּלִי ^דרך משמש לאחסון נקודות פולי קווים (כבישים, נהרות קטנים וכו') ומצולעים (שטחים סגורים: מבנים, יערות וכו').

סיווג גס של השימוש במערכים דלילים בגלובלים.

1. אנו מאחסנים את הקואורדינטות של אובייקטים מסוימים ומצביהם (מיפוי, אוטומטים סלולריים)
2. אנו מאחסנים מטריצות דלילות.

במקרה 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 הוא שיש לנו גם מערך דל, שאליו יש לגשת גם דרך $GET, שכן ערכי ברירת מחדל אינם מאוחסנים בו.

בחירת פיסות שטח יכולה להיעשות גם באמצעות תוכנית קטנה באמצעות הפונקציה $Order. זה נוח במיוחד במרחבים שהמדדים שלהם אינם מכונטים (קרטוגרפיה).

מסקנה

הזמנים הנוכחיים מציבים משימות שאפתניות חדשות. גרפים יכולים להיות מורכבים ממיליארדי קודקודים, מפות המורכבות ממיליארדי נקודות, וחלקם אולי אפילו ירצו להפעיל את היקום שלהם על אוטומטים סלולריים (1, 2).

כאשר נפח הנתונים ממערכים דלילים כבר לא יכול להתאים ל-RAM, אבל אתה צריך לעבוד איתם, אז כדאי לשקול את האפשרות של יישום פרויקטים דומים על גלובלים ו-COS.

תודה לך על תשומת הלב! אנחנו מחכים לשאלות ולרצונות שלך בתגובות.

כתב ויתור: מאמר זה וההערות שלי עליו הם דעתי ואינם מייצגים את העמדה הרשמית של InterSystems Corporation.

מקור: www.habr.com