Beiträge von Yjuq

Bevor ich es vergesse, hier mal eine andere Version des Algo in Beitrag #18.
Könnt ihr mal eure Ergebnisse posten? Bei mir braucht das mit den String Funktionen etwas unter einer Sekunde.

Hey ProgrammingDonkey!
Ich bin zu faul um mich hinter deinen Gedanken zu deinem Skript einzulesen, das eine oder andere Kommentar hätte sicherlich geholfen. Was mir jedoch konkret ins Auge springt ist das _ArrayDelete(). Bei jedem Aufruf wird das Array neu dimensioniert, das kostet viel Zeit. Um Optimierungen vorzunehmen muss man erst einmal genau wissen was man möchte. Bei dieser Primzahlen-Geschichte kann man bereits mathematische Gesetze ausnutzen. So wie ich das sehe tust du das nur bedingt, da kann man tatsächlich viel mehr rausholen als wie es den Anschein hat. Du hattest mich um eine Erklärung zu meinen Skript gebeten, um das allerdings zu verstehen muss der Gedanke dahinter verstanden werden. Ich versuche es mal zu erklären, eine Optimierung deines Codes kannst du anhand des gewonnenen Wissens dann selber vornehmen.

Mein Algorithmus tut eigentlich nur folgendes:
1. Es wird eine Liste angelegt von 2 bis N Elementen (in Form eines 1D Arrays)
2. Es wird die kleinste Zahl aus der Liste gesucht welche noch nicht „durchgestrichen“ ist, dies muss eine Primzahl sein.
3. Alle Vielfachen der Gefunden Zahl werden „durchgestrichen“.
4. Gehe wieder zu Schritt 2 und wiederhole die Schritte bis das Ende der Liste erreicht wurde.
5. Alle nicht durchgestrichenen Zahlen sind Primzahlen.

Anders gesagt arbeitet dieser nach dem Sieb des Eratosthenes. Eine einfache Implementierung würde folgendermaßen aussehen:

Wenn wir uns mal Zeile 4 anschauen, so sehen wir folgende Rechnung:Sqrt($limit). Es ist so, dass nur alle Zahlen bis zu der Quadratwurzel der Endzahl abgeklappert werden müssen. Bei 100 Primzahlen müssen also nur alle Vielfachen von 2 bis 10 tatsächlich durchgestrichen werden. Alle anderen Zahlen zu überprüfen und deren Vielfache durchzustreichen wäre lediglich nur Zeitverschwendung. Dies liegt daran dass wir jede Zahl in ihre Primfaktoren zerlegen können. Das bedeutet, dass die Zahl eine Vielfache des Primfaktor ist. Und maximal 1 Primfaktor (und das muss nicht mal unbedingt so sein) kann größer sein als die Quadratwurzel jener Zahl. Alle anderen Primfaktoren liegen damit unter der Quadratwurzel. Ein Beispiel wird dies nochmal verdeutlichen:

Nehmen wir an wir wollen alle Primzahlen bis 1000 ermitteln. Die Quadratwurzel dieser Zahl ist 31,62. Wenn wir die Zahl 1000 in ihre Primfaktoren zerlegen erhalten wir die Faktoren 2^3 * 2^5. Das bedeutet dass 1000 die Vielfache von 2 und 5 ist. Nun zerlegen wir die 999: 3^3 * 37 Wir sehen dass ein Faktor über der Quadratwurzel von 31,62 liegt. Ist aber soweit nicht tragisch da der Faktor 3 noch darunter liegt. Streichen wir also alle Vielfachen von 3 weg, so ist auch die 999 durchgestrichen. Dies kann man jetzt für jede Zahl fortführen, das System geht auf. Deshalb brauchen wir nur alle Zahlen von 2 bis Sqrt(n) durchlaufen da sowieso alle Vielfachen weggestrichen werden. Ich hoffe es ist so verständlich.

Schauen wir uns jetzt noch Zeile 17 an: For $m = $n ^ 2 To $limit Step 2 * $n
Wir starten bei $n ^ 2. Warum ist das allerdings so? Potenzieren wir unsere Startzahl (meinetwegen die 3) so stellen wir fest dass die 6 dabei übersprungen wird. Durch das Step 2 * $n werden auch die 12, 18 und 24 übersprungen. Bei der 5 wären dies die Zahlen 10, 15, 20, 30, 40 usw. Wir sehen also, dass (beinahe) nur gerade Zahlen übersprungen werden, die Schleifendurchläufe werden weniger und so brauchen wir weniger Zeit. Was ist aber nun mit der 15? Nun ja, die 15 wird durch die 3 (da diese dort nicht übersprungen wird) durchgestrichen, dies verhält sich bei allen Zahlen so. Die kleineren Zahlen streichen jene Zahlen durch, welche die größeren überspringen. Zeit wird so aber definitiv eingespart.

Nun ist der Algorithmus aber noch nicht perfekt da es noch sehr lange dauert bis alle Primzahlen ermittelt wurden. Bei 1'000'000 als Limit braucht dieses Verfahren ca. 9 Sekunden bei mir. Da geht aber noch mehr.

Eine weitere Erklärung zu dem Rest folgt noch
Gerade keine Lust mehr zu tippen

Willkommen!
Da wünsche ich dir viel Glück bei deinem Projekt, hatte mich da auch mal dran versucht.
Ist aber gar nicht so einfach, vielleicht bin ich es damals auch nur falsch angegangen.
Hier der Thread dazu: BlueStacks Mauseingabe per Tastatur

Vielleicht hilft dir dieser irgendwann mal weiter

Zu Beitrag #31:
Hatte mal meine ganzen User Daten gelöscht: C:\Users\Cederik\AppData\Local\Google\Chrome
Jetzt funktioniert unter Chrome wieder alles, anscheinend hatte ich da irgend ein Extension was die Website hier blockiert.
Hat sich irgendwie eingeschlichen, keine Ahnung wie

Falls jemand ähnliche Probleme mit Chrome haben sollte, einfach den Ordner löschen.
Sofern ihr euch registriert habt werden sämtliche Lesezeichen (welche mit euren Account verknüpft sind) wieder hergestellt.

Noch ein Problem was ich gerade feststellen musste nachdem ich meine Cookies etc. gelöscht habe:
Man kann sich nicht wieder einloggen, oben links öffnet sich das übliche Popup nicht zum einloggen.
Jedoch kann man mit Rechtsklick > Link in neuen Tab öffnen < auf die Login-Seite wechseln.

Benutze Google Chrome neuste Version

Irgendwie kann ich drz. nichts mehr in die ShoutBox schreiben. Warum weiß ich nicht...
Die Seite wird nur neu refresht und das war's, aber die Nachrichten der anderen Teilnehmer kann ich doch schon lesen.

Ich hab ja noch nie ein Foto von Andy gesehen, aber irgendwie schaut er ganz anders aus als wie ich ihn mir ausgemalt habe.
Und, wie war's?

Klar geht das schneller: Alle Primzahlen bis 1'000'000 in 1,5 Sekunden

Meinst du vielleicht die OnAutoItExitRegister() Funktion?

Schönen guten Tag Community!
In der letzten Zeit habe ich mich intensiv mit Algorithmen beschäftigt, darunter auch um die Optimierungen dieser. Durch die Project Euler bin ich auf ein paar interessante Aufgaben gestoßen, welche das Thema Primzahlen betrifft. Ich bin erstaunt was sich mit ein wenig Fachwissen an einem Algorithmus alles an Geschwindigkeit heraus holen lässt. Ich möchte mit euch meine Erkenntnisse teilen und einfach mal niederschreiben was ich gelernt habe. In Zukunft werde ich Probleme so angehen, wie ich es durch diese Website gelernt habe. Nun denn, fangen wir einmal an:

Die Primfaktorzerlegung:
Eine natürliche Zahl über 1 lässt sich in Primzahlen zerlegen (sofern diese nicht selber eine Primzahl ist). In diesen Teilabschnitt geht es darum einen Algorithmus zu entwickeln, der eine beliebige Zahl in ihre Primfaktoren zerlegt und diese als 2 dimensionales Array aus gibt. Gehen wir beispielsweise einmal von der Zahl 140 aus, ihre Primfaktoren sind 2^2 * 5 * 7. Doch wie genau können wir jetzt vorgehen um diese Primzahlen zu ermitteln?

Ein Denkbarer (und einfacher) Ansatz wäre, einfach die Zahl ständig durch 2 zu dividieren, bis ein Rest entsteht. Danach dividieren wir die Zahl durch 3, 4 und 5 (usw.) bis aus unserer ursprünglichen Zahl 1 geworden ist. Versuchen wir das mal mit der 140:

140 / 2 = 70 Rest 0
70 / 2 = 35 Rest 0
35 / 2 = 17 Rest 1 > Da ein Rest besteht, kann 2 als weiterer Faktor nicht mehr zutreffen...
35 / 3 = 11 Rest 2
35 / 4 = 8 Rest 3
35 / 5 = 7 Rest 0
7 / 5 = 1 Rest 2
7 / 6 = 1 Rest 1
7 / 7 = 1 Rest 0 > Abbruchbedingung erfüllt! Ergebnis ist 1 und Rest = 0.

Wir sehen nun in unseren Rechnungen, dass jener Divisor welche als Faktor in Frage kommt ein restloses Ergebnis liefert. Dadurch sehen wir auch welche die Primfaktoren sind und wie oft diese vorkommen. Hier der dazu passende AutoIt Code:

Funktioniert doch, erste Sahne. Nun fangen wir an mit den Optimierungen an. Sicherlich fragt sich jetzt der schlaue Leser, warum überhaupt Optimierungen vorgenommen werden sollten? Tja, ich sag nur eins: Setzt doch mal die Zahl 98765432123 spaßeshalber ein und lasst euch davon die Primfaktoren ausrechnen. Mein Rechner hat 2 Minuten gebraucht um herauszufinden dass die Primfaktoren von 98765432123 = 1447^1 * 68255309^1 sind. Jetzt wird auch schnell klar weshalb das unser Algorithmus für solch eine Zahl so lange braucht. Es muss 68255309 Schleifendurchgänge durchlaufen, um auch diesen großen Primfaktor zu ermitteln. Nicht gerade optimal. Jedoch können wir mit ein wenig Know-How die Laufzeit um 50% verringern ohne dass wir auf irgend eine Akademie gegangen sein müssen. Es gibt (außer der 2) keine geraden Primzahlen! Wie denn auch? Jede gerade Zahl lässt sich durch 2 teilen und ist daher keine Primzahl, wir können uns also ersparen die geraden Zahlen zu durchlaufen und überspringen diese einfach. Das bedeutet wir müssen am Anfang überprüfen ob die Zahl durch 2 teilbar ist, danach nur noch ob diese durch eine ungerade Zahl teilbar ist. Unser Algorithmus verändert sich also folgendermaßen:

Super, damit haben wir unseren Anwender eine Wartezeit von einer Minute beschert, auf Toilette gehen kann er also auch nicht mehr, also müssen wir die Rechenzeit doch noch etwas verkürzen damit unsere Arbeit doch nicht ganz umsonst ist. Damit das allerdings klappt müssen wir eine andere Eigenschaft der Primzahlen ausnutzen. Jede Zahl kann(!) genau ein Primfaktor besitzen, welcher die Quadratwurzel der Zahl übersteigt. Dadurch müssen alle anderen Primfaktoren auf jeden Fall unter der Quadratwurzel der Zahl liegen. Damit haben wir schon mal ein Limit für unsere Schleifendurchgänge, und zwar die Quadratwurzel der Zahl. Damit können wir unseren Code noch mehr optimieren:

Und wenn wir den Code jetzt ausführen, brauchen wir für die gleiche Zahl, die uns vorhin mit unverschämten 120 Sekunden geärgert hat, knapp nur noch 10 Millisekunden. Wenn das mal keine Steigerung der Geschwindigkeit von unseren ursprünglichen Algorithmus ist! Die Geschwindigkeit hat sich um den Faktor 12000 verringert! Nun könnten wir nur noch berechnen wie viele Primfaktoren in etwa die Zahl hat und somit den Speicherbedarf für das Array senken. Eine Möglichkeit wäre es, alle Primzahlen zu multiplizieren (ab 2 aufwärts) bis wir die Zahl 2^64 -1 (x64) bzw. 2^32 -1 (x86) übersteigen. Die Anzahl der Faktoren entspricht somit die Anzahl der meist möglichen Primfaktoren für den überhaupt möglichen Speicherbereich. Dadurch können wir dem Array eine fixe Größe Zuteilen dessen Anzahl der Elemente wir nicht zur Laufzeit berechnen müssen.

>> Weiteres folgt noch...
Gerne dürft ihr auch selber was dazu schreiben

Achja, der Server...
IRC ist noch Neuland für mich, bin froh dass ich zmd. einen Client gefunden haben *g*
Ich glaube der Server ist folgender: sinisalo.freenode.net

€dit:
Hmn, auch hier: irc.afterworkchat.de
Also beide

Gab's dazu auch irgendwo eine Ankündigung oder woher weißt du das?
Mich hat's jedenfalls etwas geärgert...

Naja, ich verweile dann mal (bis alles fertig ist) im IRC Channel #autoit
Wer ein wenig Konversation führen will kann ja dazu stoßen.

Servus, kommt es mir nur so vor oder funktioniert das Forum nicht so wie es soll?
Bei mir habe ich im Titel "Burning Board" und der Aufruf ging die letzten 3 Tage überhaupt nicht.
Zudem fehlt bei mir komplett die ShoutBox, wenigstens geht die Anmeldung drz.

Was ist los? Ist das nur bei mir so oder ist das Forum unangekündigt im Wartungsmodus?

€dit: 1. April 2015 – 16:53 Uhr
Da es mir so vorkommt als würde der Thread zum neuen Sammlung an Problemen, war ich mal so frei den Titel zu ändern.
Ich versuche mal im Laufe der Zeit hier die aktuellen Probleme als Liste festzuhalten, sodass Gun-Food sich da nicht durch die Beiträge wühlen muss.

€dit: 25. August 2015 - 19:17 Uhr

• Codeformatierungen werden im Online Editor drz. nicht übernommen. (https://autoit.de/index.php/Thre…ne-Alternative/)

Sorry dass ich so spät erst die Liste erstelle, aber nach dem Thread hier schien @Gun-Food mit Hochdruck dran zu arbeiten dass ich dachte, eine Liste sei nicht mehr notwendig. Falls weitere Dinge auftauchen werde ich diese hier ergänzen.

GegX:
Dein Algorithmus hat eine Ausführungszeit von 25 Sekunden bei mir. Ich habe mal versucht mithilfe des Sieb des Eratosthenes die benötigte Zeit zu verringert. Alle Primzahlen von 2 bis 1000000 werden bei mir in 18~19 Sekunden ermittelt. Da geht bestimmt noch mehr:

Servus, ich war gerade dabei die Aufgabe 3 (deutsche Übersetzung) in den Project Eulers zu bewerkstelligen. Es ging um Primfaktorzerlegung, da dies ganz gut zum Thema passt würde ich gerne das Skript hier veröffentlichen. Aufgrund der hohen Zahl musste ein effizienter Algorithmus her ~ Naja

Rätsel #1:
Ein Mann geht nach einer langen Sauftour stark angetrunken nach Hause. Auf der Straße entdeckt er eine Münze am Boden liegen. Obwohl weder Mond noch Sterne am Himmel sichtbar sind und auch keine Straßenlaterne an ist, hat er das Geldstück schon von weitem gesehen. Wie ist das möglich?

Rätsel #2:

56784 = 4
11111 = 0
72348 = 3
88652 = 5
88811 = 6
75213 = 0
65465 = 3
62257 = ?

Welche Zahl wird gesucht? Mit Begründung bitte!

Rätsel #3:
Loch an Loch und hält doch?

Rätsel #4
Was haben Leetspeak, die Kreiszahl Pi und die Antwort auf Alles gemeinsam?

Das Rätsel ist mir ja schon beinahe zu einfach.
Die Lösung setze ich einfach mal vorsichtshalber in einen Spoiler:

Lol, da bin ich nicht drauf gekommen

Rein theoretisch kannst du zu dem control einzelne messages senden um ein screenshot vom jeweiligen zustand des controls zu machen. Danach musst du lediglich die paint messages vom gleichen controltyp uberschreiben und die kopierten screenshots anzeigen. Funktioniert bei einem button natuerlich besser als bei einem edit control. Besser ist es natuerlich doch lieber das design der controls per hand zu verfassen da du da mehr spielraum hast. Beides ist sowieso auf gleicher weise aufwendig.