Mitglied seit: 06.04.2005
Forenbeiträge: 687
Besuche: 668
Guten Tag
Als Folge der Diskussion in [1] habe ich mir Gedanken ueber einen effizienteren Algorithmus gemacht.
Da es in dem verlinkten Thread zu sehr Offtopic waere, habe ich hier einen neuen Thread gestartet, wo nur ueber das Problem der Effizienz des eingesetzten Algorithmus diskutiert werden sollte, um Marc von Diskussionen ueber zu hohe CPU Belastung mit seinem Betreiber zu ersparen ;} .
Eigentlich ist das Problem ja recht trivial, und es stellt sich die Frage, weshalb squeez hierfuer einen eigenen Thread startet. Nun, die Bewertung eines Algorithmus ist ein eigenstaendiges Gebiet der Informatik. Und, diese Aufgabe ist ein perfektes Beispiel fuer diese Disziplin.
Hier die Originalimplementierung:
Ich habe hier ein paar Ideen im Hinterkopf, wie die CPU Belastung massiv reduziert werden kann.
Hier mein Vorschlag:
Das Problem betrifft die Berechnung der Zufallswerte, welche je nach Implementierung recht aufwaendig ausfallen kann.
Da der Inhalt eines jeden Arrays einmalig ist, und keiner der Werte mehrfach vorkommt, ist das Array bereits zufaellig sortiert. Es ist deshalb unsinnig, jedes mal noch einen zufaelligen (und damit rechenaufwaendigen) Index zu berechnen. Stattdessen kann einfach jedem Array ein inkremenierender Index zugeordnet werden, welcher jeweils inkrementierend bei jedem Zugriff hochgezaehlt wird. Der Umbruch erfolgt durch modulo Berechnung, so dass kein Ueberlauf entstehen kann.
Wichtig ist, dass die Auftrittswahrscheinlichkeiten nicht veraendert werden. Dies kann dadurch erzielt werden, in dem die Groesse eines jeden Arrays seiner naechsten Primzahl entspricht.
Nun beschraenkt sich die notwendige CPU Belastung auf das inkrementieren eines integers und der modulo "Umbrechung". Man drueckt dies in Form von O(1) aus. Die Berechnung einer Zufallszahl wuerde einem Polynom entsprechen, von welchem der Grad unbekannt ist. Also die Form O(x^m) annehmen kann, wobei m von der Implementierung abhaengt (und im besten Fall 0 entspricht, wohl aber >=1 sein wird).
So, ich bitte um eine Diskussion, wie man selbst dieses Verfahren noch beschleunigen koennte.
Marco
[1] http://www.computec.ch/forum_viewtopic.php?14.9715.10
[ Bearbeitet ]
Als Folge der Diskussion in [1] habe ich mir Gedanken ueber einen effizienteren Algorithmus gemacht.
Da es in dem verlinkten Thread zu sehr Offtopic waere, habe ich hier einen neuen Thread gestartet, wo nur ueber das Problem der Effizienz des eingesetzten Algorithmus diskutiert werden sollte, um Marc von Diskussionen ueber zu hohe CPU Belastung mit seinem Betreiber zu ersparen ;} .
Eigentlich ist das Problem ja recht trivial, und es stellt sich die Frage, weshalb squeez hierfuer einen eigenen Thread startet. Nun, die Bewertung eines Algorithmus ist ein eigenstaendiges Gebiet der Informatik. Und, diese Aufgabe ist ein perfektes Beispiel fuer diese Disziplin.
Hier die Originalimplementierung:
1. Ich bastle mir vier eindimensionale Arrays $aarray, $barray, $carray und $carray.
2. Diese werden mit Begriffen abgefuellt. $aarray = array("", "Passive", ...);
3. Zu jedem Array wird eine Zufallszahl durch $arnd = rand(0, count($aarray)-1); berechnet, die eine Referenzierung des entsprechenden Worts mit $aword = $aarray[$arnd]; zulassen soll.
4. Die Chancen werden berechnet $chances = (count($aarray)-1) * (count($barray)-1) * (count($carray)-1) * (count($darray)-1);
5. Und die Wortkette in der Form "$aword $bword $cword $dword" ausgegeben.
Ich habe hier ein paar Ideen im Hinterkopf, wie die CPU Belastung massiv reduziert werden kann.
Hier mein Vorschlag:
Das Problem betrifft die Berechnung der Zufallswerte, welche je nach Implementierung recht aufwaendig ausfallen kann.
Da der Inhalt eines jeden Arrays einmalig ist, und keiner der Werte mehrfach vorkommt, ist das Array bereits zufaellig sortiert. Es ist deshalb unsinnig, jedes mal noch einen zufaelligen (und damit rechenaufwaendigen) Index zu berechnen. Stattdessen kann einfach jedem Array ein inkremenierender Index zugeordnet werden, welcher jeweils inkrementierend bei jedem Zugriff hochgezaehlt wird. Der Umbruch erfolgt durch modulo Berechnung, so dass kein Ueberlauf entstehen kann.
Wichtig ist, dass die Auftrittswahrscheinlichkeiten nicht veraendert werden. Dies kann dadurch erzielt werden, in dem die Groesse eines jeden Arrays seiner naechsten Primzahl entspricht.
Nun beschraenkt sich die notwendige CPU Belastung auf das inkrementieren eines integers und der modulo "Umbrechung". Man drueckt dies in Form von O(1) aus. Die Berechnung einer Zufallszahl wuerde einem Polynom entsprechen, von welchem der Grad unbekannt ist. Also die Form O(x^m) annehmen kann, wobei m von der Implementierung abhaengt (und im besten Fall 0 entspricht, wohl aber >=1 sein wird).
So, ich bitte um eine Diskussion, wie man selbst dieses Verfahren noch beschleunigen koennte.
Marco
[1] http://www.computec.ch/forum_viewtopic.php?14.9715.10
[ Bearbeitet ]