在前面的部分(
在實踐中,稀疏數組通常非常巨大,以至於用相同的元素佔用記憶體是沒有意義的。因此,以這樣的方式實作稀疏數組是有意義的,這樣記憶體就不會浪費在儲存相同的值上。
在某些程式語言中,稀疏數組包含在語言本身中,
- 它們只儲存某些節點的值,不儲存未定義節點的值;
- 存取節點值的介面與許多程式語言實作對多維數組元素的存取極為相似。
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3)
- Global 是一個相當低階的資料儲存結構,因此它具有出色的速度特性(從每秒數十萬到數千萬個事務,取決於硬件,請參見下文)。
1 )
由於全域是一個持久性結構,因此當事先知道 RAM 量不夠時,在其上建立稀疏數組是有意義的。
稀疏數組實現的屬性之一是,如果存取未定義的單元格,則傳回一些預設值。
這可以使用函數來實現
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)
狀態機轉換表
由於有限自動機的轉移圖是普通圖,因此有限自動機的轉移表就是上面討論的相同的鄰接矩陣。
元胞自動機
最著名的元胞自動機是
Stephen Wolfram 認為元胞自動機
已經證明,任何在計算機上可執行的演算法都可以使用元胞自動機來實現。元胞自動機用於對動態環境和系統進行建模、解決演算法問題以及用於其他目的。
如果我們有一個巨大的欄位並且需要記錄元胞自動機的所有中間狀態,那麼使用全域變數是有意義的。
製圖學
當談到使用稀疏數組時,我首先想到的是映射任務。
一般來說,地圖上有很多空白區域。如果地圖被表示為大像素,那麼地球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 中全域空間索引的實現
圖片取自
整個地球被劃分為正方形,然後是子正方形,子正方形又分為子子正方形,依此類推。一般來說,我們得到一個層次結構來儲存創建的全域變數。
在任何時刻,我們幾乎可以立即要求所需的方塊或清除它,並且所有子方塊也將被返回或清除。
類似的全域方案可以透過多種方式實現。
選項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,但您需要使用它們時,那麼值得考慮在全域變數和 COS 上實現類似專案的可能性。
感謝您的關注!我們正在等待您在評論中提出問題和願望。
免責聲明: 本文以及我對其的評論僅代表我的觀點,與 InterSystems Corporation 的官方立場無關。
來源: www.habr.com