====== std.dist — Abstandsmaße ======

Abstände zwischen dichten ''f64''-Vektoren: Euklid, Manhattan, Chebyshev, Minkowski, Kosinus, Hamming, Jaccard — durchgehend über einen überlaufsicheren ''hypot''.

→ [[lyx_-_programmiersprache:units:mathematik|Mathematik-Units]] · [[lyx_-_programmiersprache:units:sparse|std.sparse]] · [[lyx_-_programmiersprache:units:grid|std.grid]] · [[lyx_-_programmiersprache:units:sum|std.sum]]

<code lyx>
import std.dist;
</code>

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

----

===== Darstellung =====

Ein Vektor ist ein Speicherblock aus ''nd'' ''f64''-Werten — ''alloc(nd * 8)'', beschrieben mit ''pokef64''. Eine Punktmenge ist dasselbe hintereinander: ''count'' Punkte zu je ''nd'' Werten.

<box tip>
> **Drei Units bringen ''Euclid'' und ''Manhattan'' mit — das ist Absicht.** ''std.dist'' rechnet auf **dichten** ''f64''-Vektoren, [[lyx_-_programmiersprache:units:sparse|std.sparse]] auf **dünnbesetzten** (sortierte Index/Wert-Paare), [[lyx_-_programmiersprache:units:grid|std.grid]] auf **ganzzahligen** Gitterkoordinaten. Drei Darstellungen, drei Implementierungen — wer den falschen Nachbarn wählt, zahlt mit Speicher oder Genauigkeit.
</box>

----

===== Die Maße =====

<code lyx>
unit main;
import std.io;
import std.string;
import std.alloc;
import std.dist;

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

fn main(): int64 {
    var nd: int64 := 3;
    var a: int64 := alloc(nd * 8);
    var b: int64 := alloc(nd * 8);
    pokef64(a, 0.0); pokef64(a + 8, 3.0); pokef64(a + 16, 4.0);
    pokef64(b, 0.0); pokef64(b + 8, 0.0); pokef64(b + 16, 0.0);

    ZF("Euclid(a,0)    : ", DistEuclid(a, b, nd));
    ZF("Manhattan(a,0) : ", DistManhattan(a, b, nd));
    ZF("Chebyshev(a,0) : ", DistChebyshev(a, b, nd));
    ZF("Minkowski p=3  : ", DistMinkowski(a, b, nd, 3.0));
    ZF("Norm(a)        : ", DistNorm(a, nd));
    return 0;
}
</code>

<code>
Euclid(a,0)    : 5.000000
Manhattan(a,0) : 7.000000
Chebyshev(a,0) : 4.000000
Minkowski p=3  : 4.497941
Norm(a)        : 5.000000
</code>

Für ''(0, 3, 4)'': Euklid 5, Manhattan 3+4 = 7, Chebyshev max(3,4) = 4. ''Minkowski'' mit ''p'' verbindet die drei — ''p=1'' ist Manhattan, ''p=2'' ist Euklid, große ''p'' nähern sich Chebyshev.

^ Funktion ^ Maß ^
| ''DistEuclid'' / ''DistEuclidSq'' | euklidisch, mit und ohne Wurzel |
| ''DistManhattan'' | Summe der Beträge |
| ''DistChebyshev'' | größte Einzelabweichung |
| ''DistMinkowski(a, b, nd, p)'' | verallgemeinert, ''p'' frei |
| ''DistNorm'' / ''DistNormSq'' | Länge eines einzelnen Vektors |
| ''DistHamming'' | Anzahl abweichender Stellen |
| ''DistHammingBits'' | dasselbe auf Bitmustern |
| ''DistJaccard'' | Mengenähnlichkeit |

''DistEuclidSq'' spart die Wurzel — für **Vergleiche** genügt das quadrierte Maß, und die Reihenfolge bleibt dieselbe.

----

===== Überlaufsicherheit: der eigentliche Punkt =====

Die naheliegende Formel ''√(x² + y²)'' überläuft, lange bevor das Ergebnis es täte. ''std.dist'' rechnet durchgehend über ''DistHypot'':

<code lyx>
unit main;
import std.io;
import std.string;
import std.feq;
import std.dist;

fn main(): int64 {
    var h: f64 := DistHypot(1.0e200, 1.0e200);
    Print("Bits(hypot(1e200,1e200)) = "); PrintLn(IntToStr(FeqBits(h)));
    Print("hypot ist endlich        : "); PrintLn(IntToStr(FeqIsFinite(h) as int64));

    var big: f64 := 1.0e200;
    var naive: f64 := big * big + big * big;
    Print("Bits(naiv x*x + y*y)     = "); PrintLn(IntToStr(FeqBits(naive)));
    Print("naiv ist unendlich       : "); PrintLn(IntToStr(FeqIsInf(naive) as int64));

    var q: f64 := h / 1.0e200;
    Print("hypot / 1e200            = "); PrintF64(q);
    return 0;
}
</code>

<code>
Bits(hypot(1e200,1e200)) = 7601389629357644631
hypot ist endlich        : 1
Bits(naiv x*x + y*y)     = 9218868437227405312
naiv ist unendlich       : 1
hypot / 1e200            = 1.414213
</code>

**''DistHypot'' liefert ein endliches Ergebnis, die naive Formel ''inf''.** Das Bitmuster ''7601389629357644631'' entspricht ''1,4142135623730951e200'' — bitgleich mit der Referenzrechnung. ''9218868437227405312'' ist das Bitmuster von ''+inf''.

<WRAP alert>
**''PrintF64'' zeigt für dieses Ergebnis ''overflow''.** Das ist eine Grenze der **Ausgabe**, nicht der Rechnung — ab etwa 1e19 kann ''PrintF64'' den Wert nicht mehr darstellen. Wer große Zwischenergebnisse prüft, gibt das Bitmuster über ''FeqBits'' aus oder teilt vorher herunter (oben ''h / 1e200''). Andernfalls sieht eine korrekte Rechnung wie ein Fehler aus.
</WRAP>

''DistHypot3(x, y, z)'' macht dasselbe für drei Achsen.

----

===== Kosinus: Ähnlichkeit oder Abstand =====

<code lyx>
ZF("CosineSimilarity(x, 2x) : ", DistCosineSimilarity(c, d, nd));
ZF("Cosine(x, 2x)           : ", DistCosine(c, d, nd));
</code>

<code>
CosineSimilarity(x,2x) : 1.000000
Cosine(x,2x)           : 0.000000
</code>

Für zwei Vektoren, die in dieselbe Richtung zeigen und sich nur in der Länge unterscheiden: **Ähnlichkeit 1, Abstand 0.**

^ Funktion ^ Wertebereich ^ Bedeutung ^
| ''DistCosineSimilarity'' | −1 … 1 | 1 = gleiche Richtung |
| ''DistCosine'' | 0 … 2 | ''1 − Ähnlichkeit'' |
| ''DistAngular'' | 0 … π | der Winkel selbst |

Die Verwechslung der ersten beiden ist der häufigste Fehler bei Ähnlichkeitssuchen: wer nach dem **kleinsten** Wert sortiert, will ''DistCosine''; wer nach dem **größten** sortiert, ''DistCosineSimilarity''. ''DistAngular'' ist im Gegensatz zu beiden eine echte Metrik und erfüllt die Dreiecksungleichung — nötig, sobald ein Suchbaum darauf aufsetzt.

----

===== Über Punktmengen =====

^ Funktion ^ Zweck ^
| ''DistNearest(point, set, count, nd, …)'' | nächster Punkt der Menge |
| ''DistFarthest(point, set, count, nd, …)'' | entferntester |
| ''DistMatrix(set, count, nd, out)'' | alle paarweisen Abstände |
| ''DistCentroid(set, count, nd, out)'' | Schwerpunkt |
| ''DistWithin(a, b, nd, radius)'' | liegt ''b'' im Radius um ''a''? |

''DistMatrix'' schreibt ''count × count'' Werte — der Zielpuffer muss entsprechend groß sein. Bei 10 000 Punkten sind das 800 MB; für große Mengen ist ''DistNearest'' der richtige Weg.

''DistWithin'' vergleicht ohne Wurzelziehen und ist damit billiger als ''DistEuclid(…) <= radius''.

----

Letzte Aktualisierung: 2026-08-16 · alle Beispiele mit ''lyxc 1.0.21A'' übersetzt und ausgeführt; die Überlaufsicherheit von ''DistHypot'' bitgenau gegen eine unabhängige Referenzrechnung geprüft.