Søren in Norwegen

Eines der voll tollsten Weihnachtsgeschenke ever:

Foto nicht von mir aber mit Erlaubnis hier wiedergegeben.

Urst voll geil wa! Ein Original (!!!) der Philosophiæ Naturalis Principia Mathematica!
Es war aber die zweite, erweiterte Ausgabe. Habe ich sofort daran erkannt, weil darin auch Leibniz Darstellung der Infinitesimalrechnung aufgenommen war.

Freitags versuche ich immer ein Flash T-Shirt anzuziehen. Aus Prinzip und weil’s mein Lieblingssuperheld ist.
Dies im Speziellen hat nur aeuszerst periphaer mit dem Thema dieses Artikels zu tun: „Das dauert mir zu lange! Das muss doch schneller gehen!“ … Aber i.A. passt das schon … … … wobei „aueszerst peripher“ sinnlos ist, denn die Peripherie ist ja schon der aeuszere Rand einer Zone.

Ein ganz anderer Anfang: heute plaudere ich mal etwas aus dem Naehkaestchen und versuche mehrere Wochen des freudigen Programmierens und Problemløsens in nur diesen einen Beitrag zu packen, ohne all zu technisch zu werden.

Die neulich beschriebene Idee, das Kevin-Bacon-Problem in Vektoren zu fassen, ist streng genommen nicht nøtig um das Linknetzwerk zu durchschreiten. Es reicht vøllig, dass das alles in den Speicher passt und dann kann man (wie im verlinkten Artikel gesagt) mittels Fallunterscheidungen schon ’ne ganze Menge machen.

Nachdem ich die Titel zu Zahlen transformiert hatte, habe ich einen derartigen Algorithmus mal schnell implementiert um zu sehen, wie lange der denn braucht … und der brauchte so ca. 53 Jahre!

Wait! What!? Wenn ich mich richtig erinnere, dann hatte der Code noch nicht mal alle Analyseteile, welche noch mehr Zeit benøtigt haetten.
Dies war natuerlich zu viel und ich musste eine (mathematische) Løsung finden, welche dann hoffentlich nicht so viel Zeit braucht. Das ist das, was ich beim letzten Mal beschrieb.
Dieser „Vektorcode“, brauchte in Python 3.7.3 ca. vier Minuten um das Linknetzwerk einer Seite zu analysieren. Das war zwar besser, aber fuer alle ca. 6 Millionen Seiten waeren das immer noch 45 Jahre, die mein Rechner durchgehend haette laufen muessen. … Verdammt!

Da daemmerte mir, dass ich wohl nicht umhin komme, dass ganze in C zu schreiben.
Davor versuche ich mich immer zu druecken. Der Grund ist (wie an anderer Stelle bereits (indirekt) erwaehnt), dass ich mich da um grundlegende Sachen wie Speicherverwaltung selber kuemmern muss. Und wenn da was schief geht, dann bekomme ich das mitunter gar nicht mit, weil ich keine Ahnung von C habe.

Hinzu kam, dass die aeuszerste Ordnungsstruktur, das Lexikon (das „Dictionary“ oder die „Lokomotive“ (wie ich es an anderer Stelle nenne), welche die vielen „Waggons“ mit den ganzen Links „zieht“) in der Form gar nicht existiert in C. Zumindest nicht in der einfach zu verstehenden, einfach zu handhabenden und vielseitig anwendbaren Form wie in Python.
Und das ist ein riesiges Problem, denn auf jedem Linklevel, muss ich in besagtem Lexikon tausend-, millionen-, ja fast zweihundertmillionenmal nachschauen welcher Titel welche Links (die „Ausgaenge“ zum naechsten Linklevel) hat. Und das ganze dann noch mal ca. 6 Millionen Titel.
Deswegen muss so ein Lexikon effizient und gut in the gesamte Sprache integriert sein. Ich meine tatsaechlich die Programmiersprache an sich (und Dictionaries sind extrem gut in Python integriert), denn hierbei wird verdammt gute Speicherverwaltung benøtigt!

Zum Glueck hatte ich schonmal was von Hashtabellen gehørt. Hashtabellen sind sowas wie ein Lexikon — ein „Ausgangswert“ (hier die Titel) wird irgendwas zugeordnet. Dabei kann es aber zu sogenannten Kollisionen kommen. Das waren dann bei ein und demselben Ausgangswert mehrere Zuordnungen. Beim Lexikon nehme man das Wort „Wurzel“. Das kønnte die Wurzel einer Pflanze sein oder die Wurzel einer Zahl.
Hashtabellen løsen dieses Problem (muessen sie ja, denn ansonsten wuerden sie nicht benutzt werden) aber Kollisionsvermeidung fuehrt dazu, dass der Zugriff in Hashtabellen unter Umstaenden sehr langsam sein kann. Das ist ein riesiges Problem denn, wie bereits erwaehnt, muss ich urst oft in dieser Hashtabelle nachschlagen.
Vor allen Dingen ist die zeitraubende Kollisionsvermeidung ein unnøtiger Prozess in meinem Fall, weil ich nach der „Verzahlung“ eindeutige „Ausgangswerte“ habe und es niemals zu Kollisionen kommen kann.

Dazu kam, dass es auch solche Hashtabellen nicht „fertig aus der Tuete“ in C gibt und ich das selber programmieren musste.
Aber die 45 Jahre Laufzeit waren mir zu viel. Und deswegen machte ich mich auf, mir das Ganze mal anzuschauen. Zunaechst etwas zøgerlich, ja gar etwas aengstlich, aber dann immer enthusiastischer. Ich fand ein paar extrem gute Erklaerungen im Netz und die dortigen Løsungen schaffte ich fuer mein Problem zu modifizieren. Das war spannend!

Dann implementierte ich den beim letzten Mal vorgestellten Vektoralgorithmus und das ging ganz toll. Anstatt ca. 4 Minuten pro Titel brauchte ich nur noch 3.2 Sekunden (! … !!! … !!!einseinself) pro Titel … wait! WHAT?! … Anstatt 45 Jahre wuerde ich fuer alle ca. 6 Millionen Titel dann nur noch ca. 7 Monate brauchen!

JIPPIE!!!!! Damit wurde das Projekt ganz konkret durchfuehrbar.

Nun war besagte Zeit aber immer noch ohne die eigentliche Analyse.
Doch dann erinnerte ich mich, dass Computer heutzutage ja Mehrkernprozessoren haben, von denen meistens nur einer ausgelastet ist und der Rest Pause macht. Und die Macht dieser restlichen Kerne wollte ich auch nutzen. Das Ganze kønnte man auf deutsch „simultaner Mehrfadenbetrieb“ nennen, aber ich denke nicht, dass das irgendwer sagt. Deswegen benutze ich den englischen Begriff multithreading.
Wusste ich wie das zu programmieren ist? Die Antwort ist ein klares „Nein“. Aber das war super interessant und zunaechst etwas zøgerlich, ja gar etwas aengstlich, aber dann immer enthusiastischer machte ich mich daran die technische Seite des multithreading besser zu verstehen und zu implementieren.

Das hørt sich jetzt komplizierter an als es ist. Beim multithreading ist es eigentlich nur so, dass der Computer auf Kern #1 das Linknetzwerk von Titel 516 (als Beispiel) durchsucht, auf Kern #2 das von Titel 517, auf Kern #3 das von Titel 518 usw.
Dabei muss man im Wesentlichen darauf achten, dass bestimmte Ressourcen von allen „Threads“ benutzt werden. Beim Lesen ist das nicht so tragisch, da kann der Thread auf Kern #2 warten bis der Thread auf Kern #1 fertig ist. Beim Schreiben ist das aber von ganz erheblicher Bedeutung. Klar, wird da auch gewartet, aber der thread auf Kern #2 kønnte Information ueberschreiben, die der Thread auf Kern #1 (oder Kern #3 usw.) noch braucht.
Das wird oft dadurch geløst, dass man schaut welche Ressource gerade von welchem Thread „in Benutzung“ ist und die darf dann von keinem anderen Thread „angefasst“ werden. Das ist aber URST krass zeitraubend, weil dann ja wieder alle Prozessoren Pause machen bis die Ressource frei ist. Deswegen musste ich die Teile des Vektoralgorithmus welche von allen Threads benutzt werden auf andere weise „threadsicher“ machen. Die Løsung war, dass jeder Thread seine eigenen Vektoren bekommt und dann war es technisch nur noch eine kleine Herausforderung, dass die Zuteilung der Vektoren zu den richtigen Threads automatisch geschieht (weil das ja ca. 6 Millionen mal gemacht werden muss).

Lange Rede kurzer Sinn, nach der Hashtabelle implementierte ich dann das multithreading.
Nun ist es aber so, dass multithreading extra „Betriebskosten“ (diesmal nicht in Form von Speicher aber in Form von Prozessorzyklen und damit „Rechenzeit“) verursacht. Threadsicherheit ist der Teil der Kosten ueber den ich Kontrolle hatte. Das allermeiste geschieht intern und ich habe absolut keine Ahnung, was das alles ist.
Jedenfalls fuehrt das dazu, dass man die Zeit mit zwei Kernen nicht einfach nur halbieren kann. Aber bei 2 Kernen brauchte ich nur noch 2.8 Sekunden pro Titel. Und mit drei Kernen gar nur 2.2 Sekunden pro Titel. Die Benutzung von 4 Kernen bringt keine weitere Verbesserung, machte meinen Rechner aber urst traege. Das lag natuerlich daran, dass ich nur 4 Kerne habe und auf einem muss ja auch das Betriebssystem laufen.
Drei Theads, und ca. 5 Monate Rechenzeit, sollen es also sein.

Danach „stolperte“ ich ueber eine Kuriositaet, die ich mir nicht erklaeren kann. Dafuer muss ich aber etwas ausholen.

Die Werte der einzelnen Elemente in den Vektoren sind ja nur Null und Eins, nix anderes. Aber soweit habe ich den Algorithmus derart implementiert, dass ich diese als eben das — richtige Zahlen — ansehe, die auch den Wert 23517 annehmen kønnten. Damit folgen die mehrere Bytes Speicherbedarf „richtiger“ Zahlen. Weil es aber nur Nullen und Einsen sind, kønnte der Datentyp (und damit die „Betriebskosten“) dieser Werte auch anders sein.

Also spielte ich mal mit ein paar anderen Datentypen herum und es stellte sich dann heraus, dass ich mit der Verwendung des Datentyps char die Rechenzeit auf nur 1.5 Sekunden pro Titel reduzieren konnte. Das entspricht ein bisschen weniger als ca. 3 1/2 Monate fuer die komplette Wikipedia.
Der Nachteil von char ist, dass da dann halt nur kleine Zahlen rein passen, die nicht mehr als dieses eine Byte brauchen. Zum Glueck sind Null und Eins so klein, dass es kleiner nicht geht.

Superduper … doch dann ging mir auf, dass ich die Analyse der Linklevel ja noch gar nicht implementiert hatte. Das ging aber schnell reinzuhacken und die benøtigte Zeit erhøhte sich (bei der Verwendung von char und drei Threads) um nur 0.15 Sekunden pro Titel. Selbst bei fast 6 Millionen Titeln verlaengerte sich damit die erwartete Gesamtrechenzeit auf nur etwas mehr als ca. 3 1/2 Monate.

Lange Rede kurzer Sinn: nach einigen Wochen hatte ich es nicht nur geschafft die technische Løsung des Kevin-Bacon-Problems ganz konkret in Code zu fassen, sondern ich konnte durch gezielte „Tricks und Kniffe“ die Gesamtrechenzeit von urspruenglich ca. 50 Jahren auf nur 3 1/2 Monate reduzieren.

Da fuehlte ich mich ungefaehr so:

URST! KRASS! … WIE TOLL DOCH ICH BIN! … wa! … Es gibt nichts was ich nicht kann … ICH … BIN … GOTT!

Und deswegen wollte ich das hier mal (trotz der Laenge) wenigstens in der kuerzest møglichen Form mit so wenigen (konkret) technischen Ausfuehrungen wie møglich, hingeschrieben haben.

Dreieinhalbe Monate also. Sagen wir vier, vielleicht fuenf, denn es kønnte ja mittendrin was schief gehen und dann muss ich Teile nochmal machen.

… … … aber Moment … im Buero stehen doch zwei Rechner rum, die sonst nix zu tun haben … … …

… … … hmmmmmmmm … … …

… … … hmmmm hmmmm hmmmm … … …

… … … ca. 7 Wochen spaeter … … …

Die Ergebnisse sind hier!

Aber dazu mehr ab dem naechsten Mal.

Dies …

… ist der vorletzte Schuber in dieser Reihe. Und wenn ich ehrlich bin …

… dann freute ich mich beim Lesen darauf, dass ich bald fertig mit allem war. Die Gruende dafuer …

… legte ich mehr oder weniger detailliert in den letzten Beitraegen bereits dar. Und so kurz vor Schluss ist mir dann nochmal aufgefallen, …

… dass popkulturell sehr bekannte Figuren eigentlich eher spaerlich auftreten. Zwei Beispiele waren Pig-Pen (Schulz mochte nicht, dass diese Figur auf ihr Aeuszeres reduziert wurde und hat ihn deswegen sehr spaerlich eingesetzt) und Rerun (den ich sehr mag; wobei dieser ganz zum Schluss noch eine sehr wichtige Rolle spielen wird) und andere).

Das hat sicherlich damit zu tun, dass die TV-Serien (wo diese Charaktere mglw. grøszere Rollen haben) von viel mehr Menschen geschaut (und erinnert) wurden. Aber letztlich das ist ja dann eigentlich wieder genau das, was ich im allerersten Artikel dieser Reihe ansprach: der kulturelle Einfluss, den die Peanuts hatten und weiterhin haben … und weswegen ich alle Comicstrips haben wollte.

Die Drake-Gleichung …

… wird genommen um N,

[…] the number of civilizations in our galaxy with which communication might be possible […]

zu berechnen, als Produkt aus (alle Parameter sind anzusehen als Durchschnittswerte):
– der Rate der Sternenentstehung in unserer Galaxis, R_*;
– dem Anteil der Sterne die Planeten haben, f_p;
– der Anzahl der Planeten in der habitablen Zone, n_e („e“ fuer „Erde“);
– der Anteil der Planeten mit Leben, f_l,
– der Anteil der Planeten mit intelligentem Leben, f_i;
– der Anteil der Zivilisationen mit (der Faehigkeit zu bzw. Interesse an) interstellarer Kommunikation, f_c; und
– der Lebensdauer einer solchen Zivilisation, L.

Abhaengig von den Werten der Variablen kønnen da Werte von N bei rauskommen, die sich ueber hundert (!) Grøszenordnungen (!!!) unterscheiden. Das wird dann ab und zu auch kritisert, aber dafuer kann die Gleichung nix. Die ist nie dafuer gedacht gewesen um etwas exakt zu berechnen sondern zur Diskussion.
Einige der Werte kennen wir (mittlerweile) ziemlich genau (alle die mit Astronomie zu tun haben). Ueber andere wiederum wissen wir (fast) ueberhaupt nichts (alle die mit Biologie und Soziologie zu tun haben).

Im Laufe der Jahre hat die Mehrzahl der Leute, die sich darueber Gedanken gemacht haben, relativ hohe Werte fuer N ausgerechnet. Das bedeutet, dass es nach deren Berechnungen ziemlich viele Aliens um uns herum geben muesste. Und das ist das Fermi Paradoxon: wenn es so viele Aliens gibt, warum sehen wir von denen nix?

Deswegen wird spekuliert, was denn der grosze Filter sein kønnte, der diese Kommunikation von uns weg haelt?
Dadurch, dass wir (wie erwaehnt) mittlerweile ziemlich gut die astronomischen Parameter kennen, kønnten das nur noch die biologischen (also die Entstehung von Leben oder der „Aufstieg“ zur Intelligenz) oder soziologischen (Faehigkeit und Interesse an Kommunikation bzw. Lebensdauer einer Zivilisation) sein.

Sehr oft kann man das dazu zusammenfassen, dass das ja alles grundlegende physikalisch/biologische Konzepte sind, die ueberall im Universum gleich sind. Und selbst wenn wir da keine direkten Messwerte haben, kønnen wir ja von dem einen Messwert (die Erde/Menschheit) extrapolieren.
Auf dieser Basis argumentiert Whitmire, D. P. im International Journal of Astrobiology , 18 (2), 2019, pp. 183 – 188 in seinem Artikel mit dem Titel „Implication of our technological species being first and early„:

We argue […] that the Principle of Mediocrity implies that we are typical in technological age […].

Und das ist eine angebrachte, wohlerprobte und nicht zu beanstandende wissenschaftliche Herangehensweise — wir nehmen an, dass wir (und alles um uns herum) voll durchschnittlich sind. Mit Hilfe logischer und statistischer Argumente kommt Whitmire dann zum logischen Schluss:

[…] that the typical technological species has a short lifetime and that their extinction coincides with the extinction of their planetary biosphere.

Wie gesagt, das hier ist der Teil in dem alle sterben.

Eine Modifikation waere die sogenannte Dark Forest Theorie. Im Wesentlichen besagt diese, dass um uns herum keiner „Hallo“ ruft, weil das ja wer høren kønnte, der diese Wesen dann ausløscht, bzw. dass Logik diktiert, dass wenn wir einen Nachbarn høren der „Hallo“ sagt, wir den sofort umbringen muessen (was dann der Zirkel zum ersten Teil des Satzes ist), wenn wir als Zivilisation langfristig ueberleben wollen.
Dies ist natuerlich eine sehr anthropomorphe Sichtweise, aber Logik gilt doch ueberall im Universum.

Lange Rede kurzer Sinn: das Paradoxon løst sich auf, wenn man annimmt, dass alle intelligenten Zivilisationen schnell sterben und niemals die Sterne erreichen … Das ist schon ein bisschen deprimierend muss ich sagen.

Aber wie immer: (more) Science to the Rescue … beim naechsten Mal.

Nix Besonderes ist geschehen seit dem letzten Mal.

Auszderem habe ich den Eindruck, dass bei mir so ein bisschen Space Fatigue einsetzt. Mhmmmm … ich denke mal drueber nach, ob ich nicht erstmal eine nette, bewohnte Welt ansteuere und dort eine laengere Zeit Pause mache. Ich habe genuegend Credits auf meinem Konto und anstatt immerzu neue Sonnen zu sehen, kønnte ich mir ja mal ein paar Monate lang nur eine einzige Sonne auf den Bauch scheinen lassen.

Wieauchimmer, dafuer muesste ich erstmal wieder zurueck in bewohntes Gebiet. Bewohntes Gebiet ist aber recht weit entfernt z.Z.

Ebenso liegt dieses System …

… schon wieder ein Stueckchen hinter mir, in welchem ich 4 Wasserwelten vorfand. Nix super Spektakulaeres, aber durchaus schon etwas, was nicht so haeufig vorkommt.

Die Mensch-Computer-Schnittstellen werden immer besser. Lochkarten waren eine massive Verbesserung gegenueber dem Umstecken von Kabeln. Wobei natuerlich cool ist, dass der Beruf des Programmierers damals als inhaerent weiblich angesehen war. Interessant, wie sich die Zeiten aendern. Aber ich schweife ab.

Noch besser waren dann Tastaturen und heutzutage geben die User ihren Taschencomputern oft viel mehr Liebe als anderen Menschen, denn Erstere werden ja permanent gestreichelt, und Letztere nicht so oft.
In Star Trek reden alle nur noch mit Computern, so wunderschøn ausgedrueckt in dieser klassischen Szene, und dort bewegen wir uns mit schnellen Schritten hin (ab 1:18 geht die Demonstration los).

Aber trotz ausgeklugelter Technik wie Spracherkennung, so wird die Interaktion mit Computern doch im Allgemeinen als emotionslos dargestellt und angenommen. Zum Einen, weil Computer „Gefuehle nicht kønnen“, aber zum anderen auch, weil man die Maschinen nicht mit ambivalenten Dingen verwirren møchte … hier frage ich mich, warum wir das aber unseren Mitmenschen zutrauen?

Wieauchimmer, ganz gut zusammen fasst dieser Artikel ein paar der ueblichen (und wichtigen) Punkte bezueglich der „Computer kønnen kein Mitgefuehl (und werden das auch niemals kønnen)“.

Das ist ein extrem wichtiges Thema, denn so ziemlich alle (!) Berufe haengen daran. Nicht nur Lehrer und Krankenschwestern (und -brueder), sondern natuerlich auch die Polizei und auch der Chef auf dem Bau! Das ist immer und ueberall so praesent und krass wichtig, dass wir uns (als Individuen) ueber schlechte Chefs aufregen, bzw. (als Gesellschaft) diese fundamentale Faehigkeit zur Empathie einer ganz spezifischen Berufsgruppe versuchen abzuerziehen. Letzteres damit Soldaten ungestørt ihrer „Arbeit“ nachgehen kønnen; und in den allermeisten Faellen klappt das (zum Glueck) nicht.

Aber da wird natuerlich dran geforscht und es gibt gute Ideen (nur ein Beispiel) wie man an die Sache heran gehen kann. Solche Ideen gehen von dem aus, was wir ueber die Entwicklung kleiner Kinder wissen und legen dar, wie dieses „Geruest“ (welches von der Natur wohlerprobt ist) auf Maschinen uebertragen werden kann.

Tja … da geht sie hin, unsere Menschlichkeit … oder vielmehr erweitern wir „unsere“ Menschlichkeit und ich denke, dass dies ein richtiger Schritt in die Richtung ist, nicht zu Bueroklammern reduziert zu werden.

Aehnlich dem micromort vom letzten Mal beschreibt 1 microlife das Risiko inwieweit eine gegebene Aktivitaet eine halbe Stunde der Lebenserwartung „raubt“.

Das wurde natuerlich auch genauer untersucht … ach du meine Guete … zum Glueck wird mein langes zocken (minus 1 microlife pro 2 Stunden) teilweise dadurch kompensiert, dass ich heutzutage lebe und nicht vor 40 Jahren. Ebenso ermuntert mich das auch weiterhin mit dem Fahrrad zur Arbeit zu fahren, denn physische Aktivitaet hat einen positiven Wert. Wobei das wiederum auch total anders sein kønnte, denn zum Einen fahre ich an Straszen vorbei und bin der Luftverschmutzung ausgesetzt und zum Anderen hat Fahrradfahren einen Wert von 1 micromort pro 32 gefahrenen Kilometern … *seufz* … egal was ich mache, mich duenkt um’s sterben komm ich nicht drum herum.

Das beim letzten Mal Geschriebene fuehrt direkt weiter zu einer kleinen Diskussion des Gebrauchs des Wortes „Anfaengerprogrammiererniveau“ einordnen.

Dieses hat auch nix damit zu tun, dass ich so toll bin und so viel kann. Alles was ich mache, haben sich viel schlauere Menschen schon vor sehr langer Zeit ueberlegt. Ebenso wird das tagtaeglich von sehr vielen anderen Menschen benutzt.

Aber hier steckt auch wieder ein „Prozess“, der wichtig ist zu durchschauen, wenn wir jemals den Grund von „Fortschritt“ herausfinden wollen um das Vorankommen der Menschheit gezielt zu førdern.

Dass ich die Idee der Abbildung auf ganze Zahlen hatte, hing damit zusammen, dass ich in den letzten Jahren an unterschiedliche Probleme „geraten“ bin im Zusammenhang mit Programmieren.
Diese Probleme werden nicht mal erwaehnt wenn man anfaengt mit dem Programmieren lernen. Insb. nicht bei Python, eben weil es Spezialprobleme sind die (sehr) selten auftreten. Eins davon ist das erwaehnte Speicherproblem unterschiedlicher Datentypen. Dieses Wissen ist aber extrem leicht zugaenglich und gut dokumentiert und wird im Internet hinreichend oft besprochen, wenn man denn gezielt danach sucht.
Dass Zahlen weniger Speicher brauchen als Wørter „lief mir ueber den Weg“ lange bevor ich mich der Wikipedia widmete. Nur brauchte ich das vorher nie wirklich.

Das war also ein ueber Jahre andauernder Prozess und bisher schreiben wir an diesen Prozess nur „Bildung“ ran. Das ist ganz sicher ein unheimlich wichtiger Teil des Ganzes. Aber es kann auch nicht alles sein … siehe hier.

Auszerdem wird ueberhaupt nicht diskutiert, dass es ja oft mehrere Løsungen gibt (Python vs. C). Es wird immer nur der „Gewinner“ betrachtet und dargestellt. Als ob diese ganz spezifische Form der Løsung eines spezifischen Problems ja so aus Urprinzipien folgen muss. Oder anders: es wird (fast) nie in Betracht gezogen, dass eine spezifische Løsung davon abhaengig ist, von wo man aus dem Ideenraum kommt.
Aber genau das ist so wichtig, wenn man den „Prozess des Fortschritts“ besser verstehen will.

Deswegen denke ich, dass es fuer das Menschheitsprojekt „Fortschritt“ besser waere, wenn das Prinzip der „einfach nur Bildung“ zu einem „vielen Ideen aussetzen“ wird. Zum Glueck passiert das auch in der Schule oft genug … wenn (meiner Meinung nach) auch zu oft in dem oben erwaehten „A fuehrte zu B fuehrte zu C“-Rahmen. Ich verstehe warum das so ist und will das hier nicht diskutieren … mal davon abgesehen, dass die Gesellschaft das ja auch von der Schule erwartet, dass da junge Menschen rauskommen, die ganz konkrete Aufgaben (mehr oder weniger) direkt uebernehmen kønnen.
Wirklich kreatives Herangehen an (mehr oder weniger) unbekannte Probleme wird selten benøtigt. Dafuer war frueher die Universitaet zustaendig, aber die Gesellschaft erwartet von dieser ja auch immer mehr das was Schulen schon machen … aber das wollte ich hier ja gar nicht besprechen … um das abzuschlieszen sage ich mal so viel: Schule ist schonmal ein echt guter Anfang! … nur schade, dass das so politisiert wird … mit Testbarkeit usw. und schummeln, damit man bei Pisa gut aussieht … da werden Symptome bekaempft anstatt die Ursachen fuer schlechtes Abschneiden bei Pisa oder schlecht auf das Arbeitsleben vorbereitete jungen Menschen (ist das wirklich so?) herauszufinden.

Ach ja, das Prinzip des „Ideen aussetzen“ muss mitnichten „akademisch“ sein, sondern trifft 100 % auch in der lokalen Autowerkstatt zu oder bei den Restauratøren alter Gebaeude.

„Ideen ausgesetzt sein“ ist dezentral … ørtlich, zeitlich, psychologisch-entwicklungstechnisch … und ein lang anhaltender Prozess. Bildung wird all zu oft als zentral … in der Schule, von 7 bis 18 (etwas spaeter wenn man studiert), als Kind/Jugendlicher/junger Erwachsener … angesehen. Klar, gibt es die Lippenbekenntnisse des lebenslangen Lernens. Aber wenn ich sehe, wie niedrig die Latte in den zertifizierten (!) Kursen der sog. Erwachsenenbildung liegt, dann wundert es mich ueberhaupt nicht, dass man eigtl. nur als Autodidakt wirklich was lernt … *seufz* … und dahinter steckt dann aber wieder das Prinzip des „Ideen ausgesetzt sein“, denn als Autodidakt schaut man sich ja mal eben jene „Ideen“ naeher an, die einen interessieren.

Wieauchimmer, manchmal fuehrt der Prozess dann bei Menschen die ein Stueck voran gekommen, und eben keine „Anfaenger“ mehr sind zu „Geistesblitzen“. Und diese erscheinen dann „genial“ … weil vergessen ist, was alles nøtig war, damit ein solcher „Geniestreich“ ueberhaupt erst passieren kann. Womit ich wieder bei dem oben erwaehnten „Buhei um die Intelligenz bin“.
Mal ganz davon abgesehen, dass das vermutlich ueberhaupt kein „Geniestreich“ mehr ist, wenn man sich noch weiter entlang des Pfades dieses allgemeinen „Ideen ausgesetzt sein“-Prozesses ist.

Beim nochmal durchlesen faellt mir auf, dass das alles als ein „Dankeschøn an die Lehrer“ (jedweder Art) zu lesen ist. Seien es die Grundschullehrer, die Lesen und Schreiben beibringen, oder Lehrer die einem Analysis, Chemie und Goethe naeher bringen, oder die Lehrer die ein Buch schreiben, mit dem man bspw. Programmieren lernen kann.
Lehrer tun i.A. was und versuchen es zumindest die Menschheit weiter zu bringen … womit in gewisser Weise (mal wieder) dieser Beitrag zitiert werden kann.

So … ich befuerchte, dass ich es trotz der vielen Worte mal wieder nicht geschafft habe klar zu machen, worauf ich eigentlich hinaus will … *seufz* … naja, sei’s drum … ich hab’s wenigstens probiert.

Ich bezeichnete meine Idee die Titel der Wikipediaseiten in ganze Zahlen umzuwandeln als „Geniestreich“. Ebenso schrieb ich, dass dies ueber das „Anfaengerprogrammiererniveau“ hinaus geht. Ich møchte den Gebrauch der Worte mal etwas naeher diskutieren.

Zum Einen schreibe ich „Geniestreich“, weil ich mich selbst ganz toll finde, dafuer, dass ich diese Idee hatte. Das hat aber an und fuer sich nix damit zu tun ob ich …

[…] eine Person mit überragender schöpferischer Geisteskraft […]

bin. Bin ich naemlich nicht. Das Abbilden von etwas, auf etwas anderem ist eine uralte Idee (auch wenn die konkrete Anwendung hier schon ziemlich gut ist, insb. auch deswegen was dadurch erst ermøglicht wurde). Das ich das machte ist also an und fuer sich ueberhaupt nicht „genial“.
Aber dies war eine Idee, bei der ich den „Gluehbirne ueber dem Kopf“-Moment bewusst fuehlte. Dies ist auszergewøhnlich. Meistens habe ich eine ungefaehre Vorstellung, wie ich an ein gegebenes Problem heran gehen muss und welche Werkzeuge dafuer geeignet sind. Nach und nach fallen dann die, fuer die Løsung eines Problems notwendigen, Stuecke nach laengerer Arbeit an besagtem Problem auf die „richigen Plaetze“. „Heureka“-Momente passieren sehr sehr selten.

Und verglichen mit anderen Projekten gruebelte ich wirklich lange, wie ich das Kevin-Bacon-Problem effizient fuer einen Computer uebersetzen kann. Die Abbildung der Titel zu ganzen Zahlen war ein logischer Schritt, nachdem ich das Speicherproblem erkannt hatte. Das ich davon wusste, dass Zahlen und Wørter unterschiedlich repraesentiert werden im Computer, ist uebrigens das was ich mit „geeignete Werkzeuge“ oben meinte. Dies ist im Wesentlichen ein „Werkzeug“ aus der Programmierwelt, weil es (durch besagtes Speicherproblem) damit zusammenhaengt. Aber wie gesagt, hier begann die „Gluehbirne ueber dem Kopf“ zu leuchten … wenn auch erst schwach.

Bzgl. des Gebrauchs des Wortes „Geniestreich“ spielen dann hier die darauf aufbauenden weiteren (beim letzten Mal beschriebenen) Ideen mit hinein. Insb. auch, weil diese dann relativ schnell aufeinander folgten. Das ganz konkret bewusst werden des altbekannten Faktes, dass die die Zahlenwerte der Titel als Position auf dem Zahlenstrahl zu sehen sind und die Verknuepfung, dass dies der Position eines Titels in einem Vektoren entspricht (letzteres sieht aus wie eine Idee, sind aber eigentlich zwei). Das poppte alles pløtzlich in meinem Kopf auf, obwohl ich das ja eigentlich laengst alles wusste.
Ich habe „gefuehlt“, wie die einzelnen Teile sich zur Gesamtidee bzgl. der (technischen) Løsung des Problem zusammensetzen lassen.
Und genau das ist das „geniale“ (in diesem sehr engen und limitierten Zusammenhang), denn das ist, was „Genies“ machen: Ideen aus unterschiedlichen Themenbereichen verknuepfen um Probleme zu løsen. Das ist also an und fuer sich ’ne Sache, die ’ne ganze Menge Leute relativ oft machen. Wir schreiben da nur „Genie“ ran, wenn wir selber nicht drauf gekommen waeren. Meiner Meinung nach haengt das mit dem Buhei zusammen, was diese Gesellschaft rund um „Intelligenz“ veranstaltet. Ja, das kommt mir massiv zu Gute, richtig ist das dennoch nicht. Aber ich schweife ab.

Der „Streich“ kommt dann daher, weil das so pløtzlich geschah, dass ich mehr oder weniger auf einen Punkt zeigen kann, bzw. einen etwas laenger andauernden Denkprozess … aber maximal drei Tage, in denen mein Gehirn (durch interne Selbstgespraeche) das zusammengesetzt hat.

Und dann war da eben der „Heureka Moment“, als ich nach besagten drei Tagen erkannte, dass das tatsaechlich funktionieren kann … tihihi.

Aber genug fuer heute. Beim naechsten Mal dann mehr bzgl. der Einordnung des Gebrauchs des Wortes „Anfaengerprogrammiererniveau“.

Heute folgt ein langer und sehr technischer Beitrag. Das liegt daran, weil all dies hier den Warpantrieb der ganzen Problemløsungsmaschinerie beschreibt. Und weil’s eh schon so lang wird, verbrauche ich keine weiteren Worte fuer die Vorrede auf und frage gleich …

… wie muss ich mir eigentlich das Linknetzwerk der Wikipedia vorstellen?
Wenn man „Netzwerk“ hørt, dann denkt man mindestens an etwas Zweidimensionales und eine Form eines solchen zweidimensionalen Netzwerks kann man in den bekannten vereinfachten Beispielen sehen. Die Titel sind die Knotenpunkte und die Links dann die Pfade (zum naechsten Knotenpunkt).
Diese Vorstellung hat mir aber nicht geholfen eine Idee zu entwickeln, wie man technisch effizient dieses Netzwerk „abschreiten“ kønnte. Dann hatte ich das Sprachproblem aber „verzahlt“ und ab da formte sich (zunaechst unbewusst) in mir eine Idee.

Aus den Titeln wurden fortlaufende (!) Nummern. Ich kann die also auf eine Zahlengerade setzen. Und von jedem Punkt komme ich zu ganz bestimmten anderen Punkten. Die Links sind also eine Abbildungsvorschrift — eine Funktion. Diese ist nicht bijektiv sondern nur surjektiv. Deswegen leuchtete mir zunaechst nicht ein, was die Zielmenge dieser Abbildung ist. Also malte ich mir das drei Tage lang immer und immer wieder in meinem Kopf aus:

Nur leider hing ich darin fest. Ich wusste nicht weiter, wie ich das technisch umsetzen soll. Also ich hatte schon ein paar Ideen, aber die schienen mir technisch nicht praktikabel. Der Grund war, dass ich mir ja auf jedem Linklevel merken muss, welche Knoten schon besucht waren, damit ich nicht in Schleifen gerate. Das ist an und fuer sich kein Problem, denn die kann ich einfach alle in einen „Waggon der schon besuchten Knoten“ stecken. Das Problem ist dann, dass ich fuer jede der ueber 161-Millionen Abbildungen haette schauen muessen, ob die in besagtem „Waggon“ ist (das sollen die gestrichelten Pfeile darstellen), oder nicht. Und egal wie das Ergebnis dieses Nachschauens war, ich muss dann immer noch eine Entscheidung treffen was danach zu tun sei. All das sind Rechenoperationen die viel Zeit kosten.

Nach drei Tagen daemmerte mir endlich die entscheidende Idee; zunaechst zøgernd, doch dann immer enthusiastischer: die Abbildungen bilden den Zahlenstrahl ja auf sich selber ab! Also buchstaeblich … bzw. wohl eher zahlstaeblich. Das Ganze sieht also viel eher so aus (LL = Linklevel):

Knoten die ich schonmal besucht hatte konnte ich nach dem ersten Besuch einfach „raussschmeiszen“ und wenn eine Abbildung dann ins Leere fuehrt macht das nix.

Und ziemlich schnell nach dieser entscheidenden Idee hatte ich gleich noch einen zwei Geistesblitze: diese Zahlengerade ist ja ein Vektor! … mit 5,798,312 Dimensionen (die Zahlengerade zaehlt nur nur bis 5,798,311, weil ich bei der Null anfange zu zaehlen). Und jede Abbildung zeigt auf genau einen Punkt in diesem vieldimensionalen Raum!

Aber wenn ich das als einen Vektor sehen kann, dann kann ich das Problem doch mit den simpelsten Methoden der linearen Algebra angehen! Und lineare Algebra ist doch genau das, wofuer Computer gebaut wurden. Das bedeutet, dass ich anstatt umstaendlicher und Prozessorzeit verbrauchender „nachschauen und mittels verzweigter Anweisungen Entscheidungen treffen“-Operationen einfach nur Vektoren miteinander addieren und multiplizieren kann.

Und hier kommt jetzt die Genialitaet der beim letzten Mal besprochenen Abbildung der Wørter auf (ganze) Zahlen zum Tragen … und ein weiterer Geistesblitz: der Wert einer Zahl, entspricht der Position AUF dem Zahlenstrahl. Ist ja voll banal die Erkenntnis, aber in „Vektorform“ bedeutet dies: jeder Titel (als Zahlenwert) entspricht einem eindeutigen (!) Einheitsvektor in diesem multidimensionalen Vektorraum! Ein Einheitsvektor hat nun aber die Laenge 1. Das bedeutet, dass der Zahlenwert des Titels die Position in diesem spezifischen Einheitsvektor bestimmt, die NICHT Null wird, sondern Eins. Geil wa!

OK, ich gebe zu, das ist alles etwas abstrakt. Deswegen gehen wir mal gemeinsam der Reihe nach durch die technische Umsetzung.

Zunaechst einmal habe ich ja mein Lexikon in dem steht welcher Titel welche Links hat. Das behalten wir im Hinterkopf fuer wenn wir das brauchen. Andernfalls steht das nur passiv im Hintergrund rum, ich schlage spaeter darin nur nach wo die Links zu jedem Titel hinfuehren.

Das Folgende machen wir dann fuer jeden Titel.

Zunaechst initialisieren wir drei Vektoren mit 5,798,312 Dimensionen.
Der eine Vektor stellt alle Titel dar, die wir schon „besucht“ haben. Da wir im Moment noch keinen Titel besucht haben, stehen da ueberall Einsen. Nach dem Besuch schmeiszen wir die Eins an der Stelle des besuchten Titels raus (und zurueck bleibt eine Null). Das wird wichtig fuer spaeter. Diesen Vektor nenne ich < Verbleibend >.
Der zweite Vektor repraesentiert alle Titel die sich auf dem gerade unter Untersuchung befindlichen Linklevel befinden und NICHT bereits vorher besucht wurden. Die Elemente dieses Vektors sind alle Null, AUSZER wenn ich auf dem gegebenen Linklevel zum ersten Mal auf diesen Titel treffe. Dann wird wird der Wert des Vektors an der Stelle die dem Zahlenwert des Titels entspricht Eins. Ich nenne diesen Vektor < Jetzt >.
Den dritte Vektor nenne ich < Abbildung >. Dieser wird ebenso mit Nullen initialisiert und repraesentiert spaeter die „Ausgaenge“ von einem Linklevel zum naechsten.

Da wir uns ganz am Anfang befinden ist < Jetzt > natuerlich komplett „leer“ (also besteht nur aus Nullen). Dito, ist < Verbleibend > total „voll“ (besteht also nur aus Einsen). Fuer beide gilt eine Ausnahme, naemlich an der Position des einen Titels, dessen Linknetzwerk wir erforschen møchten. Im obigen Beispiel waere es dann Position 23 an der eine Eins in < Jetzt > bzw. eine Null in < Verbleibend > steht.
Fuer das Beispiel sehen die drei Vektoren als Zeilenvektor nach der Initialisierung so aus:

Die Indizes links unten an jeder Null oder Eins repreaesentieren die Positionen (oder Dimensionen im Sinne von x, y, z …) im Vektor. Man beachte, dass ich bei Null anfange zu zaehlen. An die richtige Position gelange ich einfach durch den Zahlenwert der betreffenden Titel. Man beachte ebenso, dass fuer < Verbleibend > und < Jetzt > der Wert an Stelle 23 anders ist als fuer alle anderen Positionen in diesen beiden Vektoren. Dies gilt nicht fuer < Abbildung >, denn wir haben ja gerade erst alles initialisiert und noch gar nicht geschaut, wo die 23 hin fuehrt.

Deswegen schauen wir im naechsten Schritt im Lexikon fuer _alle_ Titel die eine Eins in < Jetzt > haben (die also neu besuchte Titel auf diesem Linklevel sind) nach, wohin die fuehren. Die Zahlwerte dieser Links bestimmen auf welchen Positionen darauf im Vektor < Abbildung > eine Eins zu setzen ist. Im Beispiel muessen wir das erstmal nur fuer die 23 tun:

Danach finden drei der vier Auswertungen statt. Zum Ersten evaluiere ich, wie oft auf dem gegebenen Linklevel der urspruengliche Titel zitiert wird (Selbstreferenz). Im gezeigten Beispiel ist das nicht der Fall aber im Allgemeinen passiert das durchaus.
Zum Zweiten schaue ich pro Linklevel, welche Seiten zitiert werden, aber nur OB und NICHT wie oft die zitiert werden. In der Untersuchung des Linknetzwerkes fuer nur einen Titel, dann ist dieser Wert pro Linklevel fuer alle anderen Titel entweder einmal oder keinmal. Aber ich schaue mir das ja fuer alle fast 6 Millionen Titel an. Ich mache das auf diese Weise, weil mich interessiert, ob es Seiten gibt die prinzipiell eher bei høheren Linkleveln zitiert werden, verglichen mit „normalen“ Seiten. Deswegen kann ich hier auch nur „ob“ und nicht „wie oft“ zaehlen (im Unterschied zur Selbstreferenz), denn dann wuerden „populaere“ Seiten durch die schiere Anzahl der Zitate die diese bekommen das Signal verfaelschen.
Rein praktisch muss ich dafuer nur < Abbildung > auswerten und mir fuer das gegebene Linklevel merken, an welchen Positionen dieser Vektor nicht Null ist. Cool wa! So einfach ist das.
Als Drittes werte ich die Anzahl der totalen „Ausgaenge“ von diesem Linklevel zum naechsten aus. Das entspricht einfach nur der Summennorm (oder Laenge) des Vektors < Abbildung >.

Nun muss ich die naechste Iteration vorbereiten. Zunaechst muss < Jetzt > in der naechsten Iteration an den Positionen eine Eins haben zu denen ein „Ausgang“ fuehrt. Unter der Einschraenkung, dass diese Positionen nicht auf einem frueheren Linklevel bereits besucht wurden! Das kann ich einfach durch eine elementweise (!) Multiplikation von < Verbleibend > mit < Abbildung > erreichen:

Das hier ist so geil! Man nehme an, dass < Abbildung > (also die „Ausgaenge“ vom jetzigen Linklevel zum naechsten) an einer bestimmten Stelle einen Wert von Eins hat (einfach weil das halt ein Link ist der auf diesem Linklevel auftaucht und dorthin will). Man nehme weiter an, dass ich den Titel der dieser Position entspricht aber schon besucht habe. In dem Fall hat < Verbleibend > an der selben Position einen Wert von Null. Somit wird das Produkt der Elemente der beiden Vektoren an dieser Position fuer den < Jetzt > Vektor der naechsten Iteration auch Null. Und das ist wichtig, denn ein Element in < Jetzt > soll ja nur dann Eins sein, wenn ich da noch nicht war, damit ich nicht in unendliche Schleifen gerate. Das wird klarer an Position 23, wenn ich weiter unten die Vektoren fuer die zweite Iteration voll ausschreibe.

An dieser Stelle nehme ich dann die letzte Auswertung vor. Die Laenge des neuen (!) < Jetzt > Vektors, ergibt die Anzahl der neuen, noch nicht besuchten „Ausgaenge“ auf diesem Linklevel, mit der gegebenen Startseite. Das møchte ich zusaetzlich zur obigen Anzahl der totalen „Ausgaenge“ wissen, denn nur die neuen zu besuchenden Seiten verlaengern die Kette von Kevin Bacon zu anderen Seiten der Wikipedia.
Das hier muss ich uebrigens sowieso auswerten, denn dies ist die Abbruchbedingung fuer die aeuszerste Schleife. Das bedeutet, dass wenn die Laenge des neuen < Jetzt > Vektors null wird (wenn es also keine „Ausgaenge“ zu noch nicht besuchten Seiten gibt), dann habe ich das komplette Linknetzwerk fuer die gegebene Startseite besucht. In dem Fall kann das ganze Prozedere natuerlich fuer den naechsten Titel von vorne beginnen.

Aber dies ist meistens erst bei høheren Linkleveln der Fall und deswegen møchte ich nun erstmal das naechste Linklevel untersuchen. Dafuer muss ich noch zwei letzte Sachen vorbereiten. Zum Einen muss < Abbildung > wieder zu null initialisiert werden (damit da in der naechsten Iteration wieder nur die neuen „Ausgaenge“ drin stehen). Zum Zweiten muss der neue < Verbleibend > Vektor berechent werden; ich habe ja jetzt mehr Seiten als zu Beginn der Iteration gesehen. Das ist ganz einfach, denn hier muss ich nur den (neuen) < Jetzt > Vektor vom bisherigen (alten) < Verbleibend > Vektor subtrahieren.

Und so einfach, meine lieben Leserinnen und Leser, ist die Løsung des Kevin-Bacon-Problems! Das ist ja wohl mal voll geil, wa! Deswegen schrieb ich ganz oben auch „Warpantrieb“, denn dadurch, dass ich hier nur Nullen und Einsen lesen, schreiben, multiplizieren und subtrahieren muss kann das ganze urst schnell berechnet werden … naja … „urst schnell“ ist relativ und ich komme darauf an anderer Stelle zurueck.

Hier nun in visueller Form die selben Schritte fuer Linklevel 2 des Beispiels:

In dieser zweiten Iteration wird an drei Stellen sichtbarer, warum ich das alles so geil finde … und damit auch mich so toll finde, weil ich da von alleine drauf gekommen bin.
Im Schritt „Ausgaenge finden“ wird < Abbildung > an Position 23 natuerlich zu 1 gesetzt (das ist noch nicht das Fetzige). 5 will da hin, selbst wenn ich da schon war. Wenn ich dann aber < Jetzt >_{fuer naechste Iteration} berechne wird das Element an Position 23 (wie oben bereits erwaehnt) durch die Multiplikation mit < Verbleibend > zu Null. DAS ist das erste Fetzige, denn diese Multiplikation ist oben besagte Kontrolle, dass ich nur bei Titeln weiter gehe, die ich noch nicht besucht hatte. Das ganze aber ohne Prozessorzeit verbrauchende Fallunterscheidungen.
Bei der selben Berechnung sieht man auch, dass die „Ausgaenge“ nicht einzeln „durchschritten“ werden (so wie wenn ein Mensch mit den Augen den Pfeilen folgt), sondern alle gleichzeitig! Das ist das zweite Fetzige.
Das dritte Fetzige ist dann letztlich, wenn < Verbleibend >_{fuer naechste Iteration} berechnet wird. Dort sieht man, wie die Laenge dieses Vektors von Linklevel zu Linklevel immer kleiner wird, weil immer mehr Einsen zu Nullen werden. Das soll ja auch so sein, denn ich habe ja immer mehr und mehr Wikipediaseiten gesehen von Linklevel zu Linklevel.

Und das ist alles so fetzig, weil die ganzen die Problemløsung bzgl. der Uebersicht ueber wichtige Aspekte zu behalten, einfach so aus der „Mathematisierung und Verzahlung“ mit „heraus fallen“.
Haette ich hier uebrigens nur den Code hinkopiert, so waere dieser Artikel deutlich kuerzer, aber mglw. auch deutlich weniger verstaendlich, gewesen. Denn der Warpkern der Problemløsungsmaschinerie sind nur ’n paar Zeilen Code.

Fuer die tatsaechliche Implementation brauchte ich mehrere Wochen. Ich musste das naemlich letztlich in C programmieren (womit ich mich fast gar nicht auskenne) UND ich wollte das parallelisieren, dass also die Linknetzwerke mehrerer Titel gleichzeitig durchschritten werden. Diese Herausforderung war aber sooooooo herrlich und das zustande bringen der (technisch, praktikablen) Løsung soooooo befriedigend.
Damit meldet sich mein innerer Zefram Cochrane fuer heute ab.