(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 v 1)        ⇒ error
(sparse-vector-ref v 1 'noval) ⇒ noval

(let1 w (make-sparse-vector #f :default 'x)
  (sparse-vector-ref w 1))     ⇒ x

12.24.1 疎なベクタ

Class: <sparse-vector-base> ¶

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

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

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

Class: <sparse-vector> ¶

Class: <sparse-@vector> ¶

{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以下の正確な整数を 格納できます。

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

{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

Function: sparse-vector-max-index-bits ¶

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

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

Function: sparse-vector-copy sv ¶

{data.sparse} 疎なベクタsvのコピーを返します。

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

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

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

• fallback引数が与えられていればそれを返します。
• そうでなく、ベクタが既定値を持っていれば、それを返します。
• そうでなければ、エラーが報告されます。

Function: sparse-vector-set! sv k value ¶

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

Function: sparse-vector-num-entries sv ¶

{data.sparse} svの持つ要素数を返します。

Function: sparse-vector-exists? sv k ¶

{data.sparse} svのk番目のエントリが値を持っていれば#tを、 そうでなければ#fを返します。 #t

Function: sparse-vector-delete! sv k ¶

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

Function: sparse-vector-clear! sv ¶

{data.sparse} 疎なベクタを空にします。

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

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

(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 ¶

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

以下の手続きは疎なベクタの要素を横断します。 要素は必ずしもインデックスの順に訪問されるわけではないことに注意してください。 その点ではハッシュテーブルの横断と似ています。

今のところ、疎なベクタをインデックスの昇順/降順に処理したい場合は、 sparse-vector-keysで全てのキーを得て、 それをソートしたもので順に値を取り出してゆくしかありません。 将来は、make-sparse-vectorにオプションをつけて インデックスの順番による横断を簡単にするかもしれません。

Function: sparse-vector-fold sv proc seed ¶

{data.sparse} svの各エントリに対し、手続きprocを (proc k_n v_n seed_n)のように呼び出してゆきます。 ここでseed_nはn >= 1の時は直前のprocの戻り値、 n = 0の時は引数seedです。 最後のprocの戻り値を返します。

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

Function: sparse-vector-map sv 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.

Function: sparse-vector-keys sv ¶

Function: sparse-vector-values sv ¶

{data.sparse} それぞれ、sv中の全てのキー、または全ての値をリストにして返します。

---

12.24.2 疎行列

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

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

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

Class: <sparse-matrix-base> ¶

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

Class: <sparse-matrix> ¶

Class: <sparse-@matrix> ¶

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

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

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

Function: sparse-matrix-num-entries mat ¶

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

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

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

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

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

Function: sparse-matrix-exists? mat x y ¶

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

Function: sparse-matrix-clear! mat ¶

{data.sparse} Empties the sparse matrix mat.

Function: sparse-matrix-delete! mat x y ¶

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

Function: sparse-matrix-copy mat ¶

{data.sparse} Returns a fresh copy of mat.

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

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

Function: sparse-matrix-inc! mat x y delta :optional fallback ¶

{data.sparse}

(sparse-matrix-update! mat x y (cut + <> delta) fallback)

Function: sparse-matrix-push! mat x y val ¶

{data.sparse}

(sparse-matrix-update! mat x y (cut cons val <>) '())

Function: sparse-matrix-pop! mat x y ¶

{data.sparse}

(rlet1 r #f
  (sparse-matrix-update! mat x y (^p (set! r (car p)) (cdr p))))

Function: sparse-matrix-fold mat proc seed ¶

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

Function: sparse-matrix-map mat proc ¶

{data.sparse}

(sparse-matrix-fold sv (^[x y v s] (cons (proc x y v) s)) '()))

Function: sparse-matrix-for-each mat proc ¶

{data.sparse}

(sparse-matrix-fold sv (^[x y v _] (proc x y v)) #f))

Function: sparse-matrix-keys mat ¶

{data.sparse}

(sparse-matrix-fold sv (^[x y _ s] (cons (list x y) s)) '())

Function: sparse-matrix-values mat ¶

{data.sparse}

(sparse-matrix-fold sv (^[x y v s] (cons v s)) '())

---

12.24.3 疎なテーブル

Class: <sparse-table> ¶

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

Function: make-sparse-table comparator ¶

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

Function: sparse-table-comparator st ¶

{data.sparse} Returns the comparator used in the sparse table st.

Function: sparse-table-copy st ¶

{data.sparse} Returns a copy of a sparse table st.

Function: sparse-table-num-entries st ¶

{data.sparse} Returns the number of entries in a sparse table st.

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

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

Function: sparse-table-set! st key value ¶

{data.sparse} Sets value with key in st.

Function: sparse-table-exists? st key ¶

{data.sparse} Returns #t if an entry with key exists in st, #f otherwise.

Function: sparse-table-delete! st key ¶

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

Function: sparse-table-clear! st ¶

{data.sparse} 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 ¶

{data.sparse}

Function: sparse-table-fold st proc seed ¶

Function: sparse-table-for-each st proc ¶

Function: sparse-table-map st proc ¶

{data.sparse}

Function: sparse-table-keys st ¶

Function: sparse-table-values st ¶

{data.sparse}