====== 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.
→ [[lyx_-_programmiersprache:units:mathematik|Mathematik-Units]] · [[lyx_-_programmiersprache:units:dist|std.dist]] · [[lyx_-_programmiersprache:units:linalg|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.
----
===== Darstellung =====
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);
**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.
----
===== Rechnen =====
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.
^ Gruppe ^ Funktionen ^
| Prüfen und Aufräumen | ''SparseIsSorted'' · ''SparseSort'' · ''SparsePrune'' |
| Umwandeln | ''SparseFromDense'' · ''SparseToDense'' |
| Einzelzugriff | ''SparseGet'' |
| Normen | ''SparseNorm'' · ''SparseNormSq'' · ''SparseNormL1'' · ''SparseNormInf'' · ''SparseNormalize'' · ''SparseScale'' |
| Ähnlichkeit | ''SparseDot'' · ''SparseCosine'' · ''SparseCosineDist'' · ''SparseAngular'' |
| Mengenmaße | ''SparseOverlap'' · ''SparseJaccard'' |
| Abstände | ''SparseEuclid'' · ''SparseManhattan'' |
| Verknüpfen | ''SparseAdd'' · ''SparseSub'' · ''SparseAxpy'' · ''SparseHadamard'' |
| Suchen | ''SparseNearest'' · ''SparseTopK'' |
''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.
----
===== Ähnlichkeitssuche =====
Beide Suchfunktionen erwarten die Sammlung als **drei parallele Felder** — Indizes, Werte und die Längen je Eintrag — plus die Anzahl:
^ Funktion ^ Liefert ^
| ''SparseNearest(qi, qv, qn, cIdx, cVal, cNnz, count, outSim)'' | Position des ähnlichsten Eintrags, Ähnlichkeit unter ''outSim'' |
| ''SparseTopK(qi, qv, qn, cIdx, cVal, cNnz, count, k, outPos, outSim)'' | die ''k'' besten, Positionen und Werte in zwei Feldern |
''SparseTopK'' gibt die tatsächlich gefüllte Anzahl zurück — bei weniger als ''k'' Kandidaten ist sie kleiner als ''k''.
> **Kosinus-Ähnlichkeit oder Kosinus-Abstand?** ''SparseCosine'' liefert die **Ähnlichkeit** (1 = gleiche Richtung), ''SparseCosineDist'' den **Abstand** (0 = gleiche Richtung). Die Suchfunktionen arbeiten mit der Ähnlichkeit, sortieren also **absteigend**. Wer sie mit einem Abstandsmaß mischt, bekommt die Reihenfolge verkehrt herum.
>
> ''SparseAngular'' ist die einzige der drei, die eine echte Metrik ist und die Dreiecksungleichung erfüllt — nötig, sobald ein Suchbaum darauf aufsetzt.
----
===== Abgrenzung =====
^ Darstellung ^ Unit ^
| dicht, ''f64'' | [[lyx_-_programmiersprache:units:dist|std.dist]] |
| **dünn, sortierte Paare** | ''std.sparse'' |
| ganzzahlige Gitterkoordinaten | [[lyx_-_programmiersprache:units:grid|std.grid]] |
''Euclid'' und ''Manhattan'' gibt es in allen dreien — das sind drei Implementierungen für drei Darstellungen, keine Doppelung.
> **Das sind Vektoren, keine Matrizen.** Dünnbesetzte **Matrizen** und die zugehörigen iterativen Löser (CG, GMRES) gibt es derzeit in keiner Unit. Für dichte Matrizen ist [[lyx_-_programmiersprache:units:linalg|std.linalg]] zuständig.
----
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.