|
ENGLISH VERSION |
|
 |
| Links | | | Forum | | | Kommentare | | | News melden |
|
| Chat | | | Umfragen | | | Newsticker | | | Archiv |
|
| amiga-news.de Forum > Programmierung > Wieviele Files in Dir? | [ - Suche - Neue Beiträge - Registrieren - Login - ] |
| 1 -2- 3 | [ - Beitrag schreiben - ] |
|
05.01.2012, 13:17 Uhr AGSzabo Posts: 1663 Nutzer |
@Holger: > Das wusstest Du aber nicht. Trotzdem hast Du angenommen, dass es schneller wäre. Ich hatte angenommen, dass der vorhandene Code schneller ist, weil er mit einem Test weniger aus kommt. Warum genau das so ist hat sich er erst dann geklärt. > Andererseits frag ich mich immer noch, wo da die Zeit verbraten werden soll, bei 2000 Einträgen und dem gezeigten Assembler-Code. Inzwischen arbeite ich mit einem Test von 8860 Einträgen. Auf 2000 springt der Zähler so schnell, dass es gleich am Anfang da zu sein scheint. Allerdings nur auf meiner Turbo-Maschine mit 2x 2700 Mhz. Übrigens ist mir der Einfrier-Hänger jetzt auch beim ASL Requester und beim "list" in der Shell aufgefallen. Könnte ein Problem des UAE sein. Den Suchalgo hab ich noch nicht ganz verstanden. Im Moment habe ich durchaus sehr viele ähnliche Strings, weil ich einfach den Directory-Inhalt 8x geklont habe um so viele Dateien zu erhalten.  -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 13:49 Uhr Thore Posts: 2266 Nutzer |
> Den Suchalgo hab ich noch nicht ganz verstanden. Ein Beispiel mit Zahlen Suche der Zahl 8 von 20 sortierten Einträgen: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Nehme das mittlere Element: 11 Vergleiche es mit der 8: Kleiner als 11 Nehme die linke Hälfte da kleiner. 0 1 2 3 4 5 6 7 8 9 10 Nehme das mittlere Element: 5 Vergleiche es mit der 8: Größer als 5 Nehme die rechte Hälfte da größer. 6 7 8 9 10 Nehme das mittlere Element: 8 Vergleiche es mit der 8: gefunden in 3 Schritten. Ach ja: Du brauchst nicht so viele Dateien zum Testen. Mach Dir doch ein Fake-Directory im Beispielcode (z.B. ne Textdatei mit tausenden Einträgen) und lese einfach die Strings ein. So kannst Du den Sortier-Einfüge Algo separat mal testen mit extrem vielen Einträgen ohne die Festplatte vollzumüllen. [ Dieser Beitrag wurde von Thore am 05.01.2012 um 13:51 Uhr geändert. ] [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 14:54 Uhr AGSzabo Posts: 1663 Nutzer |
@Thore: > ... Vergleiche es mit der 8: gefunden in 3 Schritten. Soweit klar. Woher weiß ich, wann wo die Mitte ist? -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 15:06 Uhr Thore Posts: 2266 Nutzer |
Die Anzahl weißt Du, wenn du sie mitschreibst. Anzahl / 2 (gerundet) = Pivot Dieses ist der Index deines mittleren Elements. Wie du das findest, da gibts mehrere Wege, z.B. wie Holger es beschrieb: Pivot mal dein Next aufrufen. Dieser Index ist dann beim nächsten Schritt der Anfang oder das Ende der neuen Menge (je nach dem ob linke oder rechte Hälfte genommen wurde) [ Dieser Beitrag wurde von Thore am 05.01.2012 um 15:07 Uhr geändert. ] [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 15:46 Uhr AGSzabo Posts: 1663 Nutzer |
Ich hab grad wieder auf ExAll() umgestellt. Mit einem größeren Buffer bringt es tatsächlich auch auf einem langsamen Gerät ein paar Sekunden. Den Algo habe ich soweit begriffen. Man könnte auch von Anfang an einen Zeiger auf das erste Element merken, und dann immer nach zwei neuen Nodes um 1 Node weiter gehen. So hat man immer die Mitte ohne die hälfte der Nodes bis dahin durchzugehen. Klappt das aber nur mit der Mitte, oder gibt es eine Möglichkeit, dieses Verfahren auf alle Schritte auszuweiten? ps: mit ExAll() hab ich auch gratis das Patternmatching mit drin, das ist sehr nett.  -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ Dieser Beitrag wurde von AGSzabo am 05.01.2012 um 15:47 Uhr geändert. ] [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 16:15 Uhr Thore Posts: 2266 Nutzer |
Das Pivot-Element kann man beliebig wählen, allerdings sinkt damit die Effizienz, wenn es nicht die Mitte ist. Im besten Fall findest du schneller, im schlechten Fall langsamer. Mit der Mitte hast Du eben das Optimum. Bei geraden Anzahlen gibt es keine Mitte, da ist es Dir freigestellt welche der zwei mittleren Elemente Du nimmst. [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 16:22 Uhr AGSzabo Posts: 1663 Nutzer |
@Thore: Ne, ich meine ich muss im zweiten Schritt die Mitte von der hälfte nehmen. Die erste Mitte kann ich wie oben beshrieben durch weitergehen zum nächsten Element nach allen zwei neuen Nodes merken. Die Frage war, ob ich die Mitte der Hälfte auch in etwa so ermitteln kann oder ob ich da dann durch die Hälfte der Hälfte Nodes steigen muss? Und so weiter. -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 16:34 Uhr Thore Posts: 2266 Nutzer |
Im Grunde kannst du es "auch einfach so schätzen". Ist allerdings wie erwähnt nicht mehr ganz effizient. Die neue Mitte kannst du aber auch ausrechnen [ Dieser Beitrag wurde von Thore am 05.01.2012 um 16:35 Uhr geändert. ] [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 17:06 Uhr AGSzabo Posts: 1663 Nutzer |
@Thore:Zitat: Ah ja, so ginge das. Ich müsste bei jedem Einfügen alle Nodes bis zum ersten Pivot durch steppen (Anzahl / 2), diesen vergleichen und dann von dort aus zB die eben Ermittelte Zahl wieder durch zweit teilen und vorwärts oder rückwärts so viele Nodes durch gehen. Dort wieder vergleichen und so weiter, bis 0 raus kommt, oder 1? Oder was sonst? Ich denke aber über eine noch weitere Beschleunigung nach: Ich merke mir den Anfang der Liste. Wenn ich neue Nodes anfüge, zähle ich deren Anzahl mit. Bei jeder geraden Anzahl steppe ich vom Anfang der Liste um 1 Node weiter und habe so immer einen Zeiger auf die Mitte der Liste, von der ich ausgehen kann! Für die weiteren Schritte würde ich weitere Zeiger benötigen, oder so wie oben weiter machen. Wenn ich weitere Zeiger will, müsste ich bei jedem zweiten weitergehen des aktuellen Mitte-Zeigers zwei neue Zeiger merken, nämlich auf eine Node vorher und eine Node nacher. Diese Zeiger müsste ich alle immer weiter anpassen. Hmmm, ich denke, das ist blöd. Bis auf den ersten Schritt, wo ich die Mitte ALLER Nodes merke. Der bringt mir evtl schonmal eine Beschleunigung um die Hälfte, ohne im ersten Schritt bis zur Hälfte zu steppen. Stimmts? -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 19:51 Uhr Holger Posts: 8116 Nutzer |
Zitat:Genau das schrieb ich bereits vor ein paar Stunden. Die Gesamtanzahl an vor/zurück Schritten ist (ungefähr) gleich der Anzahl Knoten. Zitat:Für Deinen Zweck läuft es so ab: 1. Du hast einen Anfang (erster Knoten) und ein Ende (letzter Knoten). 2. Du besorgst Dir den mittleren Knoten zwischen diesen beiden (Pivot) 3. Du vergleichst Deinen neuen Knoten mit dem Pivot 4. Ist der neue Knoten kleiner, ersetzt der Pivot Deinen Endknoten, ist er größer, ersetzt er Deinen Anfangsknoten. Gleichheit kann bei Dir nicht auftreten 5. Befinden sich zwischen Anfangs- und Endknoten noch andere Knoten, gehe zu Schritt 2. 6. Jetzt fügst Du den neuen Knoten zwischen A und E ein fertig Zitat:Das würde die Anzahl der Schritte während des Suchens halbieren. Zitat:Und natürlich auch in irgendeiner Datenstruktur merken. 2*log₂(n) Knoten. Zitat:Ja, was das reine Steppen angeht. Der eigentliche Performance-Killer und auch der Grund, überhaupt binäre Suche anzuwenden, sind die String-Vergleiche. Die kann man weiter reduzieren, wenn man, wie hier schon angesprochen, Interpolationssuche verwendet. Die Verfahren sind sich allerdings so ähnlich, dass es durchaus sinnvoll ist, zuerst die Binäre Suche zu implementieren. -- Good coders do not comment. What was hard to write should be hard to read too. [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 20:08 Uhr AGSzabo Posts: 1663 Nutzer |
@Holger: Danke. > Gleichheit kann bei Dir nicht auftreten Doch, die AddSorted Methode ist Teil der Listview, die von der Filerequesterklasse lediglich benutzt wird. Aus der Sicht der Listview kann es durchaus zwei oder mehr gleiche Knoten geben. In dem Fall hänge ich die neue Node einfach vor (oder nach?) dem Element ein, an dem die Gleichheit festgestellt wurde? -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 20:14 Uhr AGSzabo Posts: 1663 Nutzer |
@Holger: > 2. Du besorgst Dir den mittleren Knoten zwischen diesen beiden (Pivot) Hmm, dazu muss ich die Zahl der Nodes dazwischen wissen. Reicht es, wenn ich die beim Adden neuer Nodes 1 dazu zähle und die Zahl bei den Durchläufen jedesmal halbiere, zB mit lsr.l d0 ? Oder kommt es zu Ungenauigkeiten? -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 20:27 Uhr AGSzabo Posts: 1663 Nutzer |
@Holger: 1. Ich habe einen Anfangsknoten (im ersten Schritt die Erste Node der Liste) und eine Anzahl. Einen Endknoten brauche ich nicht. 2. Ich halbiere die Anzahl. Ist sie 0, gehe ich zu Schritt 4. Sonst gehe vom Anfangsknoten so viele Nodes vorwärts wie die Anzahl ist. Die neue Node vergleiche ich mit dem Ziel. 3. Ist die neue Node kleiner, bleibt der Anfangsknoten der selbe. Ist sie größer, wird der Pivot der neue Anfangsknoten. In beiden Fällen gehe ich zu Schritt 2. An sonsten gehe ich zu 4. 4. Ich füge die Node ein. -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 21:38 Uhr Thore Posts: 2266 Nutzer |
Ok, wenn dein Pivot sich ändert, bleibt die Anhahl dennoch gleich? Das wäre nämlich richtig dann. Bei jedem Mal halbiert sich die Anzahl, ungeachtet dessen wo dein Pivot ist. Probiers aus, scheint klappen zu können. [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 21:57 Uhr AGSzabo Posts: 1663 Nutzer |
@Thore: Bleibt nicht gleich. Wie meinst du das? VOR Jeder Suche nach dem neuen Pivot halbiert sich die Anzahl. -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 22:17 Uhr Thore Posts: 2266 Nutzer |
Mach einfach ein paar Schreibtischtests, dann siehst du was ich meine Also ne Menge: 1 2 3 4 5 6 7 8 9 10 dann wahlweise diese Zahlen suchen: 2, 5, 8, 9, 10 Klappt alles mit deinem Algo? Einfach von Hand mal nachempfinden mit Papier und Stift. [ - Antworten - Zitieren - Direktlink - ] |
|
05.01.2012, 22:46 Uhr AGSzabo Posts: 1663 Nutzer |
Ich seh grad mein Ansatz funktioniert so noch nicht richtig. Ich denke mir das mal auf Papier durch und melde mich dann wieder. -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
|
06.01.2012, 13:51 Uhr AGSzabo Posts: 1663 Nutzer |
Jetzt habe ich folgenden Code, der FAST funktioniert. Ich erhalte eine im Grunde geordnete Liste, in der ein paar wenige falsch positionierte Nodes drin sind. Sieht jemand den Fehler?code:.binary_add ; a0 list ; a1 new node ; a2 noder after which to add ; d4 new node priority ; a4 new node text pushm a0/a1 sub.l a2,a2 ; initially add at head ; get number of rows, add at head if none move.w oxLV_rowscount(a3),d5 beq .before .start ; get back list pointer move.l (a7),a5 ; get first node move.l (a5),a5 .half lsr.w #1,d5 beq .add_where ; find pivot, num is at least 1 move.w d5,d0 subq.w #1,d0 .findpivot move.l (a5),a5 dbf d0,.findpivot cmp.l my_priority(a5),d4 blt .right bgt .left move.l my_text(a5),a0 move.l a4,a1 bsr .strcmp blt .right bgt .left ; strings are equal here bra .after .right move.l a5,a2 bra .half .left move.l a2,a5 cmp.l #0,a5 beq .start bra .half .add_where ; get node priority, higher means add before cmp.l my_priority(a5),d4 blt .after bgt .before move.l my_text(a5),a0 move.l a4,a1 bsr .strcmp blt .after bgt .before ; strings are equal here .after move.l a5,a2 .before popm a0/a1 jmp _LVOoxAddMemberAfter(a6) .strcmp ; a0 string1, a1, string2 moveq #0,d0 moveq #0,d1 .loop1 move.b (a1)+,d1 bclr #5,d1 ; case independent move.b (a0)+,d0 beq.s .exit1 bclr #5,d0 cmp.b d0,d1 beq.s .loop1 .exit1 sub.l d1,d0 rts -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ Dieser Beitrag wurde von AGSzabo am 06.01.2012 um 13:52 Uhr geändert. ] [ - Antworten - Zitieren - Direktlink - ] |
|
06.01.2012, 13:58 Uhr Thore Posts: 2266 Nutzer |
Kannst Du nicht schauen, welche Nodes falsch sind und wie sie positioniert sind? Sind sie komplett anders, also "Test" zwischen "Abc" und "Bde" oder unterscheiden die sich an der 12. Stelle? Kannst Du das Problem mit wenigen dateien analysieren? [ - Antworten - Zitieren - Direktlink - ] |
|
06.01.2012, 14:05 Uhr AGSzabo Posts: 1663 Nutzer |
@Thore: Etwa 10 aus 80 Nodes sind komplett anders positioniert. -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
|
06.01.2012, 14:11 Uhr Thore Posts: 2266 Nutzer |
ich nehm an da funktioniert der such-Algo noch nicht richtig. Erste Vermutung: Wenn das Pivot erst rechts, dann links wandert, oder andersrum, stimmt was nicht mehr? (ungeprüft und nur eine Vermutung) [ - Antworten - Zitieren - Direktlink - ] |
|
06.01.2012, 14:16 Uhr AGSzabo Posts: 1663 Nutzer |
@Thore: Test hat ergeben, dass der Code zwischen .add_where und .before GARNICHTS bewirkt. -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
|
06.01.2012, 14:25 Uhr Thore Posts: 2266 Nutzer |
Geht das nicht daß man das blt .after einfach weglässt? Dann sparst ein Sprung.... [ - Antworten - Zitieren - Direktlink - ] |
|
06.01.2012, 14:27 Uhr AGSzabo Posts: 1663 Nutzer |
@Thore: Das bleibt drin weil darunter noch der Fall abgehandelt werden soll,falls beide Strings gleich sind... an sonsten kann man es weglassen, ja. -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
|
06.01.2012, 14:30 Uhr Thore Posts: 2266 Nutzer |
Im String Compare verwendest du auch d0 und d1, genau wie oben beim Pivot- Solltest du im Compare nicht die Register retten? [ - Antworten - Zitieren - Direktlink - ] |
|
06.01.2012, 15:01 Uhr AGSzabo Posts: 1663 Nutzer |
@Thore: Der immer zu halbierende Wert sitzt in d5, d0 ist bloß eine lokale Kopie davon für die Schleife. -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ Dieser Beitrag wurde von AGSzabo am 06.01.2012 um 15:01 Uhr geändert. ] [ - Antworten - Zitieren - Direktlink - ] |
|
06.01.2012, 20:26 Uhr AGSzabo Posts: 1663 Nutzer |
Ich habs! Mein Algo funktionierte schon im Grunde! Es musste noch ne Art Rundung mit rein und das ich mir beim vor-zurück gehen die richtige Node raus hole. Man musste mal hier mal da eine Node vorher oder nacher nehmen. Optimieren kann man bestimmt diese Rundung: code:.half ext.l d5 divu.w #2,d5 tst.w d5 beq .add_where move.l d5,d0 swap d0 tst.w d0 beq .a addq.w #1,d5 .a Bitte nicht wundern dass ich das so umständlich mache. Ich hatte zuerst nur ein "lsr.w #1,d5" drin. damit ging es aber nicht. Als Optimierung dachte ich mir, dass man das rechts evtl. raus geschobene ungerade Bit abfragen und/oder benutzen kann. Vielleicht kann jemand das ausschreiben oder hat eine bessere Idee? -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ Dieser Beitrag wurde von AGSzabo am 06.01.2012 um 20:36 Uhr geändert. ] [ - Antworten - Zitieren - Direktlink - ] |
|
06.01.2012, 20:45 Uhr AGSzabo Posts: 1663 Nutzer |
Mein Algo ist folgender: Hier ist der Algo im Prinzip erklärt: 1. Ich habe die Anzahl und den Anfang. Ist die Anzahl 0, füge ich die neue Node ein. 2. Ich halbiere die Anzahl. Und addiere Sie zum Anfang um den Pivot zu erhalten. An der resultierenden Stelle vergleiche ich die Nodes. 3. War die Anzahl nach der Halbierung 0, füge ich die neue Node je nach dem Vergleich vor oder hinter der Node an der resultierten Stelle ein. 4. War die Anzahl nicht 0 und die neue Node kleiner, gehe ich zu Schritt zwei. War die Anzahl nicht 0 und die neue Node größer, wird der Pivot mein neuer Anfang und ich gehe zu Schritt 2. Das ist sicher durch ein paar Umstellungen noch optimierbar, oder? -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
|
07.01.2012, 09:48 Uhr AGSzabo Posts: 1663 Nutzer |
Haha, die Lösung ist mir im Halbschlaf eingefallen:code:.half lsr.w #1,d5 beq .add_where bcc .find_pivot addq.w #1,d5 .find_pivot Das ist eine mögliche Optimierung! -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
|
07.01.2012, 10:37 Uhr AGSzabo Posts: 1663 Nutzer |
Jetzt aber zu der eigentlichen AddSorted Routine. Ist das noch optimierbar? Vor allem dass an zwei Stellen .cmpnodes aufgerufen wird, gefällt mir nicht wirklich. Es wird aber nix doppelt ausgeführt, oder? Das .add_where kommt nur am Schluss dran.code:add_sorted ; a0 list ; a1 new node ; a4 new node text (used in .cmpnodes) ; d4 new node priority (used in .cmpnodes) ; d5 number of nodes in list pushm a0/a1 ; a2 is the node after which the new node is added, ; if it remains 0 the new node is added at list head sub.l a2,a2 .start ; get back pointer to list move.l (a7),a5 .half lsr.w #1,d5 beq .add_where bcc .find_pivot addq.w #1,d5 .find_pivot move.w d5,d0 subq.w #1,d0 .loop ; get first or next node move.l (a5),a5 dbf d0,.loop bsr .cmpnodes beq .add bgt .left ; right (ble) move.l a5,a2 bra .half .left move.l a2,a5 move.l a5,d0 ; scratch to test for 0 beq .start bra .half .add_where move.l (a5),a5 bsr .cmpnodes bgt .add ; before ; after (ble) move.l a5,a2 .add popm a0/a1 jmp _LVOoxAddMemberAfter(a6) Die Subroutine .cmpnodes hatten wir schon besprochen, das ist die mit den Strings. -- Author of Open eXternal User Interfaces, eXternal Format Rippers and the Book "Torakosmos". Developing with E-UAE on an Ubuntu dualcore system. [ - Antworten - Zitieren - Direktlink - ] |
| 1 -2- 3 | [ - Beitrag schreiben - ] |
| amiga-news.de Forum > Programmierung > Wieviele Files in Dir? | [ - Suche - Neue Beiträge - Registrieren - Login - ] |
|
|
Impressum |
Datenschutzerklärung |
Netiquette |
Werbung |
Kontakt
Copyright © 1998-2024 by amiga-news.de - alle Rechte vorbehalten. |
|