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のいずれかで、
それぞれの疎なベクタの格納可能な値は、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のいずれかを
指定できます。
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}
Calls proc with index and value, e.g. (proc k value),
for each element of sv.
The results of proc are discarded by sparse-vector-for-each,
and gathered to a list and returned by sparse-vector-map.
{data.sparse}
それぞれ、sv中の全てのキー、または全ての値をリストにして返します。
疎行列は要素が2つの非負整数でインデックスされること以外は疎なベクタと同じです。
註：この疎行列の実装は、事前に構造が分かっていない疎な行列をそれなりに空間効率良く 扱うことを目的としています(例えば、2Dのマップにランドマークを記録してゆく、 といったイメージです)。もし探しているものが、数値計算用に特定の構造を持つ疎行列の 実装でしたら、このモジュールは速度的に十分ではないでしょう。
現在の実装では、それぞれのインデックスの最大ビット数が
sparse-vector-max-index-bitsの半分までという制限があります。
将来はこの制限をなくす予定です。
{data.sparse}
An abstract base class of sparse matrixes. Inherits <collection>.
Like sparse vectors, a sparse matrix can be of type that can store any Scheme objects, or that can store only certain types of numbers.
All of these sparse matrix subtypes can be accessed by the same API.
{data.sparse}
The actual sparse matrix classes. Inherits <sparse-matrix-base>.
An instance of <sparse-matrix> can contain any Scheme objects.
@ is either one of s8, u8,
s16, u16, s32, u32,
s64, u64, f16, f32, or f64.
The range of values an instance of those classes can hold
is the same as the corresponding <@vector> class
in gauche.uvector (see ユニフォームベクタ). That is,
<sparse-u8matrix> can have exact integer values
between 0 and 255.
{data.sparse}
Creates an empty sparse matrix. The type argument can be
#f (default), one of subclasses of <sparse-matrix-base>,
or a symbol of either one of s8, u8,
s16, u16, s32, u32,
s64, u64, f16, f32, or f64.
If type is omitted or #f, a <sparse-matrix> is
created. If it is a class, an instance of the class is created
(It is an error to pass a class that is not a subclass of
<sparse-matrix-base>.)
If it is a symbol, an instance of corresponding <sparse-@matrix>
is created.
You can specify the default value of the matrix by default keyword argument. If given, the vector behaves as if it is filled with the default value (but the matrix iterator only picks the values explicitly set).
Note that you have to give the optional argument as well to specify the keyword argument.
{data.sparse}
Returns the number of entries explicitly set in a sparse matrix mat.
{data.sparse}
Returns an element indexed by (x, y) in a sparse matrix mat.
If the indexed element isn’t set, fallback is returned if provided;
otherwise, if the matrix has the default value, it is returned; otherwise,
an error is raised.
{data.sparse}
Set value to the sparse matrix mat at the location
(x, y).
{data.sparse}
Returns #t iff the sparse matrix mat has a value at
(x, y).
{data.sparse}
Empties the sparse matrix mat.
{data.sparse}
Remove the value at (x, y) from the sparse matrix mat.
{data.sparse}
Returns a fresh copy of mat.
{data.sparse}
Call proc with the value at (x, y) of the sparse matrix,
and sets the result of proc as the new value of the location.
The optional fallback argument works just like sparse-matrix-ref;
if provided, it is passed to proc in case the
matrix doesn’t have a value at (x, y).
If fallback isn’t provided and the matrix doesn’t have a value
at the location, the default value of the matrix is used if it has one.
Otherwise, an error is signalled.
{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}
Loop over values in the sparse matrix mat. The procedure
proc is called with four arguments, x, y, val
and seed, for each index (x, y) which has the value
val. The initial value of seed is the one given to
sparse-matrix-fold, and the result of proc is passed
as the next seed value. The last result of proc is returned
from sparse-matrix-fold.
The procedure proc is only called on the entries that’s actually has a value, and the order of which the procedure is called is undefined.
{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}
A class for sparse table. Inherits <dictionary> and
<collection>.
Operationally sparse tables are the same as hash tables, but the former consumes less memory in trade of slight slower access. (Roughly x1.5 to x2 access time when the table is small. As the table gets larger the difference becomes smaller.)
{data.sparse}
Creates and returns an empty sparse table.
The comparator argument specifies how to compare and hash keys;
it must be either a comparator (see 基本的な比較器),
or one of the symbols eq?, eqv?, equal? and
string=?, like hash tables (see ハッシュテーブル). If it is a symbol,
eq-comparator, eqv-comparator, equal-comparator or
string-comparator are used, respectively.
{data.sparse}
Returns the comparator used in the sparse table st.
{data.sparse}
Returns a copy of a sparse table st.
{data.sparse}
Returns the number of entries in a sparse table st.
{data.sparse}
Retrieves a value associated to the key in st.
If no entry with key exists, fallback is returned
when it is provided, or an error is signaled otherwise.
{data.sparse}
Sets value with key in st.
{data.sparse}
Returns #t if an entry with key exists in st,
#f otherwise.
{data.sparse}
Deletes an entry with key in st if it exists.
Returns #t if an entry is actually deleted, or #f
if there hasn’t been an entry with key.
{data.sparse}
Empties st.
{data.sparse}