{"id":11375,"date":"2022-01-13T13:37:45","date_gmt":"2022-01-13T11:37:45","guid":{"rendered":"http:\/\/www.soeren-in-norwegen.net\/blog\/?p=11375"},"modified":"2021-09-01T11:32:46","modified_gmt":"2021-09-01T09:32:46","slug":"kevin-bacon-xiii-size-matters","status":"publish","type":"post","link":"http:\/\/www.soeren-in-norwegen.net\/blog\/2022\/01\/kevin-bacon-xiii-size-matters\/","title":{"rendered":"Kevin Bacon – XIII – Size Matters!"},"content":{"rendered":"

Beim letzten Mal<\/a> beschrieb ich die Umwandlung des urspruenglichen Sprachproblems in ein mathematisches Problem. Damit kann man prinzipiell so wie’s ist (von Apfel<\/em> zu Kuchen<\/em> zu Mehl<\/em> usw.) an die Sache heran gehen.
\nWir 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.<\/p>\n

Vor ein paar Monden<\/a> h\u00f8rte ich mit der Saeuberung der Rohdaten auf und es blieben noch \u2026<\/p>\n

[\u2026] 5,798,312 Wikipediaseiten auf denen insgesamt 165,913,569 Links erscheinen [\u2026]<\/p><\/blockquote>\n

\u2026 zurueck.<\/p>\n

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).
\nDas Komische war nun, dass das eigentlich alles in den Speicher meines Laptops passen sollte \u2026 aber irgendwie kam dieser nicht zurecht, wenn ich versuchte mehr als 10 dieser Dateien gleichzeitig zu laden.<\/p>\n

Merkwuerdig \u2026 wie sieht das denn eigentlich im Speicher aus?
\nNunja, 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.
\nIm Wesentlichen braucht ein Buchstabe im Speicher 1 Byte \u2026 jaja, Sonderzeichen brauchen mglw. mehr, aber ich sollte davon nicht soooo viele haben \u2026 Der Speicherbedarf der Titel sollte also das Integral ueber die hier gezeigte Verteilung<\/a> sein: 117,194,976 Bytes also ca. 117 MB.
\nDie Verteilung der Laengen der Links ist sehr aehnlich:<\/p>\n

\"\"<\/a><\/p>\n

In den nicht normierten Daten ist die Amplitude der Verteilung der Links natuerlich viel gr\u00f8szer und diese muss natuerlich fuer das Integral genommen werden.
\nNebenbemerkung: 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<\/a>. 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.<\/p>\n

Fuer den Speicherbedarf aller in den Links enthaltenen Zeichen errechnete ich nun: 2,898,076,329 also ca. 2.9 GB.<\/p>\n

Na sowas! Meine simplen Ueberlegungen l\u00f8sen die Merkwuerdigkeit nicht auf!
\nDes Raetsels L\u00f8sung 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 :) .<\/p>\n

Nehmen wir die Zeichenkette „gerader Strich mit kurzer Kappe, zwei mal zwei nach links offene Halbkreise, schraeger Strich mit Vordach“ — oder in kurz 1337.
\nIch nehme 1337 mit Absicht. Zum Einen ist es natuerlich die Zahl Eintausenddreihundertsiebenundreiszig. Dann es aber auch das bekannteste Beispiel fuer Leetspeak<\/a> und wird eben auch direkt als „LEET“ — also ein Wort — interpretiert.
\nEin 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).<\/p>\n

Damit bin ich bei einem weiteren wichtigen Aspekt: Operationen.
\nAbhaengig 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“.
\nBei 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\u00f8mische Zahlsymbole nimmt, denn da sind 10, 50, 100, 500 und 1000 nur ein Symbol. Noch cooler ist das cistercianische Zahlsystem<\/a>, welches bis 9999 immer nur ein Symbol braucht.<\/p>\n

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 \u2026 \u2026 \u2026 jaja, ich weisz, dass es da Spezialfaelle gibt, die Ausnahmen zu dieser Aussage sind \u2026 aber mir geht’s hier darum, dass man einem Computer explizit und jedes Mal sagen muss, womit dieser eigentlich gerade arbeitet.
\nDas 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.<\/p>\n

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.<\/p>\n

Um die „Betriebskosten“ kommt man niemals drumherum und es gibt nun zwei M\u00f8glichkeiten, wie man das handhaben kann. Zentral oder dezentral.
\nZentral 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.
\nDezentral 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\u00f8sen) abhaelt, wenn man das „Inventar“ immer „sortieren und sauber halten“ muss.<\/p>\n

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\u00a0 und vom Menschen der den Code schreibt weg gehalten werden.
\nEs 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.<\/p>\n

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).
\nDa 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\u00f8here „Betriebskosten“ haben, aber in der Summe sind das dann ungefaehr 11 GB.<\/p>\n

Mhm \u2026 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?
\nOhne 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\u00f8rigen 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).<\/p>\n

Zur besseren Veranschaulichung stelle man sich einen Gueterzug der Farbe transportiert vor. Alle Links die zu einem Titel geh\u00f8ren 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<\/a>.<\/p>\n

Und der Speicherbedarf dieser uebergeordneten Strukturen entwickelt sich selbst ohne die „Nutzlast“ dramatisch! Die „Waggons“ in denen sich die Links befinden ben\u00f8tigen 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.<\/p>\n

Aber eigentlich braucht die Anordnung in Sets deutlich mehr, denn beim Maximum der Verteilung bzgl. der Anzahl der Links pro Titel<\/a>, 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:<\/p>\n

\"\"<\/a><\/p>\n

Puuuuh \u2026 das geht linear, nochmal Glueck gehabt \u2026 \u2026 \u2026 Oopsie, das sind ja doppeltlogarithmische Achsen<\/a>! \u2026 \u2026 \u2026 Ach du meine Guete! Der Anstieg ist ja positiv! Damit wird ja der Exponent des maechtigen Gesetzes gr\u00f8szer Null!<\/p>\n

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:<\/p>\n

\"\"<\/a><\/p>\n

Mist! Die Ordinate ist linear und in Megabyte.<\/p>\n

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.<\/p>\n

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\u00f8he von weiteren 11 GB.
\nKein Wunder, dass mein Computer da keine Lust drauf hat.<\/p>\n

Wie ich dieses Problem l\u00f8ste stelle ich beim naechsten Mal vor. Denn die L\u00f8sung 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\u00f8sen konnte.<\/p>\n

Ach so \u2026 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<\/a>. Dabei werden strukturierte Daten in einen seriellen Datenstrom „umgewandelt“ fuer die Speicherung. Darauf kann ich dann natuerlich nicht arbeiten.
\nIch k\u00f8nnte mir denken, dass viele von den „Betriebskosten“ gespart werden k\u00f8nnten, indem man einen Teil des seriellen Datenstroms bspw. als „ab hier keine Zahlen sondern nur W\u00f8rter“ 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.
\nAber das sollte alles als Spekulation gesehen werden, denn ich habe eigentlich gar keine Ahnung was da wirklich passiert.<\/p>\n","protected":false},"excerpt":{"rendered":"

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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/posts\/11375"}],"collection":[{"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/comments?post=11375"}],"version-history":[{"count":9,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/posts\/11375\/revisions"}],"predecessor-version":[{"id":11397,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/posts\/11375\/revisions\/11397"}],"wp:attachment":[{"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/media?parent=11375"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/categories?post=11375"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/tags?post=11375"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}