Søren in Norwegen

Zum Jubilaeum (heute vor einem Jahr erschien der allererste Beitrag in dieser nicht ganz so kurzen Miniserie) geht es endlich mal weiter mit Kevin Bacon. Auch wenn die Weise der Publizierung das nicht erkennen laeszt, so habe ich die Auswertung doch monatelang vor mich hergeschoben, weil das so viel ist.

Heute nun steige ich gleich voll ein und verliere mich in einer Sache, die zunaechst wie ein kleines, nicht ganz so wichtiges Detail aussieht. Zumindest erschien es mir so. Dann machte ich aber ein paar Ueberschlagsrechnungen und irgendwie stimmte das Hinten und Vorne nicht. Die Aufklaerung des Mysteriums war eine spannende Sache und legt dann bereits ganz am Anfang SEHR viel ueber das Linknetzwerk der Wikipedia dar.
Das ist als eine Art „Warnung“ anzusehen, dass dies ein laengerer Beitrag wird.

Als kurze Wiederholung:
– Ich rede von Linkleveln und die Nummer des Linklevels sagt aus, wie viele „Schritte“ ich im Linknetzwerk getan habe um dort hinzukommen.
– Die Linklevel fangen an bei Null zu zaehlen, was dann natuerlich dem Titel / der Wikipediaseite entspricht, dessen Linknetzwerk ich jetzt gerade untersuche.
– Links die in vorherigen Schritten besucht wurden, werden nicht nochmal besucht.
– Auf jedem Linklevel sammle ich Daten und heute geht es um die totale Anzahl von Links die zum naechste Linklevel fuehren. Siehe dazu mein Artikel von neulich (gut, dass ich den geschrieben habe).
– Ich bin i.A. nicht an einzelnen Seiten interessiert, sondern an der Gesamtverteilung der Grøsze(n) von Interesse ueber alle Titel.

Und nun geht’s los und immer schøn der Reihe nach.

In der Gesamtheit sieht die Verteilung der totalen Anzahl von Links per Linklevel ueber alle Wikipediaseiten so aus:

Das sieht einfach aus, denn Verteilungen hatte ich hier ja schon ein paar Mal. Aber wenn man das auf sich wirken laeszt, dann sind da eine Vielzahl von Beobachtungen. Viele dieser Beobachtungen sind allgemein und treten auch so, oder zumindest in aehnlicher Form, bei anderen Grøszen von Interesse auf. Weil wir, also ihr, meine lieben Leserinnen und Leser, und ich, dem hier zum ersten Mal begegnen, møchte ich etwas naeher darauf eingehen.

Wie so oft sehen wir, dass die Darstellung mit linearer Ordinate im linken Bild nicht viel hergibt. Andererseits sehen wir bei lineraer Darstelung, wie schnell alles passiert und dann auch wie schnell alles wieder vorbei ist. Das Maximum ist nach nur vier Schritten erreicht. Und bereits auf Linklevel 3 tuen sich fast 100 Billionen Links auf. Das heiszt bei ca. 6 Millionen Titeln, habe ich nach nur 3 Schritten im Durchschnitt bereits ca. 150 Millionen weiterfuehrende Links vor mir.
Das erklaert natuerlich, warum man die meisten Titel von jedem anderen Titel mittels nur drei (oder vier) Schritten erreichen kann. Das war ja eine ganz konkrete Sache, ueber die ich mich bereits im allerersten Beitrag dieser Reihe (wenn auch nicht direkt) wunderte und die in mir ueberhaupt erst das Interesse an dem ganzen Thema weckte. Damit waere das nach einem Jahr dann endlich geklaert. Toll wa!

Bei logarithmischer Ordinate sieht man dann aber, dass auch nach dem Maximum noch laengst nicht alles vorbei ist. Und ach du meine Guete! Die Dynamik in dieser Verteilung geht von (knapp unter) 100 bis 10¹⁴ … das sind 12 Grøszenordnungnen! Das ist so viel, dass ich hier nicht mal mehr die kleinen Striche an der Achse zeichne. Dabei finde ich die doch so toll, weil sie so charakteristisch fuer logarithmische Achsen sind :) .
In Zukunft werde ich Verteilungen mit lineare Ordinaten nur noch zeigen, wenn es zu Informationsgewinn fuehrt. Bei einer solchen Dynamik ist es ziemlich offensichtlich, dass die logarithmische Darstellung der linearen ueberlegen ist.

Auch wenn das Allermeiste nach Linklevel 8 vorbei, so sieht man auch, dass es Wikipediaseiten gibt, die noch viel mehr Schritte benøtigen, bevor man diese erreicht hat. Hier nehme ich dann meine Aussage von oben teilweise zurueck und sage, dass mich dann doch interessiert, welche Seiten das sind.
Aber auch die letzte Ecke des Weltwissens ist nach maximal 73 Schritten erreicht. Der letzte Balken ist auf Linklevel 72 und das bedeutet, dass es nur noch von dort „Ausgaenge“ zu Seiten gibt, die ich vorher nicht besucht habe. Dies wird aber an anderer Stelle genauer betrachtet.

Das sind allgemeine Sachen. Heute von Interesse ist nur das Maximum (man beachte, dass die Ordinate nicht bei Null, sondern erst bei 10 Millionen anfaengt; die Balken sind also „eigentlich“ viel laenger) …

… und eigentlich interessiert mich gar nicht das Maximum an sich, sondern nur der Aufstieg von Linklevel 1 zu Linklevel 2 … und was dies ueber das Linknetzwerk sagt. Aber der Reihe nach.

Auf Linklevel 0 … ach je, das wird mir zu umstaendlich das immerzu zu schreiben und ich kuerz das jetzt mit „LL“ ab und der Wert ist dann der Index … jedenfalls betraegt die Summer der totalen Links auf LL₀ 165,913,569. Diese Zahl kenne wir schon, denn es ist die Summe aller Links, die ich auf allen Wikipediaseiten finde. Zum ersten Mal sind wir auf diese Zahl bereits vor langer Zeit gestoszen.
Wenn ich nun diese ca. 165 Millionen „Ausgaenge“ zu LL₁ nehme, dann treffe ich dort auf mehr als 27 Milliarden Links. Cool wa, wie schnell das waechst! … … … Moment mal! … wieso waechst das denn SO schnell? … Das kommt mir etwas komisch vor.

Und damit sind wir bei dem am Anfang erwaehnten Detail, welches leicht zu uebersehen ist.

Machen wir mal eine Ueberschlagsrechnung. Die ca. 165 Millionen Links auf LL₀ verteilen sich auf ca. 6 Millionen Seiten. Das macht ca. 30 Links pro Seite im Durchschnitt … nicht ganz, aber es ist ja nur eine Ueberschlagsrechnung. Wenn ich nun 165 Millionen Seiten auf LL₁ mit (durchschnittlich) 30 Links pro Seite multipliziere, dann komme ich auf ca. 5 Milliarden „Ausgaenge“ zu LL₂.
Einen Faktor zwei haette ich mglw. als „Fehler“ abgetan, aber ’n Faktor 5 zu viel? Hier scheint ein nicht ganz so offensichtlicher Mechanismus zu wirken … SUPERSPANNEND!

Aber vielleicht ist es doch ganz einfach. Denn mglw. muss ich mit dem Median und nicht dem Mittelwert rechnen … da muss ich mal eine der aelteren Analysen raussuchen … *raussuch* … im Wesentlichen ist’s das hier … øhm … nø … das ist auch nicht des Raetsels Løsung, denn die Haelfte der Seiten haben 15 Links oder weniger … Mhmmmmm … aber Moment … wenn der Mittelwert bei ca. 30 liegt, dann bedeutet das doch, dass Seiten mit (deutlich) mehr als 30 Links pro Seite einen groszen Einfluss haben muessen … mhmmmmm …

Einschub: die Idee mit dem Median war, wenn man mal drueber nachdenkt, von Anfang an zum Scheitern verurteilt … aber das Resultat dieser Idee (der relativ grosze Unterschied zwischen Median und Mittelwert) fuehrte mich letztlich in die richtige Richtung … das ist das Schøne am Erforschen eines Themas … das klappt mitnichten alles beim ersten Mal, aber wenn man was probiert was zu nix fuehrt, wird man mitunter auf Details aufmerksam, die man so vorher gar nicht bemerkt hat … und dann kommt man ueber einen (mehr oder weniger) kurzen Umweg doch noch zur Løsung :) .

Da stellt sich nun die Fragen: wie grosz ist eigentlich der Einfluss vielzitierter Seiten?
Ich stellte die 50 meistzitierten Seiten bereits vor. Und eine Seite, die bspw. 1000 Links hat und 300-tausend Mal zitiert wird, wuerde zum Gesamtsignal 300 Millionen Links — also ca. 1 % — beitragen. Gleichzeitig wissen wir, dass das Maximum der Verteilung der Zitierungen bei eins liegt, waehrend das Maximum der Links pro Seite bei ca. 10 liegt. Diese zwei Dinge zusammen fuehren dazu, dass ich fuer die gleiche Signalstaerke die die 300-tausend Mal zitierte Seite hat, 30 Millionen Seiten braeuchte, die ein Mal zitiert werden (mit 10 Links pro Seite). So viele gibt es gar nicht und um besagte Signalstaerke zu erreichen muesste ich alle Seiten zusammen nehmen, die einmal, zweimal, dreimal, … neunmal, zehnmal zitiert werden.
Diese kurze und einfache Ueberlegung zeigt bereits, wie krass ueberproportional der Einfluss nur einer vielzitierten Seite sein kann. Aber die 1000 Links oben habe ich mir nur ausgedacht und es stellt sich die naechste Frage: wie sieht denn die Anzahl der Links in Abhaengigkeit von den Zitierungen aus?

Nun ja, das ist etwas unuebersichtlich und sieht so aus:

Wir sehen, dass wir erstmal nix sehen, auszer einem groszen schwarzen Fleck.
Der schwarze Fleck kommt durch die Ueberlappung sehr sehr sehr vieler Datenpunkte zustande. Wobei ich die Punkte fuer null Zitierungen bzw. null Links weggelassen habe, weil die hier nicht relevant sind.

Wenn man sich alles mal genauer anschaut, dann sieht man, dass die Seite mit den meisten Zitierungen tatsaechlich ca. 1000 Links hat. Das war aber reiner Zufall.
Desweiteren sieht man, dass Wikipediaseiten selten deutlich mehr als 1000 Links haben und dass die Anzahl der Links unabhaengig ist von der Anzhal der Zitierungen fuer Seiten die weniger als ca. 1000 Zitierungen auf sich vereinen.
Ab ca. 1000 Zitierungen haben die entsprechenden Seiten aber anscheinend eine Art „Mindestanzahl“ an Links, in Abhaengigkeit von der Anzahl der Zitierungen. Das sieht man an der schraeg liegenden „Abbruchkante“, welche die „Mindestanzahl“ an Links festlegt, die eine Seite haben „muss“, wenn sie bspw. 50-tausend Zitierungen auf sich vereint.
Das war erstmal ein _aeuszerst_ (!) ueberraschendes Ergebniss. Damit hatte ich nicht gerechnet. Ohne weitere Vorannahmen gibt es dafuer auch gar keinen Grund, denn warum sollte eine vielzitierte Seite nicht nur einen Link haben. Und das sieht man ja auch bspw. an den drei vertikalen Punkten bei ca. 60-tausend Zitierungen. Das sind drei so oft zitierte Seiten mit weniger als 10 Links.
Andererseits ist dieses Ergebniss dann doch nicht so ungewøhnlich wenn man bedenkt, dass vielzitierte Seiten vermutlich (eben wegen deren Popularitaet) sehr gut kuratiert sind. Das bedeutet dann, dass in diesen Artikeln vermutlich jedes kleine bisschen verlinkt ist. Je populaerer ein Artikel ist, um so mehr beinhaltet dieser vermutlich, was dann wiederum zu mehr Links fuehrt.
Dennoch, dies war eine spannendes Resultat, eben weil mich das so ueberrascht hat.

Wie genau hilft uns dies nun aber mit der obigen Frage? Nun ja, das ist ganz einfach. Ich muss fuer jede Wikipediaseite das Produkt aus der Anzahl der Links und der Anzahl der Zitierungen bilden. Die Summer aller dieser Produkte sollte dann die ca. 27 Milliarden| totalen Links von LL₁ zu LL₂ ergeben.

Aber an dieser Stelle breche ich ab. Es muss noch ziemlich viel erklaert werden und der Beitrag ist jetzt schon so lang.

Beim letzten Mal erklaerte ich drei der vier Grøszen die ich beim Abschreiten des Wikipedialinknetzwerkes untersucht habe. Die vierte ist eine Grøsze, die ich Linkfrequenz nenne. In kurz ist die Linkfrequenz ein Zaehler pro Linklevel und Titel OB (aber NICHT wie oft) besagter Titel insgesamt beim Abschreiten der Linknetzwerke aller Titel (inklusive sich selber) als Link auftaucht. Das ist gar nicht so kompliziert, wie sich diese komprimierte Beschreibung mglw. anhørt. Im Prinzip schaue ich auf jedem Linklevel, welcher (anderen) Titel zitiert werden und zaehle dann die Linkfrequenz(en) fuer diese (anderen) Titel und dieses Linklevel einmal hoch. Das wird (hoffentlich) verstaendlicher mit einem Beispiel.

Dafuer ziehe ich das (etwas modifizerte) abgeschlossene Beispiellinknetzwerk von vor einiger Zeit wieder heran:

Als Beispiel folgen wir allen Linkketten die zu Borkenkaefer fuehren.

Auf Linklevel 0 von Baum und Frucht wird Borkenkaefer zitiert. Damit zaehlt der Linkfrequenzzaehler von Borkenkaefer fuer Linklevel 0 zwei mal hoch.

Auf Linklevel 1 von Kirsche (via Baum), von Apfel (via Baum) und nochmals von Apfel (wie Frucht) wird Borkenkaefer zitiert. Auch hier zaehlt der Linkfrequenzzaehler von Borkenkaefer nur zwei mal hoch (diesmal fuer Linklevel 1). Der Grund ist, dass Baum und Frucht von Apfel aus gesehen auf dem gleichen Linklevel liegen. Das bedeutet, dass Borkenkaefer zwei mal auf Linklevel 1 (von Apfel aus gesehen) zitiert wird. Aber da ich nur daran interessiert bin OB und NICHT wie oft ein Titel pro Linklevel zitiert wird, zaehlt der Zaehler fuer diese beiden Faelle nur ein mal. Dies wird noch zwei Mal der Fall sein und da schreibe ich dann nur „dito“ und meine die Erklaerung hier.

Auf Linklevel 2 von Kuchen wird Borkenkaefer 3 mal zitiert (via Kirsche und Baum, via Apfel und Baum, via Apfel und Frucht). Dito, denn es ist wieder der selbe Ursprungsartikel von dem aus dieses Linklevel erreicht wurde und deswegen geht der Zaehler nur ein Mal hoch.

Zum Abschluss wird der Linkfrequenzzaehler von Borkenkaefer auf Linklevel 3 zwei mal hochgezaehlt. Einmal von Kirsche aus gesehen (via Kuchen, Apfel, Baum und Kuchen, Apfel, Frucht; dito) und einmal von  Apfel aus gesehen (via Kuchen, Kirsche, Baum).

Insgesamt sieht die komplette Linkfrequenzmatrix fuer dieses kleine, abgeschlossene Netzwerk so aus.

Die Linkfrequenzzaehler von Kuchen sind etwas speziell. Von Apfel aus gesehen zaehlt der Zaehler fuer Linklevel 0 einmal hoch, dann geht der Algorithmus zu Kuchen und von dort weiter zu Kirsche. Kirsche ist auf Linklevel 2 (von Apfel aus gesehen) und zitiert nochmal Kuchen. Damit geht der Zaehler fuer Linklevel 2 um einen hoch. Der Algorithmus geht aber nicht zurueck zu Kuchen, denn dieser Titel wurde ja (von Apfel aus gesehen) bereits besucht. Das Gleiche passiert wenn Kirsche der Ursprungsartikel ist.

Das scheint etwas kompliziert und die Frage ist, wofuer ich das eigentlich brauche. Der Grund ist, dass ich bei ersten (noch nicht systematischen) Tests ein paar Merkwuerdigkeiten bei der Anzahl der neuen Links auf hohen Linklevels gesehen habe. Es scheint, dass es Seiten gibt, die (fast) immer nur ganz am Ende der Linkkette (bei Linkleveln ueber 50) zitiert werden. Durch die Beobachtung der Linkfrequenz hoffe ich diesen auf die Spur zu kommen. Sollte meine Vermutung richtig sein, sollten derartige Seiten Peaks in der Verteilung bei hohen Linkleveln haben. Dies im Gegensatz zu „normalen“ Seiten, bei denen ich eine Art Plateau bei kleineren bis mittleren Linkleveln erwarten wuerde. Die genaue Analyse wird das zeigen … und noch ein bisschen auf sich warten lassen, weil ich gerade so viele „Faesser“ aufgemacht habe.

Ich weisz, dass ihr, meine lieben Leserinnen und Leser ganz gespannt auf die Ergebnisse wartet. Aber ihr seht ja auch, dass ich z.Z. ein bisschen mit anderen Projekten abgelenkt bin.

Weil ich das Kevin Bacon Projekt nicht ganz ruhen lassen will, habe ich mir gedacht zwei kurze Beitraege bezueglich den Daten die ich eingesammelt habe zu schreiben. Mich duenkt dass ich das in diesem sehr detaillierten und technischen Beitrag bereits erwaehnte.

Bisher ging es aber nur um das (super spannende und interessante) „Vorspiel“ … also die Erklaerung was ich eigentlich gemacht habe, um das Linknetzwerk der Wikipedia zu analysieren … abgesehen von der Analyse die nicht das „Abschreiten“ des Linknetzwerks benøtigte.
Dies wurde dann alles in ein Programm implementiert und besagtes Programm lieferte die gewuenschten Resultate — die oben erwaehnten eingesammelten Daten. Drei dieser Grøszen sind einfach zu verstehen. Die vierte erhaelt ihren eigenen (kurzen) Beitrag.

Am anschaulichsten scheint mir zu sein, den Prozess des „Abschreitens“ des Linknetzwerks nochmal durchzugehen und fuer jede Grøsze zu besprechen.

Am Anfang nehme ich einen Wikipediabeitrag (oder Titel wie ich es auch nenne). Dieser ist auf Linklevel 0 und hat eine gewisse Anzahl Links als „Ausgaenge“ zum Linklevel 1. Die _totale_ Anzahl dieser Links notiere ich mir fuer Linklevel 0. Als Beispiel nehme ich an, dass es 23 Ausgaenge waren zu 23 verschiedenen Wikipediaseiten.

Linklevel 1 besteht nun aus ALLEN diesen 23 Seiten. Diese 23 Seiten haben INSGESAMT wieder eine gewisse Anzahl Links. Nehmen wir als Beispiel an, dass es im Durchschnitt 10 Links pro Seite sind. Damit is die _totale_ Anzahl Links fuer Linklevel 1 zu Linklevel 2, fuer diesen ganz spezifischen, am Anfang gewaehlten, Wikipediabetrag, 230.
Nun nehmen wir weiter an, dass 5 von den 23 Seiten jeweils einmal auf besagten urspruenglichen Wikipediabetrag zurueck verlinken. Das hat zwei Folgen.
Zum Einen sehe ich ein Zurueckverlinken-zum-Ursprung als Selbstreferenz und die Summe aller Selbstrefrenzen notiere ich mir pro Linklevel. Das machte ich auch schon bei Linklevel 0, aber dort ist die Anzahl der Selbstreferenzen meist Null.
Zum Zweiten folge ich nur Links zu Seiten die ich vorher noch nicht besucht habe. Als Beispiel nehme ich an, dass die restlichen 225 Links alle zu verschiedenen Seiten gehen. Diese Zahl, die Anzahl aller _neuen_ (einzigartigen) Links, notiere ich mir auch per Linklevel (und urspruenglichen Wikipediabetrag).

Auf Linklevel 2 habe ich nun 225 Seiten. Ich nehme wieder 10 Links pro Seite (im Durchschnitt) an. Das macht dann 2250 _totale_ Links auf Linklevel 2. Desweiteren nehme ich an, dass da 50 Selbsreferenzen dabei sind. Auszerdem sehe ich, dass fuer dieses Fantasiebeispiel im Schnitt jede Seite auf Linklevel 2 eine Seite zitiert, die ich schonmal auf Linklevel 1 besucht habe. Das waeren also 225 „Zurueckverlinkungen“, die NICHT zum Urpsrung gehen (und somit keine Selbstreferenzen sind) denen ich aber ebenso nicht folge, damit ich nicht in Schleifen gerate. Die Anzahl der _neuen_ (einzigartigen) Links ist also: 2250 Links – 50 Selbstreferenzen – 225 Zurueckverlinkungen = 1975 Links

Auf Linklevel 3 habe ich nun 1975 Seite und das Spiel geht immer weiter, so lange, bis es keine Verlinkungen (oder Ausgaenge) mehr, zu Seiten auf denen ich noch nicht war, gibt .

In Tabellenform sieht das Fantasiebeispiel so aus:

Das Ganze geschieht nun fuer alle (beinahe) 6 Millionen Wikipediatitel und wie die Verteilung dieser Grøszen pro Linklevel aussieht ist das, was mich interessiert. Aber das soll genug sein fuer heute.

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.

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.

Endlich kann ich ueber diesen Geniestreich reden … aber ich greife vor.

Beim vorletzten Mal „mathematisierte“ ich das Kevin-Bacon-Problem. Das war prinzipiell løsbar, aber ich stellte beim letzten Mal fest, dass es aufgrund von Speicherplatzmangel technisch in der gegebenen Form praktisch nicht løsbar war.

Ich redete beim letzten Mal viel ueber die „Betriebskosten“ (in Form von Speicher) die Datenobjekte haben. Dabei konzentrierte ich mich auf Wortobjekte. Fuer jedes Wort habe ich „Betriebskosten“ von 49 Bytes plus der Speicherbedarf der „Nutzlast“ von 1 Byte pro Buchstabe. Die „Nutzlast“ ist von der Laenge des Wortes abhaengig.

Ich erwaehnte auch, dass eine Zahl keine Laenge hat. Cool ist nun, dass der Gesamtspeicherbedarf („Betriebskosten“ + „Nutzlast“) einer ganzen Zahl auf meinem Rechner unter Python 3.7.3 deutlich kleiner ist als fuer Wørter; naemlich nur 28 Bytes. Und das ist unabhaengig davon, wie grosz die Zahl wird! … Naja, es gibt natuerlich Ausnahmen. Die Null braucht nur 24 Bytes und ganz grosze Zahlen (genauer gesagt ab 1,073,741,824) brauchen dann schon 32 Byte und irgendwann werden die Zahlen so grosz, dass die 36 Byte brauchen usw. Aber das ist hier nicht von Interesse, da ich nicht in diese groszen Bereiche komme mit dem gegebenen Problem.

Und hier kommt jetzt die geniale Idee: Ich bildete jeden Titel auf eine nicht negative ganze Zahl (inklusive der Null) ab. Wenn ein Titel von einem anderen Titel zitiert wird, dann erstatte ich diesen mit der gegebenen Zahl. Die Reihenfolge spielt dabei ueberhaupt keine Rolle. Diese Abbildung ist bijektiv und die Abbildungsvorschrift (einfach eine lange Tabelle welcher Titel welcher Zahl zugeordnet ist) merke ich mir natuerlich, falls ich spaeter eine spezfische Linkkette nachverfolgen will.

Durch die Abbildung auf nicht negative ganze Zahlen verringerte sich der Speicherbedarf meiner 5,798,312 Titel und 165,913,569 Links von ehedem 11 GB auf 4,807,932,668 als ca. 4.8 GB … Huzzah!

Damit habe ich das Kevin-Bacon-Problem nicht nur mathematisiert, sondern auch „verzahlt“. Das coole ist, dass sich dabei der Informationsinhalt, bzgl. der Informationen, an denen ich interessiert war (!), nicht veraenderte. Cool wa!

Zur Veranschaulichung hier das dritte Beispiel vom vorletzten Mal in der neuen Darstellung:

Mit dem Bild erkennt man besser, dass sich der untersuchte Informationsinhalt nicht aendert. Ob Apfel jetzt auf Kuchen zeigt oder 23 auf 5 tut nix zur Sache, solange im gesamten Netzwerk 23 immer mit Apfel und 5 immer mit Kuchen assoziiert ist.

Zum Problem der „Betriebskosten“ der Wortobjekte kamen beim letzen Mal die Betriebskosten der „Waggons“ (oder Ueberstrukturen) in denen diese aufbewahrt wurden. Ein Problem wurde es deshalb, weil jeder Titel einen solchen „Waggon“ hat. Ganz spezifisch waren diese „Waggons“ sogenannte Sets und deren „Betriebskosten“ waren abhaengig von der Anzahl der darin enthaltenen Elemente.
Das Gute ist nun, dass es noch andere Arten von „Waggons“ gibt. Fuer den Verwendungszweck hier ist nur wichtig, dass diese die „Aufbewahrungsbox“ aller zu einem Titel gehørenden Links sind, damit nix durcheinander kommt. Dafuer brauche ich kein Set, wie beim letzten Mal erwaehnt, sondern es reicht ein sogenannten Tupel.
Waehrend man mit Sets urst viel machen kann (bspw. Elemente heraus nehmen oder dazu packen, oder Mengenoperationen mit anderen Sets ausfuehren) kann man mit Tuples (fast) nix machen. Das ist ein unveraenderbarer „Kasten“ fuer meine Links (die ja nun Zahlen sind). Und weil man damit so wenig machen kann, betragen die „Betriebskosten“ eines leeren Tuples nur 56 Bytes und die steigen linear an (diesmal wirklich) mit 8 Byte pro neuem Element.

Wie beim letzten Mal brauche ich nun das Produkt aus der Verteilung der Links pro Titel und dem tatsaechlichen Speicherbedarf der Tuples. Zum Vergleich habe ich in dieses Diagramm das Resultat dieser Rechnung und der gleichen Rechnung vom letzten Mal dargestellt.

So ein Mist, da aendert sich ja nicht viel … ach nee! Die Skala der linken Ordinate ist eine ganze Grøszenordnung (!) kleiner als die Skala der rechten Ordinate … voll krass!

Der Gesamtspeicherbedarf betraegt damit fuer alle „Tuple-Waggons“ keine 11 GB wie bei den Sets, sondern nur 1,605,627,528 Bytes also ca. 1.6 GB.
Da kommen dann noch die ca. 300 MB fuer die oberste Struktur hinzu, welches alle „Waggons“ den richtigen Titeln zuordnen (die „Lokomtive“ vom letzten Mal bzw. das „Dictionary“). Insgesamt benøtige ich mit diesen Modifikationen dann nur noch 6,7 GB.

JIPPIE! So viel Speicher habe ich und deswegen soll das fuer heute reichen. So viel sei nur noch gesagt: hier hingeschrieben hørt sich der Schritt der Abbildung der Titel auf ganze Zahlen voll logisch an. Deswegen war dieser Geniestreich als solcher auch zunaechst unbemerkt. Ich wollte ja erstmal nur das Speicherplatzproblem løsen. Aber letztlich erlaubte mir erst dieser Schritt die (effiziente!) technische Implementierung der Løsung des eigentlichen Problems. Dazu Bedarf es allerdings noch ein paar weiterer (Achtung: Spoiler) „Transformationen“.

Beim letzten Mal beschrieb ich die Umwandlung des urspruenglichen Sprachproblems in ein mathematisches Problem. Damit kann man prinzipiell so wie’s ist (von Apfel zu Kuchen zu Mehl usw.) an die Sache heran gehen.
Wir sprechen hier aber von fast 6 Millionen Knoten (Wikipediatiteln) und mehr als 181-Millionen Verbindungen dazwischen in diesem Netzwerk. Und fuer jeden Knoten muss ich die Gesamtheit der Verbindungen „abschreiten“. Dabei lief ich in ein albekanntes Problem: nicht genug Speicher! Aber der Reihe nach.

Vor ein paar Monden hørte ich mit der Saeuberung der Rohdaten auf und es blieben noch …

[…] 5,798,312 Wikipediaseiten auf denen insgesamt 165,913,569 Links erscheinen […]

… zurueck.

Ich schrieb auch, dass der Speicherbedarf dieser Daten von ehemals ueber 70 GB (die gesamte Wikipedia) auf 4.1 GB verringert wurde. Ich hatte das auf 61 Dateien verteilt und die bin ich fuer die bereits vorgestellten Untersuchungen immer der Reihe nach durchgegangen (denn da hat mich ja das Netzwerk an sich nicht interessiert).
Das Komische war nun, dass das eigentlich alles in den Speicher meines Laptops passen sollte … aber irgendwie kam dieser nicht zurecht, wenn ich versuchte mehr als 10 dieser Dateien gleichzeitig zu laden.

Merkwuerdig … wie sieht das denn eigentlich im Speicher aus?
Nunja, erstmal dachte ich ganz einfach, dass die Titel der Seiten Buchstabenketten (allgemeiner: Zeichenketten) mit einer bestimmten Laenge sind. Dito bzgl. der Links „hinter“ jedem Titel.
Im Wesentlichen braucht ein Buchstabe im Speicher 1 Byte … jaja, Sonderzeichen brauchen mglw. mehr, aber ich sollte davon nicht soooo viele haben … Der Speicherbedarf der Titel sollte also das Integral ueber die hier gezeigte Verteilung sein: 117,194,976 Bytes also ca. 117 MB.
Die Verteilung der Laengen der Links ist sehr aehnlich:

In den nicht normierten Daten ist die Amplitude der Verteilung der Links natuerlich viel grøszer und diese muss natuerlich fuer das Integral genommen werden.
Nebenbemerkung: das kleine „Uebergewicht“ bzw. „Untergewicht“ links bzw. rechts vom Maximum ist sicherlich dadurch zu erklaeren, dass „prominente“ (also oft zitierte) Seiten einen kurzen und knackigen Titel haben — siehe hier. Der Unterschied ist zwar zu sehen, aber nicht so massiv (oder unerwartet), sodass ich mich da nicht weiter fuer interessiere. Insb. auch deswegen nicht, weil die gegebene Erklaerung (mit den Beispielen der meistzitierten Seiten) durchaus plausibel klingt.

Fuer den Speicherbedarf aller in den Links enthaltenen Zeichen errechnete ich nun: 2,898,076,329 also ca. 2.9 GB.

Na sowas! Meine simplen Ueberlegungen løsen die Merkwuerdigkeit nicht auf!
Des Raetsels Løsung ist zweigeteilt und ich gebe zu, dass das ueber das Anfaengerprogrammiererniveau hinaus geht (wenn auch nicht sehr weit). Aber dafuer muss ich etwas ausholen. Das wiederum handelt im vorbeigehen auch gleich etwas ab, was beim naechsten Mal total hilft :) .

Nehmen wir die Zeichenkette „gerader Strich mit kurzer Kappe, zwei mal zwei nach links offene Halbkreise, schraeger Strich mit Vordach“ — oder in kurz 1337.
Ich nehme 1337 mit Absicht. Zum Einen ist es natuerlich die Zahl Eintausenddreihundertsiebenundreiszig. Dann es aber auch das bekannteste Beispiel fuer Leetspeak und wird eben auch direkt als „LEET“ — also ein Wort — interpretiert.
Ein und die selbe (!) Zeichenkette hat also zwei unterschiedliche Bedeutungen. So wir denn von diesen Unterschieden wissen, so ist das fuer uns Menschen i.A. kein Problem 1337 kontextabhaengig richtig zu interpretieren. Wenn ich also sage packe bei 1337 nochmal 1337 ran, so ist das eine Addition im Falle der Zahl und das Ergebnis wird 2274 bzw. wird is im Falle des Wortes 13371337 (also LEETLEET).

Damit bin ich bei einem weiteren wichtigen Aspekt: Operationen.
Abhaengig von der Bedeutung die die Zeichenkette hat, kann man damit unterschiedliche Operationen ausfuehren oder gleiche Operationen, die aber unterschiedliche Ergebnisse haben. Oben erwaehnte ich die Addition. Eine andere Operation waere „Sag mir mal die Laenge von dem was ich gerade vor mir habe“.
Bei LEET entspricht die Laenge natuerlich der Anzahl der Zeichen und ist somit vier. Aber selbst wenn eine Zahl viele Zahlzeichen enthaelt, so ist die Laenge einer Zahl doch immer eins! Das ist besser zu verstehen, wenn man rømische Zahlsymbole nimmt, denn da sind 10, 50, 100, 500 und 1000 nur ein Symbol. Noch cooler ist das cistercianische Zahlsystem, welches bis 9999 immer nur ein Symbol braucht.

Das alles weisz man „automatisch“ als Mensch, aber dem Computer muss man zu jeder Zeichenkette sagen, was die jetzt eigentlich fuer eine Bedeutung hat, damit die richtigen Operationen drauf ausgefuehrt werden. Und hat eine Zeichenkette erstmal eine Bedeutung, so aendert die sich niemals … … … jaja, ich weisz, dass es da Spezialfaelle gibt, die Ausnahmen zu dieser Aussage sind … aber mir geht’s hier darum, dass man einem Computer explizit und jedes Mal sagen muss, womit dieser eigentlich gerade arbeitet.
Das ganze geht natuerlich noch viel tiefer direkt rein in die Innereien des Computers. Denn eine Zahl ist im Speicher ganz anders dargestellt als ein Wort.

Worauf ich hinaus will ist das Folgende. Jedes Objekt im Program (also meine Zeichenketten) hat „Betriebskosten“ in Form von Speicherplatzbedarf wo eben die Bedeutung des besagten Objektes abgelegt ist. Diese „Betriebskosten“ beinhalten das was ich oben sagte, damit der Computer weisz, wie mit besagten Objekten umzugehen ist. Interessiert bin ich aber nur an der „Ladung“ eines Objektes; also der Zahl oder dem Wort an sich. Diese „Ladung“ kommt zu den „Betriebskosten“ hinzu.

Um die „Betriebskosten“ kommt man niemals drumherum und es gibt nun zwei Møglichkeiten, wie man das handhaben kann. Zentral oder dezentral.
Zentral bedeutet, dass man eine gewisse Menge Speicherplatz reserviert und ranschreibt welche Bedeutung alle Objekte die sich darin befinden haben. Dann muss man das nur einmal sagen und die „Betriebskosten“ fallen nur einmal an.
Dezentral bedeutet, dass man das an jedes einzelne Objekt ranschreibt. Dann fallen die „Betriebskosten“ fuer jedes Objekt an. Warum sollte man das machen? Naja, dafuer gibt es technische Gruende, und mindestens einen eher philosophischen Grund: um dem Menschen der das Programm schreibt die Arbeit zu erleichtern. Denn das ist genau das was Python macht. Speicher- und Objektmanagement sind Dinge, die man in anderen Programmiersprachen explizit machen muss. Ich finde das durchaus interessant, aber ich gebe zu, dass es vom eigentlichen Programmieren (sich logische Strukturen ueberlegen, die ein gewisses Problem løsen) abhaelt, wenn man das „Inventar“ immer „sortieren und sauber halten“ muss.

Und das ist das was ueber das Anfaengerprogrammiererniveau zumindest unter Python hinausgeht. „Anfaengerprogrammiererniveau“ deswegen, weil Python heutzutage nunmal die Sprache ist, in der mglw. die allermeisten Leute anfangen zu programmieren. Und die fangen damit an, eben weil da solche Sachen im Hintergrund passieren  und vom Menschen der den Code schreibt weg gehalten werden.
Es ist aber natuerlich auch Grund, warum Python nicht fuer die Programmierung wirklich groszer Programme (wie bspw. Betriebssysteme) benutzt wird. Hat halt alles seine Vor- und Nachteile.

Soweit dazu. Den Speicherbedarf der „Ladung“ habe ich oben berechnet. Aber wie grosz sind denn nun die „Betriebskosten“ pro Zeichenkette? Nun ja, das ist kompliziert und nicht nur von der Architektur des Rechners und Betriebssystems, sondern auch der benutzten Inkarnation der Programmiersprache abhaengig. Unter Python 3.7.3 auf meinem Rechner belaufen sich besagte „Betriebskosten“ von Zeichenketten auf 49 Byte pro Objekt. (Unter Python 2.7.16 sind es uebrigens nur 37 Byte).
Da wir 5,798,312 Wikipediaseiten und 165,913,569 Links haben kommen zu den obigen ca. 3 GB also nochmals 8,413,882,169 Byte hinzu. Eigentlich ein bisschen mehr, weil Sonderzeichen høhere „Betriebskosten“ haben, aber in der Summe sind das dann ungefaehr 11 GB.

Mhm … 11 GB das wird zwar knapp, aber so viel habe ich eigentlich. Warum kommt der Computer aber schon nicht mehr klar, wenn ich nur 10 Dateien eingelesen habe?
Ohne lange Rede: die Links sind in Sets (das ist sowas wie ’ne Liste ohne doppelte Objekte) angeordnet und davon habe ich natuerlich pro Titel eins. Insgesamt ist dann alles in einem einem sogenannten „Dictionary“ sortiert, damit ich zu jedem Titel leicht die zugehørigen Links finde (wie eben in einem Lexikon). Solche uebergeordneten Strukturen haben natuerlich auch Betriebskosten zusaetzlich (!) zu denen der einzelnen Elemente die in diesen Strukturen „aufbewahrt“ werden. Aber anders als bei den „primitiven“ Objekten wie oben beschrieben steigen die Betriebskosten in Abhaengigkeit von der Anzahl der Elemente die sich darin befinden. Klar, der gesamte Speicherbedarf eines Wortes ist abhaengig von der Anzahl der Buchstaben, aber das ist die „Nutzlast“. Die „Betriebskosten“ des Wortes sind davon unabhaengig. Und das ist bei den uebergeordneten Strukturen anders (weil die komplizierter sind und auch kompliziertere Operationen erlauben).

Zur besseren Veranschaulichung stelle man sich einen Gueterzug der Farbe transportiert vor. Alle Links die zu einem Titel gehøren entsprechen einer Farbe. Besagte Sets sind dann ein Tankwaggon, die jeweils nur eine Farbe enthalten. Wenn ich mehrere Tankwaggons habe, dann fallen die Betriebskosten (Wartung, oder Versicherung) pro Stueck an. Habe ich weniger Farbe, benutze ich einen kleineren Tankwagon, der geringere Kosten hat. Die Lokomotive (welche wiederum Betriebskosten hat) nun zieht alle Tankwaggons. Habe ich nur ein paar, benutze ich eine kleinere Lokomotive (mit geringeren Kosten), als wenn der Gueterzug so lang ist wie in Sibirien.

Und der Speicherbedarf dieser uebergeordneten Strukturen entwickelt sich selbst ohne die „Nutzlast“ dramatisch! Die „Waggons“ in denen sich die Links befinden benøtigen in ihrer kleinsten Form (also ohne Nutzlast, wenn ein Titel keine Links enthaelt) bereits 224 Bytes. Bei den ca. 6 Millionen Titeln macht das also mindestens (!) nochmal 1.3 GB. Und nun kommen wir in Regionen, wo mir der Speicher ausgeht.

Aber eigentlich braucht die Anordnung in Sets deutlich mehr, denn beim Maximum der Verteilung bzgl. der Anzahl der Links pro Titel, beansprucht ein Set bereits 736 Bytes Speicherbedarf an „Betriebskosten“. 736 Bytes braucht ein Set auch dann, wenn es 18 Elemente hat, aber ab 19 Elementen braucht es 2272 Bytes. Insgesamt sieht das dann so aus:

Puuuuh … das geht linear, nochmal Glueck gehabt … … … Oopsie, das sind ja doppeltlogarithmische Achsen! … … … Ach du meine Guete! Der Anstieg ist ja positiv! Damit wird ja der Exponent des maechtigen Gesetzes grøszer Null!

Lange Rede kurer Sinn: die vormals betrachtete, oben verlinkte, Verteilung der Anzahl der Links fuer alle Titel muss mit dem hier dargestellten Speicherbedarf _multipliziert_ werden. Das sieht dann so aus:

Mist! Die Ordinate ist linear und in Megabyte.

Erst jetzt ergibt das Integral unter dieser Kurve den tatsaechlichen Speicherbedarf dieser Ueberstruktur von Sets welche besagte Links enthalten: 10,962,695,936 Byte also ca. 11 GB die zu den obigen 11 GB noch dazu kommen. So viel Speicher habe ich nicht. Die „Lokomotive“ (das „Dictionary“), also die oberste Ordnungsstruktur, braucht dann bei ca. 6 Millionen Elementen nochmals 300 MB. Aber das faellt dann kaum mehr ins Gewicht.

Ich fasse zusammen. Der Speicherbedarf der eigentlichen „Buchstaben“ aller Titel und Links betraegt nur 3 GB. Aber die Verwaltung all dieser Buchstabenobjekte verursacht (in Python) „Betriebskosten“ von 8 GB. Die Strukturen in der die ganzen Objekte nun zusammengefasst sind verursacht dann nochmals „Betriebskosten“ in Høhe von weiteren 11 GB.
Kein Wunder, dass mein Computer da keine Lust drauf hat.

Wie ich dieses Problem løste stelle ich beim naechsten Mal vor. Denn die Løsung ist echt cool (weil so elegant) und erlaubte mir ueberhaupt erst das Gesamtproblem (die Erforschung des Linknetzwerkes) derart umzuformulieren, dass ein Computer das (schnell) løsen konnte.

Ach so … wenn ich hier 22 GB zusammenrechne, wie komme ich denn auf die 4.1 GB, die ich ganz oben erwaehne. Nun ja, wenn ich das alles auf der Festplatte speichere, dann wird die Struktur serialisiert. Dabei werden strukturierte Daten in einen seriellen Datenstrom „umgewandelt“ fuer die Speicherung. Darauf kann ich dann natuerlich nicht arbeiten.
Ich kønnte mir denken, dass viele von den „Betriebskosten“ gespart werden kønnten, indem man einen Teil des seriellen Datenstroms bspw. als „ab hier keine Zahlen sondern nur Wørter“ definiert (anstatt das fuer jedes Wort einzeln zu machen). Wenn das wieder zurueck „uebersetzt“ (de-serialisiert) wird, dann sieht der Algorithmus das und „baut“ daraus die richtigen Wortobjekte.
Aber das sollte alles als Spekulation gesehen werden, denn ich habe eigentlich gar keine Ahnung was da wirklich passiert.

Ausgehend von Kevin Bacon war der urspruengliche Plan das Linknetzwerk der Wikipedia zu untersuchen.
Dies ist im Grunde ein universelles (im Sinne von Universum) Problem — Die Beziehung von Informationen zueinander. Das habe ich dann gleich erstmal massiv auf Erdwissen eingeschraenkt welches sich in der (westlichen) Wikipedia befindet. Damit konnte ich das universelle Problem auf ein Sprachproblem reduzieren.
Das war aber immer noch zu viel, denn die Texte enthalten unheimlich viel Information, die im Sinne der Fragestellung „unbrauchbar“ ist. All das habe ich weggeschmissen und zurueck blieben die Titel von Wikipediaseiten und welche anderen Wikipediaseiten diese zitieren.

Das Wichtige an einem solchen Netzwerk sind nun aber nicht die Anzahl der „Knotenpunkte“. Ein Elefant hat deutlich mehr Neuronen als ein Mensch und dennoch sind es Fuszstapfen des Homo Sapiens auf dem Mond.
Nebenbemerkung: Gehirne sind urst krass kompliziert; bspw. haben grøszere Tiere im Allgemeinen auch grøszere Neuronen (die brauchen also mehr Platz). Und auch die Struktur des Gehirns (die Runzeln) oder in welchem Teil des Gehirns sich die Neuronen befinden ist wichtig. Und ich tu mal so, als ob es Vøgel nicht gibt.

Ganz generell ist also nicht die Menge der Knoten ausschlaggebend, sondern wie viele Verbindungen es zwischen den Knoten gibt. Selbst wenn ueber das Netzwerk jeder Punkt erreicht werden kann, so dauert es laenger, je mehr „Zwischenstops“ bei anderen Knoten man unterwegs einlegen muss. Oder anders gesagt: wer schaut sich schon die zweit oder gar dritte Seite mit den Sucherergebnissen an?
Diese Anzahl der Schritte bezeichnete ich am Anfang der Serie als „Linklevel“.

Zur Veranschaulichung nehme man dieses ausgedachte Beispiel:

Von Apfel (Linklevel 0, da das der Ursprung ist) komme ich direkt zu Baum, Frucht und Kuchen. Von Apfel aus gesehen liegen diese drei also auf Linklevel 1. Im Beispiel geht das Netzwerk bei Frucht nicht weiter. Von Baum aber geht es zu Borkenkaefer und Holz. Diese Beiden liegen von Apfel aus gesehen auf Linklevel 2 und von Baum aus gesehen auf Linklevel 1. Letzteres ist (erstmal) nicht von Interesse, denn hier interessiert uns nur Apfel und Baum wird separat untersucht.
Kuchen verweist nun zurueck auf Apfel. Das ist das, was ich spaeter „Selbstreferenz“ nennen werde, denn das ist ja prinzipiell auch von Interesse: wie entwickelt sich die Selbstreferenz je „weiter“ man weg ist vom Urpsrung? Natuerlich liegt fuer Kuchen der Apfel ebenso auf Linklevel 1 und via Apfel erreicht man dann von Kuchen aus die anderen Elemente (nur jeweils ein Linklevel høher). Auch dies wird in der Analyse separat betrachtet; ich erwaehne das nur, weil das aus dem Beispiel „heraus faellt“.

In einem zweiten Beispiel kommt Kirsche hinzu:

Das ist das Gleiche wie bei Apfel, nur von Kirsche aus gesehen ist Apfel auf dem selben Linklevel wie Holz (Linklevel 2) denn diese beiden „kommunizieren“ via den Knoten Kuchen. Umgekehrt gilt das natuerlich genauso.
Ich erwaehne dies, weil das Linknetzwerk absolut das Selbe (!) ist, trotzdem ein anderer Knoten als Ursprung genommen wurde.

Jetzt noch ein drittes Beispiel:

Von Apfel komme ich via Kuchen, Mehl und Weizen zu Pflanze. Von Pflanze komme ich dann zurueck zu Baum. Damit wuerde Baum (von Apfel aus gesehen) auf Linklevel 1 und Linklevel 5 liegen. Das wird aber ignoriert, weil ich sonst in Schleifen gerate, aus denen ich nicht heraus komme. Dadurch, dass Baum bereits auf Linklevel 1 „besprochen“ wurde ist das auch gerechtfertigt denke ich.

Ich habe das aus zwei Gruenden (nochmals) so ausfuehrlich beschrieben. Zum Einen, um nach all den vorhergehenden Analysen und Diagrammen das urspruengliche Problem wieder in Erinnerung zu rufen. Zum Anderen sieht man hieran, dass ich das Sprachproblem „mathematisieren“ konnte. Denn wie man an den Beispielen sieht, faellt das Kevin-Bacon-Problem in das Gebiet der Graphentheorie.
Von Letzterer habe ich keine Ahnung. Das hindert mich aber nicht daran, ganz praktisch und pragmatisch an die Sache heran zu gehen und eine Løsung zu finden, die gut genug fuer das ist, was ich eigentlich wissen will.

Damit genug fuer heute.