data.sparse - 疎なデータコンテナ ¶このモジュールは、非負整数でインデックスされる空間効率の良いデータ構造である 疎ベクタ (sparse vector)と 疎行列 (sparse matrix)、 および 疎ベクタを格納領域に用いるハッシュテーブルである疎テーブル (sparse table) を提供します。
疎ベクタは非負整数のインデックスと値を関連付けます。
整数でインデックスされるので名前にベクタがついていますが、
連続するメモリに置かれる配列ではなく、むしろ連想配列のようなものです。
(内部的には、現在の実装はコンパクトなトライを使っています)。
少なくとも2^32-1までのインデックスが使えることは保証されています。
実装が許す最大のインデックスのビット長は
sparse-vector-max-index-bitsで得ることができます。
(将来的にはこの制限を無くす計画です)。
通常のベクタと違い、疎ベクタは作る時に大きさを指定する必要がありません。 サポートされている範囲内ならどんなインデックスにでも単に値を格納できます。
(define v (make-sparse-vector)) (sparse-vector-set! v 0 'a) (sparse-vector-ref v 0) ⇒ a (sparse-vector-set! v 100000000 'b) (sparse-vector-ref v 100000000) ⇒ b ;; set! also work (set! (sparse-vector-ref v 100) 'c) (sparse-vector-ref v 100) ⇒ c
値がセットされていない要素にアクセスすると、デフォルトではエラーが通知されます。
ベクタごとに既定値を設定したり、
sparse-vector-refの省略可能引数にフォールバック値を
渡すことでエラーを回避できます。
(sparse-vector-ref v 1) ⇒ error
(sparse-vector-ref v 1 'noval) ⇒ noval
(let1 w (make-sparse-vector #f :default 'x)
(sparse-vector-ref w 1)) ⇒ x
疎行列は、二つの整数でインデックスされるという点以外は疎なベクタと同じです。
疎テーブルはハッシュテーブルと同じように動作しますが、キーのハッシュ値を インデックスとして値を疎ベクタに格納しています。
これらの疎なデータコンテナの主な目的は、メモリ効率です。 ベクタに値を入れておきたいけれどごく一部のインデックスしか使わないことが 分かっている、と言った場合に、巨大なベクタをアロケートしてその大部分を 使わないでおくのは明らかに無駄でしょう。ただそれだけではありません。 Gaucheのガベージコレクタは、一続きの巨大なメモリ領域を確保するのとあまり 相性が良くありません。大きなベクタを大量に使うとGCのオーバヘッドが急速に増えます。 Gaucheの組み込みハッシュテーブルは データストアに通常のベクタを使っているのですが、 大量のデータを詰め込むとその効果が目に見えてきます。ヒープサイズが急に増え、 GCはより頻繁に走り、しかも一回一回に要する時間は長くなるでしょう。 一方で、疎テーブルは大量のデータに対してもかなり安定に動作します。
疎なデータコンテナは、単純なデータコンテナに比べるとアクセスにオーバヘッドはあります。 通常のハッシュテーブルより若干遅いですし、通常のベクタと比べるとかなり遅いです。 けれども、テーブル内のデータ数が大きくなる領域では、通常のハッシュテーブルの アクセス時間の方が急速に悪化するため、いずれ二つのアクセス時間は そこそこ同じになります。
どちらを使うべきかはアプリケーションに依存します。良く分からないのであれば、 ベンチマークを取りましょう。簡単な基準としては、数万以上のエントリを持つ ハッシュテーブルを数個以上作るなら、疎テーブルの方が良くなるかもしれません。 実行中に“repeated allocation of large blocks”というGCからの 警告を目にしたなら、疎テーブルへの切り替えを考えてみましょう。
| • 疎なベクタ: | ||
| • 疎行列: | ||
| • 疎なテーブル: |
{data.sparse}
疎なベクタの抽象ベースクラスです。<dictionary>と<collection>を
継承しています。<sequence>は継承していないことに注意してください。
疎なベクタは整数でインデクス可能ですが、インデクスの順番に要素にアクセスする手段を
持っていません。
疎なベクタは、<vector>と同様、任意のSchemeオブジェクトを格納可能である
ものもあれば、<s8vector>等と同様に特定の範囲の数値のみ格納可能なものもあります。
全ての疎なベクタは同一セットのAPIで利用可能です。
疎なベクタはまた、コレクションAPIとディクショナリAPIを実装しています。これらについては
gauche.collection - コレクションフレームワークおよびgauche.dictionary - ディクショナリフレームワークを
参照してください。
{data.sparse}
疎なベクタの具体クラスです。それぞれ<sparse-vector-base>を継承します。
<sparse-vector>のインスタンスは任意のSchemeオブジェクトを格納できます。
@は s8, u8,
s16, u16, s32, u32,
s64, u64, f16, f32, f64,
c32, c64, c128のいずれかで、
それぞれの疎なベクタの格納可能な値は、gauche.uvectorの
対応する<@vector>に準じます(ユニフォームベクタ参照)。
つまり、<sparse-u8vector>の要素には0以上255以下の正確な整数を
格納できます。
{data.sparse}
空の疎なベクタを作成して返します。type引数は#f(デフォルト)か、
<sparse-vector-base>のサブクラスのどれか、
あるいはシンボルs8, u8,
s16, u16, s32, u32,
s64, u64, f16, f32, f64,
c32, c64, c128のいずれかを指定できます。
typeが省略されるか#fの場合は<sparse-vector>のインスタンスが
作られます。typeがクラスであればそのインスタンスが、またシンボルであれば、
対応する<sparse-@vector>のインスタンスが作られます。
キーワード引数defaultによって、作成するベクタの要素既定値を指定できます。 この引数が与えられると、ベクタは全てあらかじめその値で埋められているかのように 振る舞います (ただしイテレータは陽にセットされた値のみ取り出します)。
キーワード引数を与える場合、それに先立って省略可能引数も与える必要が あることに注意してください。
(define v (make-sparse-vector 'u8 :default 128)) (sparse-vector-ref v 0) ⇒ 128
{data.sparse}
実装が利用できる、疎なベクタのインデックスの最大のビット数を返します。
例えばこれが32を返したなら、インデックスとして(expt 2 32)まで
使えるということです。この値は最低でも32であることが保証されています。
以下のエントリにおいて、引数svは疎なベクタのインスタンスです。 他のオブジェクトが渡された場合はエラーが報告されます。
{data.sparse}
疎なベクタsvのコピーを返します。
{data.sparse}
疎なベクタsvのインデックスkにある要素を返します。
kは正確な整数でなければなりません。
kに対応する要素がない場合は、次のように振る舞います。
{data.sparse}
疎なベクタsvのk番めの要素にvalueを設定します。
kは非負の正確な整数で、許される最大のインデックス以下でなければなりません。
{data.sparse}
svの持つ要素数を返します。
{data.sparse}
svのk番目のエントリが値を持っていれば#tを、
そうでなければ#fを返します。
#t
{data.sparse}
svのk番目のエントリが値を持っていれば、それを消去して
#tを返します。
そうでなければ何もせずに#fを返します。
{data.sparse}
疎なベクタを空にします。
{data.sparse}
これは次のコードと同じ動作をしますが、数値を格納する疎ベクタでは特に
効率よく動作します。
(sparse-vector-set! sv k (+ (sparse-vector-ref sv k fallback) delta))
もし加算の結果がsvに許される数値の範囲を越えた場合は、 エラーが投げられます。将来はそういった場合に値をクランプするオプションも 用意する予定です。
{data.sparse}
疎なベクタのエントリの値を取り出してアップデートするパターンを
簡単に書くためのルーチンです。それぞれ、hash-table-update!、
hash-table-push!、hash-table-pop!と
同じように動作します。(ハッシュテーブル参照)。
以下の手続きは疎なベクタの要素を横断します。 要素は必ずしもインデックスの順に訪問されるわけではないことに注意してください。 その点ではハッシュテーブルの横断と似ています。
今のところ、疎なベクタをインデックスの昇順/降順に処理したい場合は、
sparse-vector-keysで全てのキーを得て、
それをソートしたもので順に値を取り出してゆくしかありません。
将来は、make-sparse-vectorにオプションをつけて
インデックスの順番による横断を簡単にするかもしれません。
{data.sparse}
svの各エントリに対し、手続きprocを
(proc k_n v_n seed_n)のように呼び出してゆきます。
ここでseed_nはn >= 1の時は直前のprocの戻り値、
n = 0の時は引数seedです。
最後のprocの戻り値を返します。
{data.sparse}
svの各要素について、procをインデックスと値を引数にして
(proc k value)のように呼び出します。
sparse-vector-for-eachではprocの結果は捨てられ、
sparse-vector-mapでは結果がリストに集められて返されます。
{data.sparse}
それぞれ、sv中の全てのキー、または全ての値をリストにして返します。
疎行列は要素が2つの非負整数でインデックスされること以外は疎なベクタと同じです。
註：この疎行列の実装は、事前に構造が分かっていない疎な行列をそれなりに空間効率良く 扱うことを目的としています(例えば、2Dのマップにランドマークを記録してゆく、 といったイメージです)。もし探しているものが、数値計算用に特定の構造を持つ疎行列の 実装でしたら、このモジュールは速度的に十分ではないでしょう。
現在の実装では、それぞれのインデックスの最大ビット数が
sparse-vector-max-index-bitsの半分までという制限があります。
将来はこの制限をなくす予定です。
{data.sparse}
疎な行列の抽象ベースクラスです。<collection>を継承しています。
疎なベクタと同様に、疎な行列には任意のSchemeオブジェクトを格納できるものと、 特定の範囲の数値を格納できるものがあります。
全ての疎な行列のサブタイプへのアクセスには同じAPIが使えます。
{data.sparse}
疎な行列の具体クラスです。それぞれ<sparse-matrix-base>を継承します。
<sparse-matrix>のインスタンスは任意のSchemeオブジェクトを格納できます。
@は s8, u8,
s16, u16, s32, u32,
s64, u64, f16, f32, f64,
c32, c64, c128のいずれかで、
それぞれの疎な行列の格納可能な値は、gauche.uvectorの
対応する<@vector>に準じます(ユニフォームベクタ参照)。
つまり、<sparse-u8matrix>の要素には0以上255以下の正確な整数を
格納できます。
{data.sparse}
空の疎な行列を作成して返します。type引数は#f(デフォルト)か、
<sparse-matrix-base>のサブクラスのどれか、
あるいはシンボルs8, u8,
s16, u16, s32, u32,
s64, u64, f16, f32, f64,
c32, c64, c128のいずれかを指定できます。
typeが省略されるか#fの場合は<sparse-matrix>のインスタンスが
作られます。typeがクラスであればそのインスタンスが、またシンボルであれば、
対応する<sparse-@matrix>のインスタンスが作られます。
キーワード引数defaultによって、作成する行列の要素既定値を指定できます。 この引数が与えられると、行列は全てあらかじめその値で埋められているかのように 振る舞います (ただしイテレータは陽にセットされた値のみ取り出します)。
キーワード引数を与える場合、それに先立って省略可能引数も与える必要が あることに注意してください。
{data.sparse}
疎な行列matに明示的にセットされたエントリの数を返します。
{data.sparse}
疎な行列matの(x, y)で指される要素を返します。
その要素がセットされていなかった場合、fallbackが与えられていれば
それが返され、そうでなければ、行列のデフォルト値が返されます。
行列がデフォルト値も持っていなければエラーが投げられます。
{data.sparse}
疎な行列matの(x, y)にvalueをセットします。
{data.sparse}
疎な行列matの(x, y)に明示的に値がセットされていれば#tを、
そうでなければ#fを返します。
{data.sparse}
疎な行列matを空にします。
{data.sparse}
疎な行列matの(x, y)の要素を取り除きます。
{data.sparse}
matのコピーを新たに作って返します。
{data.sparse}
疎な行列の(x, y)の要素の値を引数にしてprocを呼び出し、
その返り値を新たな値としてセットします。
省略可能なfallbackはsparse-matrix-refと同様です。
(x, y)に要素がセットされていない時、
fallbackが与えられていればそれががprocに渡されます。
fallbackが与えられず、しかし配列のデフォルト値が設定されていれば
そのデフォルト値がprocに渡されます。
デフォルト値も設定されていなければエラーが投げられます。
{data.sparse}
(sparse-matrix-update! mat x y (cut + <> delta) fallback)
{data.sparse}
(sparse-matrix-update! mat x y (cut cons val <>) '())
{data.sparse}
(rlet1 r #f (sparse-matrix-update! mat x y (^p (set! r (car p)) (cdr p))))
{data.sparse}
疎な行列matの要素についてループします。
procはmatの各インデックス(x, y)とその場所の値val
について、4つの引数 x、y、val、seedで呼ばれます。
最初のseedはsparse-matrix-foldに渡されたseedであり、
procの返り値が次の呼び出しのseedに渡されてゆきます。
最後のprocの返り値がsparse-matrix-foldの返り値となります。
procは、明示的にセットされたエントリに対してのみ呼ばれます。 また、それが呼ばれる順序は不定です。
{data.sparse}
(sparse-matrix-fold sv (^[x y v s] (cons (proc x y v) s)) '()))
{data.sparse}
(sparse-matrix-fold sv (^[x y v _] (proc x y v)) #f))
{data.sparse}
(sparse-matrix-fold sv (^[x y _ s] (cons (list x y) s)) '())
{data.sparse}
(sparse-matrix-fold sv (^[x y v s] (cons v s)) '())
{data.sparse}
疎なテーブルのクラスです。<dictionary>と
<collection>を継承しています。
操作から見ると、疎なテーブルはハッシュテーブルと同じです。 ただ、アクセスが多少遅いかわりに、メモリ消費量が抑えられます。 (テーブルが小さいうちは、およそ1.5〜2倍アクセスが遅いですが、 デーブルが大きくなるにつれ差は縮まります。)
{data.sparse}
空の疎なテーブルを作って返します。
comparatorは、キーの比較とハッシュに使われる比較器
(基本的な比較器参照)、もしくはシンボル
eq?、eqv?、equal?、string=?のいずれかです
(これはハッシュテーブルと同じです。ハッシュテーブル参照)。
シンボルの場合は、それぞれ
eq-comparator、eqv-comparator、equal-comparator、
string-comparatorが使われます。
{data.sparse}
疎なテーブルstの比較器を返します。
{data.sparse}
疎なテーブルstのコピーを作って返します。
{data.sparse}
疎なテーブルstのエントリ数を返します。
{data.sparse}
疎なテーブルst中の、キーkeyに関連付けられた値を返します。
キーがテーブル中にない場合、fallbackが与えられればそれが返され、
与えられなければエラーが投げられます。
{data.sparse}
疎なテーブルstに、キーkeyと値valueの関連づけを格納します。
{data.sparse}
疎なテーブルstに、キーkeyを持つエントリがあれば
#tを、なければ#fを返します。
{data.sparse}
疎なテーブルstから、キーkeyを持つエントリを削除します。
エントリが実際に削除されたら#tお、エントリがもともと存在しなければ
#fを返します。
{data.sparse}
疎なテーブルstを空にします。
{data.sparse}