Divide and conquer - Teile und herrsche - zum Unicode-Codepoint effizient den Unicode-Block finden - per binäre Suche
Wenn man sich - wie ich - vorrangig mit anwendungsnaher Programmierung beschäftigt, dann sollte man sich normalerweise auf die Ressourcen von Programmiersprachen stützen. Und nicht auf die Idee kommen, bestimmte systemnahe Dinge wie Suchen und Sortieren in einer Hochsprache "nachbauen" zu wollen.
Denn in so einem Fall läuft man schnell Gefahr, Dinge sehr ineffizient zu machen.
Aber was ist, wenn sich eine Fragestellung ergibt, bei der die "offenkundige Lösung" auch offenkundig schlecht ist?
So eine Situation gab es jetzt für mich, als ich eine Idee zur Erweiterung meiner Unicode-Unterseite
Online-Tools zu Unicode
https://www.sql-und-xml.de/unicode-database/online-tools/
hatte. Dort kann man - seit 2004 - über ein simples Formular Integer, Hex- und Character-Darstellungen ineinander umrechnen lassen. Das Formular wird auch ganz gut genutzt. Es nutzt ausschließlich clientseitiges JavaScript. Es ist also kein erneutes Laden der Seite notwendig -> die Nutzung geht schnell.
Die Idee: Es wäre doch schön, wenn man zum ersten Zeichen gleich den Unicode-Block angezeigt bekäme.
Hintergrund: Innerhalb des Unicode-Systems sind derzeit ein Teil der Ganzzahlen von 0 - 1114111 zunächst in Blöcken unterteilt. Der erste Block - Basic Latin - geht bsp. von 0 - 127. Jeder Zahl ist nun - umkehrbar eindeutig - ein Zeichen zugeordnet. 0-127 deckt das US-Ascii ab. 128-255 ist der Latin-1 Supplement - Block, da sind bsp. einige europäische Zeichen mit Accent-Zeichen und auch die deutschen Umlaute drin. Später folgen Blöcke für die Buchstaben verschiedener Sprachen, mathematische und technische Symbole usw.
Aktuell liegt Unicode in der Version 10.0 vor. Es gibt 280 Blöcke und einen Bereich von insgesamt 1.114.111 Zeichen. Die Blöcke sind "etwas unübersichtlich". Deshalb die Idee, gleich den Blocknamen auszugeben. Dann kann man nämlich ein Zeichen aus einer Website einfach per Copy & Paste in das Feld "Character" reinkopieren, wählt die Transformation
> char → int, hex, bit
und kann sich die Details zu diesem Zeichen auf der angezeigten Blockseite ausgeben lassen. Die stehen über die Unicode-Datenbank https://www.sql-und-xml.de/unicode-database/ ohnehin zum direkten Anklicken zur Verfügung.
Die aktuell 280 Blocknamen und die zugehörigen unteren und oberen Grenzen liegen vor. Die kann man auch als drei sortierte statische Arrays vordefinieren.
Aber wie findet man nun bsp. am schnellsten heraus, daß der Codepoint 10000 mit dem zugeordneten Zeichen ✐ aus dem Dingbats-Block stammt, der die Codepunkte 9984 - 10175 abdeckt?
Die "offenkundige Lösung" (zum besseren Verständnis teils mit Pseudocode)
--
/* Durchlaufe die Liste aller Einträge */
for (i = 0; i < liste_der_unteren_Grenzen.length; i++) {
/* Prüfe für den aktuellen Eintrag, ob der aktuelle Codepoint zwischen den Grenzen liegt */
if (liste_der_unteren_Grenzen[i] <= codepoint
AND codepoint <= liste_der_oberen_Grenzen[i]) {
console.log("Hurra - passt");
stringBlockname = liste_der_Blocknamen[i];
exit for; /*Abbruch*/
}
}
--
ist offenkundig ineffizient: Denn damit sind bis zu 280 Prüfungen notwendig.
Innerhalb von JavaScript gibt es zwar auch noch eine Methode Array.find, die eine beliebige Funktion für jedes Arrayelement ausführt und das erste positive Ergebnis zurückgibt. Aber auch diese läuft über alle Array-Elemente - und ist damit ebenso ineffizient.
--
Eine mögliche Lösung: Divide and conquer = Teile und herrsche. Es wird versucht, das Problem bei jedem Durchgang zu verkleinern. Bis schließlich nur noch ein Block übrig bleibt, der nun "passt".
Sprich: Man hat zwei Grenzen: Die untere Grenze ist zunächst 0, die obere (bei 280 Elementen) 279. Einer der Indexwerte zwischen diesen beiden Grenzen ist der Indexwert des gesuchten Blocks. Da man die Grenzen der Größe nach vorsortieren kann, kann man den ersten Test frei wählen. Also wählt man die Mitte - 139 oder 140 als aktuelle Position. Und prüft:
> codepoint < liste_der_unteren_Grenzen[position = 140]
Ist diese Bedingung erfüllt, dann weiß man,daß man alle Positionen >= 140 bereits ignorieren kann. Die gesuchte Position kann also maximal 139 sein. Ist die Bedingung nicht erfüllt, dann weiß man, daß der Codepoint mindestens zum Block mit der Position 140 gehört. In dem Fall kann man alle Positionen < 140 ignorieren.
In beiden Fällen hat sich also die Aufgabenstellung halbiert: Man muß nicht mehr gegen 280 Grenzen testen. Sondern nur noch gegen die Hälfte der Positionen.
Damit kann man im ersten Fall die obere Grenze auf 139 verringern. Im zweiten Fall setzt man die untere Grenze auf 140 hoch. Anschließend wird der neue Mittelpunkt zwischen den beiden neuen Grenzen berechnet und mit diesem die Prüfung wiederholt.
In beiden Fällen hat sich die Länge des Prüfintervalls halbiert. Das ist damit sehr effizient. Das macht man solange, bis untere und obere Grenze zusammenfallen.
Dann weiß man, daß man nun den Block gefunden hat. Eventuell muß man dann noch prüfen, ob der gesuchte Codepoint tatsächlich zu diesem Block gehört, also kleinergleich der oberen Grenze ist. Oder ob der Codepoint zu einem derzeit nicht belegten Bereich gehört. So gehört der Codepoint 2200 weder zum Block "Syriac Supplement" (geht bis 2159) noch zum nächsten Block Arabic Extended-A (beginnt bei 2208).
Folglich benötigt ein solcher Algorithmus bei 280 Blöcken immer maximal 9 Prüfungen (2^9 = 512, 2^8 = 256 reicht nicht), um die korrekte untere Grenze zu finden. Es gibt zwar keine "ganz schnelle" Lösung, die nur mit ein oder zwei Prüfungen auskommen würde. Das wäre der Fall, wenn man immer beim Index 0 anfängt und die meisten Überprüfungen sehr niedrige Codepoints betreffen würden.
Aber dafür gibt es auch keinen Fall, in dem 200 oder gar 280 Prüfungen notwendig wären. Und selbst wenn sich die Zahl der Blöcke verdoppeln würde, wäre nur eine Prüfung mehr notwendig. Die erste Prüfung würde aus nun 560 Blocken wieder 280 Blöcke machen, ab dann ginge das wie bisher weiter.
Fazit: Ein Algorithmus, der bei einem Durchlauf das Problem quasi halbiert, der ist immer gut. Das kann man auch in Hochsprachen effizient machen.
Das wurde inzwischen auf der Online-Tools - Seite eingebaut. Die drei Arrays mit den Blocknamen, den Start- und den Endwerten sind vordefiniert in der JavaScript-Datei abgelegt.
--
Praktisch ist das eine Umsetzung der binären Suche
https://de.wikipedia.org/wiki/Bin%C3%A4re_Suche
Diese ist selbst ein Spezialfalls des Prinzips "Teile und herrsche".