For Gauche 0.9.5


Next: , Previous: , Up: ライブラリモジュール - ユーティリティ   [Contents][Index]

12.14 data.sparse - 疎なデータコンテナ

Module: 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からの 警告を目にしたなら、疎テーブルへの切り替えを考えてみましょう。


Next: , Previous: , Up: 疎なデータコンテナ   [Contents][Index]

12.14.1 疎なベクタ

Class: <sparse-vector-base>

疎なベクタの抽象ベースクラスです。<dictionary><collection>を 継承しています。<sequence>は継承していないことに注意してください。 疎なベクタは整数でインデクス可能ですが、インデクスの順番に要素にアクセスする手段を 持っていません。

疎なベクタは、<vector>と同様、任意のSchemeオブジェクトを格納可能である ものもあれば、<s8vector>等と同様に特定の範囲の数値のみ格納可能なものもあります。 全ての疎なベクタは同一セットのAPIで利用可能です。

疎なベクタはまた、コレクションAPIとディクショナリAPIを実装しています。これらについては コレクションフレームワークおよびディクショナリフレームワークを 参照してください。

Class: <sparse-vector>
Class: <sparse- TAGvector>

疎なベクタの具体クラスです。それぞれ<sparse-vector-base>を継承します。

<sparse-vector>のインスタンスは任意のSchemeオブジェクトを格納できます。

TAGs8, u8, s16, u16, s32, u32, s64, u64, f16, f32, f64のいずれかで、 それぞれの疎なベクタの格納可能な値は、gauche.uvectorの 対応する<TAGvector>に準じます(ユニフォームベクタ参照)。 つまり、<sparse-u8vector>の要素には0以上255以下の正確な整数を 格納できます。

Function: make-sparse-vector :optional type :key default

空の疎なベクタを作成して返します。type引数は#f(デフォルト)か、 <sparse-vector-base>のサブクラスのどれか、 あるいはシンボルs8, u8, s16, u16, s32, u32, s64, u64, f16, f32, f64のいずれかを 指定できます。

typeが省略されるか#fの場合は<sparse-vector>のインスタンスが 作られます。typeがクラスであればそのインスタンスが、またシンボルであれば、 対応する<sparse-TAGvector>のインスタンスが作られます。

キーワード引数defaultによって、作成するベクタの要素既定値を指定できます。 この引数が与えられると、ベクタは全てあらかじめその値で埋められているかのように 振る舞います (ただしイテレータは陽にセットされた値のみ取り出します)。

キーワード引数を与える場合、それに先立って省略可能引数も与える必要が あることに注意してください。

(define v (make-sparse-vector 'u8 :default 128))

(sparse-vector-ref v 0) ⇒ 128
Function: sparse-vector-max-index-bits

実装が利用できる、疎なベクタのインデックスの最大のビット数を返します。 例えばこれが32を返したなら、インデックスとして(expt 2 32)まで 使えるということです。この値は最低でも32であることが保証されています。

以下のエントリにおいて、引数svは疎なベクタのインスタンスです。 他のオブジェクトが渡された場合はエラーが報告されます。

Function: sparse-vector-copy sv

疎なベクタsvのコピーを返します。

Function: sparse-vector-ref sv k :optional fallback

疎なベクタsvのインデックスkにある要素を返します。 kは正確な整数でなければなりません。

kに対応する要素がない場合は、次のように振る舞います。

Function: sparse-vector-set! sv k value

疎なベクタsvk番めの要素にvalueを設定します。 kは非負の正確な整数で、許される最大のインデックス以下でなければなりません。

Function: sparse-vector-num-entries sv

svの持つ要素数を返します。

Function: sparse-vector-exists? sv k

svk番目のエントリが値を持っていれば#tを、 そうでなければ#fを返します。 #t

Function: sparse-vector-delete! sv k

svk番目のエントリが値を持っていれば、それを消去して #tを返します。 そうでなければ何もせずに#fを返します。

Function: sparse-vector-clear! sv

疎なベクタを空にします。

Function: sparse-vector-inc! sv k delta :optional (fallback 0)

これは次のコードと同じ動作をしますが、数値を格納する疎ベクタでは特に 効率よく動作します。

(sparse-vector-set! sv k (+ (sparse-vector-ref sv k fallback) delta))

もし加算の結果がsvに許される数値の範囲を越えた場合は、 エラーが投げられます。将来はそういった場合に値をクランプするオプションも 用意する予定です。

Function: sparse-vector-update! sv k proc :optional fallback
Function: sparse-vector-push! sv k val
Function: sparse-vector-pop! sv k :optional fallback

疎なベクタのエントリの値を取り出してアップデートするパターンを 簡単に書くためのルーチンです。それぞれ、hash-table-update!hash-table-push!hash-table-pop!と 同じように動作します。(ハッシュテーブル参照)。

The following procedures traverses a sparse vector. Note that elements are not visited in the order of index; it’s just like hash table traversers.

At this moment, if you want to walk a sparse vector with increasing/decreasing index order, you have to get a list of keys by sparse-vector-keys, sort it, then use it to retrieve values. We may add an option in future to make-sparse-vector so that those walk operation will be more convenient.

Function: sparse-vector-fold sv proc seed

For each entry in sv, calls proc as (proc k_n v_n seed_n), where k_n is an index and v_n is a value for it, and seed_n is the returned value of the previous call to proc if n >= 1, and seed if n = 0. Returns the value of the last call of proc.

Function: sparse-vector-for-each sv proc
Function: sparse-vector-map sv proc

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.

Function: sparse-vector-keys sv
Function: sparse-vector-values sv

Returns a list of all keys and all values in sv, respectively.


Next: , Previous: , Up: 疎なデータコンテナ   [Contents][Index]

12.14.2 疎行列

疎行列は要素が2つの非負整数でインデックスされること以外は疎なベクタと同じです。

註:この疎行列の実装は、事前に構造が分かっていない疎な行列をそれなりに空間効率良く 扱うことを目的としています(例えば、2Dのマップにランドマークを記録してゆく、 といったイメージです)。もし探しているものが、数値計算用に特定の構造を持つ疎行列の 実装でしたら、このモジュールは速度的に十分ではないでしょう。

現在の実装では、それぞれのインデックスの最大ビット数が sparse-vector-max-index-bitsの半分までという制限があります。 将来はこの制限をなくす予定です。

Class: <sparse-matrix-base>

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.

Class: <sparse-matrix>
Class: <sparse- TAGmatrix>

The actual sparce matrix classes. Inherits <sparse-matrix-base>. An instance of <sparse-matrix> can contain any Scheme objects.

TAG 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 <TAGvector> class in gauche.uvector (see ユニフォームベクタ). That is, <sparse-u8matrix> can have exact integer values between 0 and 255.

Function: make-sparse-matrix :optional type :key default

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-TAGmatrix> 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.

Function: sparse-matrix-num-entries mat

Returns the number of entries explicitly set in a sparse matrix mat.

Function: sparse-matrix-ref mat x y :optional fallback

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.

Function: sparse-matrix-set! mat x y value

Set value to the sparse matrix mat at the location (x, y).

Function: sparse-matrix-exists? mat x y

Returns #t iff the sparse matrix mat has a value at (x, y).

Function: sparse-matrix-clear! mat

Empties the sparse matrix mat.

Function: sparse-matrix-delete! mat x y

Remove the value at (x, y) from the sparse matrix mat.

Function: sparse-matrix-copy mat

Returns a fresh copy of mat.

Function: sparse-matrix-update! mat x y proc :optional fallback

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.

Function: sparse-matrix-inc! mat x y delta :optional fallback
(sparse-matrix-update! mat x y (cut + <> delta) fallback)
Function: sparse-matrix-push! mat x y val
(sparse-matrix-update! mat x y (cut cons val <>) '())
Function: sparse-matrix-pop! mat x y
(rlet1 r #f
  (sparse-matrix-update! mat x y (^p (set! r (car p)) (cdr p))))
Function: sparse-matrix-fold mat proc seed

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.

Function: sparse-matrix-map mat proc
(sparse-matrix-fold sv (^[x y v s] (cons (proc x y v) s)) '()))
Function: sparse-matrix-for-each mat proc
(sparse-matrix-fold sv (^[x y v _] (proc x y v)) #f))
Function: sparse-matrix-keys mat
(sparse-matrix-fold sv (^[x y _ s] (cons (list x y) s)) '())
Function: sparse-matrix-values mat
(sparse-matrix-fold sv (^[x y v s] (cons v s)) '())

Previous: , Up: 疎なデータコンテナ   [Contents][Index]

12.14.3 疎なテーブル

Class: <sparse-table>

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.)

Function: make-sparse-table comparator

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.

Function: sparse-table-comparator st

Returns the comparator used in the sparse table st.

Function: sparse-table-copy st

Returns a copy of a sparse table st.

Function: sparse-table-num-entries st

Returns the number of entries in a sparse table st.

Function: sparse-table-ref st key :optional fallback

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.

Function: sparse-table-set! st key value

Sets value with key in st.

Function: sparse-table-exists? st key

Returns #t if an entry with key exists in st, #f otherwise.

Function: sparse-table-delete! st key

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.

Function: sparse-table-clear! st

Empties st.

Function: sparse-table-update! st key proc :optional fallback
Function: sparse-table-push! st key val
Function: sparse-table-pop! st key :optional fallback
Function: sparse-table-fold st proc seed
Function: sparse-table-for-each st proc
Function: sparse-table-map st proc
Function: sparse-table-keys st
Function: sparse-table-values st

Previous: , Up: 疎なデータコンテナ   [Contents][Index]