グローバルはデータを保存するための伝家の宝刀です。 スパース配列。 パート 3

前のパート (1, 2) グローバルをツリーとして説明しましたが、今回はグローバルをスパース配列として見ていきます。

スパース配列 ほとんどの値が同じ値をとる配列の一種です。

実際には、疎配列は非常に巨大であることが多いため、同一の要素でメモリを占有することに意味がありません。 したがって、同一の値を格納するためにメモリが無駄にならないような方法でスパース配列を実装することは理にかなっています。
一部のプログラミング言語では、スパース配列が言語自体に含まれています。 たとえばJでは, マトラブ。 他のプログラミング言語には、それらを実装できる特別なライブラリがあります。 C++ の場合 - 固有値 ら。

グローバルは、次の理由から、スパース配列を実装するのに適した候補です。

1. 特定のノードの値のみを保存し、未定義のノードの値は保存しません。
2. ノードの値にアクセスするためのインターフェイスは、多くのプログラミング言語が多次元配列要素へのアクセスを実装する方法と非常によく似ています。

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

3. Global はデータを保存するためのかなり低レベルの構造であるため、優れた速度特性を備えています (ハードウェアに応じて XNUMX 秒あたり数十万から数千万のトランザクション。以下を参照)。 1)

グローバルは永続的な構造であるため、RAM の量が十分ではないことが事前にわかっている場合は、グローバル上にスパース配列を作成することが理にかなっています。

スパース配列実装の特性の XNUMX つは、未定義のセルにアクセスした場合にデフォルト値を返すことです。

これは関数を使用して実装できます $GET 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 * の積として解釈されます) 最大行サイズ)、つまり、そのような行列を格納するさらに経済的な方法はビット文字列です。ビット文字列の実装は特別な方法で大きなギャップを最適化するためです。

ビット文字列の操作は関数によって実行されます。 $ BIT.

; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)

ステートマシン遷移テーブル

有限オートマトンの遷移グラフは通常のグラフであるため、有限オートマトンの遷移テーブルは上で説明したのと同じ隣接行列になります。

セルオートマトン

最も有名なセルオートマトンは ゲーム「ライフ」、そのルール (セルに多くの隣接セルがある場合、そのセルは消滅します) により、これは疎な配列です。

スティーブン・ウルフラム氏は、セルオートマトンは 新しい科学分野。 2002 年、彼は 1280 ページの本『A New Kind of Science』を出版し、その中でセル オートマトンの進歩は孤立したものではなく永続的であり、科学のあらゆる分野に多大な影響を及ぼしていると広く主張しています。

コンピュータ上で実行可能なアルゴリズムはすべて、セル オートマトンを使用して実装できることが証明されています。 セル オートマトンは、動的な環境やシステムをモデル化し、アルゴリズムの問​​題を解決したり、その他の目的で使用されます。

巨大なフィールドがあり、セル オートマトンのすべての中間状態を記録する必要がある場合は、グローバルを使用するのが合理的です。

地図作成

スパース配列の使用に関して最初に思い浮かぶのは、タスクのマッピングです。

原則として、マップには空きスペースがたくさんあります。 地図が大きなピクセルで表される場合、地球のピクセルの 71% が海によって占められることになります。 スパース配列。 そして、人間の手による作品だけを適用すると、空きスペースは95％以上になります。

もちろん、マップをラスター配列の形式で保存する人は誰もおらず、ベクトル表現が使用されます。
しかし、ベクトル マップとは何でしょうか? これはフレームの一種であり、点で構成されるポリラインやポリゴンです。
本質的には、ポイントとそれらの間の接続のデータベースです。

最も野心的な地図作成ミッションの 99,999999 つは、銀河の地図を作成するガイア望遠鏡のミッションです。 比喩的に言えば、私たちの銀河は、全宇宙と同様に、連続したまばらな配列、つまり、まれな小さな点、つまり星が存在する巨大な空の空間です。 空きスペースはXNUMX…….%です。 私たちの銀河の地図を保存するために、グローバル データベースである 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é が選ばれたのは、その柔軟性だけでなく、データのストリームを非常に迅速に保存できると同時に、高速検索のためのインデックス グローバルを作成できるという点でもありました。

私たちが地球に戻ったら、地図作成プロジェクトは地球上で作成されました。 オープンストリートマップXAPI そしてOpenStreetMapのフォーク - FOSM.

最近オン ハッカソン 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 を使用して、任意のレベルの正方形にあるポイントを要求することは難しくありません。 最初のオプションでは、任意のレベルの正方形のスペースをクリーンアップする方がいくらか簡単ですが、これが必要になることはほとんどありません。

下位レベルの正方形の XNUMX つの例:

ここでは、XAPI プロジェクトのいくつかのグローバルを示します。 グローバルのインデックスの表現:

グローバル ^ウェイ ポイントの保管に使用されます ポリライン (道路、小さな川など) とポリゴン (閉鎖されたエリア: 建物、森林など)。

グローバルでのスパース配列の使用の大まかな分類。

1. 特定のオブジェクトの座標とその状態 (マッピング、セル オートマトン) を保存します。
2. スパース行列を保存します。

ケース 2) の場合、要素に値が割り当てられていない特定の座標をリクエストする場合、デフォルトのスパース配列要素の値を取得する必要があります。

多次元行列をグローバルに保存するときに得られるボーナス

行、平面、立方体などの倍数である空間の部分をすばやく削除および/または選択します。 整数インデックスが使用される場合、行、平面、立方体などの倍数である空間のチャンクを迅速に削除および/またはフェッチできる機能が役立つ場合があります。

チーム 殺します 単一の要素または行を削除したり、平面全体を削除したりすることもできます。 グローバルのプロパティのおかげで、これは非常に迅速に行われ、要素ごとに削除するよりも数千倍速くなります。

この図は、グローバル内の XNUMX 次元配列を示しています。 ^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デフォルト値は保存されていないためです。

スペースの一部の選択は、関数を使用する小さなプログラムを通じて行うこともできます。 $注文。 これは、インデックスが量子化されていない空間 (地図作成) で特に便利です。

まとめ

現在の時代は、新たな野心的な課題を提起しています。 グラフは数十億の頂点で構成され、マップは数十億の点で構成され、セル オートマトンで独自のユニバースを実行したいと思う人もいるかもしれません (1, 2).

スパース配列からのデータ量が RAM に収まらないが、スパース配列を操作する必要がある場合は、グローバルと COS に同様のプロジェクトを実装する可能性を検討する価値があります。

ご清聴ありがとうございました！ ご質問やご希望はコメントにてお待ちしております。

免責事項: この記事およびそれに対する私のコメントは私の意見であり、インターシステムズ株式会社の公式見解とは一切関係がありません。

出所： habr.com