std.sparse — dünnbesetzte Vektoren

Vektoren, die fast überall null sind, als sortierte Index/Wert-Paare: Skalarprodukt und Kosinus im Gleichlauf über beide Listen, Normen, Mengenmaße und Ähnlichkeitssuche mit Top-k.

→ Mathematik-Units · std.dist · std.linalg

import std.sparse;

Schicht 0, hängt an std.math und std.alloc. 26 Funktionen. Alle Beispiele mit lyxc 1.0.21A übersetzt und ausgeführt.

Ein dünnbesetzter Vektor sind zwei Felder gleicher Länge: die Indizes (int64, aufsteigend sortiert) und die zugehörigen Werte (f64). Die Länge ist nnz — die Zahl der Einträge ungleich null. Die Dimension selbst wird nirgends geführt.

// a = {0: 1, 5: 2, 9: 3}
var ia: int64 := alloc(3 * 8);
var va: int64 := alloc(3 * 8);
poke64(ia,      0);  pokef64(va,      1.0);
poke64(ia + 8,  5);  pokef64(va + 8,  2.0);
poke64(ia + 16, 9);  pokef64(va + 16, 3.0);

<WRAP alert> Die Sortierung ist Voraussetzung, nicht Zusage. Sämtliche Verknüpfungen zweier Vektoren laufen als Gleichlauf über beide Indexlisten — zwei Zeiger, die gemeinsam vorrücken. Das ist der Grund, warum SparseDot bei 100 000 Dimensionen und je 20 Einträgen 40 Schritte braucht statt 100 000. Unsortierte Eingaben liefern stillschweigend falsche Ergebnisse, keinen Fehler.

SparseIsSorted(idx, nnz) prüft, SparseSort(idx, val, nnz) stellt her. </WRAP>

unit main;
import std.io;
import std.string;
import std.alloc;
import std.sparse;

fn ZF(t: pchar, v: f64): void { Print(t); PrintF64(v); }
fn ZI(t: pchar, v: int64): void { Print(t); PrintLn(IntToStr(v)); }

fn main(): int64 {
    // a = {0:1, 5:2, 9:3}   b = {5:4, 9:1, 12:7}
    var ia: int64 := alloc(3 * 8); var va: int64 := alloc(3 * 8);
    poke64(ia, 0);       pokef64(va, 1.0);
    poke64(ia + 8, 5);   pokef64(va + 8, 2.0);
    poke64(ia + 16, 9);  pokef64(va + 16, 3.0);

    var ib: int64 := alloc(3 * 8); var vb: int64 := alloc(3 * 8);
    poke64(ib, 5);       pokef64(vb, 4.0);
    poke64(ib + 8, 9);   pokef64(vb + 8, 1.0);
    poke64(ib + 16, 12); pokef64(vb + 16, 7.0);

    ZI("IsSorted(a)  : ", SparseIsSorted(ia, 3) as int64);
    ZF("Get(a, 5)    : ", SparseGet(ia, va, 3, 5));
    ZF("Get(a, 7)    : ", SparseGet(ia, va, 3, 7));
    ZF("Dot(a,b)     : ", SparseDot(ia, va, 3, ib, vb, 3));
    ZI("Overlap(a,b) : ", SparseOverlap(ia, 3, ib, 3));
    ZF("Jaccard(a,b) : ", SparseJaccard(ia, 3, ib, 3));
    ZF("Cosine(a,b)  : ", SparseCosine(ia, va, 3, ib, vb, 3));
    ZF("Norm(a)      : ", SparseNorm(va, 3));
    ZF("NormL1(a)    : ", SparseNormL1(va, 3));
    ZF("Euclid(a,b)  : ", SparseEuclid(ia, va, 3, ib, vb, 3));
    return 0;
}

IsSorted(a)  : 1
Get(a, 5)    : 2.000000
Get(a, 7)    : 0.000000
Dot(a,b)     : 11.000000
Overlap(a,b) : 2
Jaccard(a,b) : 0.500000
Cosine(a,b)  : 0.361873
Norm(a)      : 3.741657
NormL1(a)    : 6.000000
Euclid(a,b)  : 7.615773

Sämtliche Werte stimmen mit der Referenzrechnung überein. Dot ist 2·4 + 3·1 = 11 — nur die gemeinsamen Indizes 5 und 9 tragen bei. SparseGet auf einen nicht vorhandenen Index liefert 0.0, wie es sein muss.

SparsePrune(idx, val, nnz, eps) wirft Einträge unterhalb einer Schranke weg und gibt die neue Länge zurück — nach Additionen sammeln sich sonst Werte an, die praktisch null sind, aber weiter Platz und Rechenzeit kosten.

SparseFromDense(dense, n, eps, …) baut aus einem dichten Feld die dünne Form; eps entscheidet, was als null gilt.

Beide Suchfunktionen erwarten die Sammlung als drei parallele Felder — Indizes, Werte und die Längen je Eintrag — plus die Anzahl:

SparseTopK gibt die tatsächlich gefüllte Anzahl zurück — bei weniger als k Kandidaten ist sie kleiner als k.

Euclid und Manhattan gibt es in allen dreien — das sind drei Implementierungen für drei Darstellungen, keine Doppelung.

Letzte Aktualisierung: 2026-08-16 · alle Beispiele mit lyxc 1.0.21A übersetzt und ausgeführt; Skalarprodukt, Kosinus, Jaccard und Abstände gegen eine unabhängige Referenzrechnung geprüft.