Wieviele Files in Dir? - amiga-news.de Forum

amiga-news.de Forum > Programmierung > Wieviele Files in Dir?

[ - Suche - Neue Beiträge - Registrieren - Login - ]

1 2 -3-

[ - Beitrag schreiben - ]

07.01.2012, 13:43 Uhr

Thore
Posts: 2266
Nutzer

Recht viele Sprünge drin, die kosten. Auf nem 68060 kein Thema mit dem Branch Cache aber die anderen 68k müssen ackern. Allerdings fraglich obs hier wirklich anders geht.
Hast Dus mal auf Geschwindigkeit geprüft? Ist es bei deiner Anzahl Nodes schneller als Linearsuche?
Wenn Du die Anzahl Nodes vorher prüfst und bis zu nem gewissen Wert Linearsuche verwendest und ab nem gewissen Wert Interpolation/Binärsuche dann hast Du ein absolutes Optimum an Geschwindigkeit. Musst nur ausloten wo die Grenze liegt.

[ Dieser Beitrag wurde von Thore am 07.01.2012 um 13:44 Uhr geändert. ]

[ - Antworten - Zitieren - Direktlink - ]

07.01.2012, 14:49 Uhr

AGSzabo
Posts: 1663
Nutzer

@Thore:

> Hast Dus mal auf Geschwindigkeit geprüft?

Ich konnte bisher keinen Unterschied feststellen. Der PC an dem ich zur Zeit bin ist sowieso viel zu langsam, besonders die Platte. Daheim kann ich dann besser testen. So Spielchen wie zuerst alle (!) Dateien einlesen (großer Buffer) und dann sehen wie lange das reinen Einfüllen dauert, hab ich schon ausprobiert und keinen Unterschied bemerkt.

> Musst nur ausloten wo die Grenze liegt.

Ja sowas ging mir auch schon durch den Kopf. Ich vermute so ab 2500 Files.
--
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 - ]

08.01.2012, 11:29 Uhr

AGSzabo
Posts: 1663
Nutzer

Bahh, ich habe leider festgestellt, dass mein schöner Algo vermutlich nur bei sehr großen Datenmengen ein paar Fehler mit rein bringt. Und zwar keine einzelnen Ausrutscher, sondern ganze Blöcke von Namen mit dem selben Anfangsbuchstaben landen an der falschen Stelle. Das Problem tritt aber nur sporadisch auf.

Außerdem hatte der .strcmp code den Fehler, dass die Case-Unabhängigkeit auch bei Chars außerhalb der Buchstaben das Bit 5 gelöscht hat, was bei Satzzeichen zB zu Fehlern führt. Hab ich mal ganz raus genommen. Dafür konnte ich das leeren von d0 und d1 am Anfang der Funktion einsparen und das sub.l d0,d1 zu sub.b machen. Das geht offenbar genauso:

code:

.cmploop	move.b  (a1)+,d1
		move.b  (a0)+,d0
		beq.s  .cmp
		cmp.b  d0,d1
		beq.s  .cmploop
.cmp		sub.b  d1,d0
.rts		rts

[ - Antworten - Zitieren - Direktlink - ]

09.01.2012, 11:46 Uhr

AGSzabo
Posts: 1663
Nutzer

@Holger:

Zitat:
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

Hab ich jetzt mal versucht, so um zu setzen. Da ist ein Problem gleich zu Anfang aufgetreten: Angenommen es sind zwei Nodes, da gibt es keine Mitte und ich weiß nicht, ob der neue Knoten vor den ersten, oder zwischen beide, oder nach dem zweiten eingefügt werden muss. Diese Situation kann auch am Ende des Suchvorgangs eintreten.

--
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 - ]

09.01.2012, 17:26 Uhr

Holger
Posts: 8116
Nutzer

Zitat:
Original von AGSzabo:
Da ist ein Problem gleich zu Anfang aufgetreten: Angenommen es sind zwei Nodes, da gibt es keine Mitte und ich weiß nicht, ob der neue Knoten vor den ersten, oder zwischen beide, oder nach dem zweiten eingefügt werden muss.

Zu Beginn musst Du natürlich überprüfen, ob Dein Knoten überhaupt zwischen Anfangs- und Endknoten liegt. Gehört er vor den ersten oder hinter den letzten, weißt Du ja, was zu tun ist.

Zitat:
Diese Situation kann auch am Ende des Suchvorgangs eintreten.

Nö, wie denn?
Wenn Du die Anfangssituation geprüft und den Algorithmus korrekt implementiert hast, gibt es überhaupt kein Problem.

Du weißt mit Sicherheit, dass der Knoten hinter A und vor E gehört, also weißt Du, dass er zwischen A und E gehört. Gibt es zwischen diesen beiden Knoten keinen weiteren (also auch keine Mitte) mehr, bist Du fertig.

--
Good coders do not comment. What was hard to write should be hard to read too.

[ - Antworten - Zitieren - Direktlink - ]

09.01.2012, 17:29 Uhr

Holger
Posts: 8116
Nutzer

Zitat:
Original von AGSzabo:
Außerdem hatte der .strcmp code den Fehler, dass die Case-Unabhängigkeit auch bei Chars außerhalb der Buchstaben das Bit 5 gelöscht hat, was bei Satzzeichen zB zu Fehlern führt.

Wieso? Glaubst Du, den User interessiert es, ob Satz- und Sonderzeichen korrekt nach ASCII-Code sortiert sind?

--
Good coders do not comment. What was hard to write should be hard to read too.

[ - Antworten - Zitieren - Direktlink - ]

09.01.2012, 18:09 Uhr

AGSzabo
Posts: 1663
Nutzer

@Holger:

Ok, ich habe es hin bekommen. Problem, es ist total slow. Was siehst du?

code:

.binary		; new node in a4, used in .cmpnodes

		; get most left node to a2 and
		; most right node to d2

		move.l	(a7),a0
		move.l	oxO_list(a0),a2
		move.l	oxO_list+8(a0),d2

		; neue node links oder rechts aussen?

		move.l	a2,a5
		bsr	.cmpnodes
		bge	.linksaussen

		move.l	d2,a5
		bsr	.cmpnodes
		bgt	.schleife

		; rechtsaussen

		move.l	d2,a2
		bra	.add

.schleife	; folgt rechts auf links?

		cmp.l	(a2),d2
		beq	.add

		; wenn nur eine node zwischen liegt,
		; gehe nur eins vorwärts 

		move.l	a2,a5
		lsr.w	#1,d5
		move.w	d5,d0
		beq	.vorwaerts

		subq.w	#1,d0

.vorwaerts	move.l	(a5),a5
		dbf	d0,.vorwaerts

		; ist die neue node links oder rechts vom pivot?

		bsr	.cmpnodes
		bgt	.ist_links

		; ist rechts, ersetze linken rand durch pivot

		move.l	a5,a2
		bra	.schleife

.ist_links	; ersetze rechten rand durch pivot

		move.l	a5,d2
		bra	.schleife

.linksaussen	sub.l	a2,a2

.add		; einfügen nach node in a2

--
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 09.01.2012 um 18:12 Uhr geändert. ]

[ Dieser Beitrag wurde von AGSzabo am 09.01.2012 um 18:33 Uhr geändert. ]

[ Dieser Beitrag wurde von AGSzabo am 09.01.2012 um 18:42 Uhr geändert. ]

[ Dieser Beitrag wurde von AGSzabo am 09.01.2012 um 19:00 Uhr geändert. ]

[ - Antworten - Zitieren - Direktlink - ]

09.01.2012, 18:11 Uhr

AGSzabo
Posts: 1663
Nutzer

@Holger:

> Wieso? Glaubst Du, den User interessiert es, ob Satz- und Sonderzeichen korrekt nach ASCII-Code sortiert sind?

Bei mir hat sich das Satzzeichen unter die Buchstaben gemischt.
--
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 - ]

09.01.2012, 20:10 Uhr

Holger
Posts: 8116
Nutzer

Zitat:
Original von AGSzabo:
Bei mir hat sich das Satzzeichen unter die Buchstaben gemischt.

Welches Satzzeichen, welcher Buchstabe?

Es kann eigentlich nicht passieren, weil diese Bit-Clear Operation ziemlich genau und auch umkehrbar die Groß- und Kleinbuchstaben aufeinander mappt.

Einziger Fehler, den ich erkennen kann, ist, dass ÿ wie ein ß behandelt wird, was allerdings nicht so wichtig ist, weil es weder das große ß, noch das Ÿ im 8 Bit Zeichensatz des Amigas gibt.

Klar, das ist keine richtige alphabetische Sortierung oder Ordnung nach DIN 5007 oder ähnliches, aber als einfacher String-Vergleich sollte er eigentlich funktionieren.

--

[ Dieser Beitrag wurde von Holger am 09.01.2012 um 21:13 Uhr geändert. ]

[ - Antworten - Zitieren - Direktlink - ]

09.01.2012, 20:23 Uhr

AGSzabo
Posts: 1663
Nutzer

@Holger:

> Welches Satzzeichen, welcher Buchstabe?

Der Punkt wollte manchmal nicht da liegen, wo er hingehört. Aber ich habs eben nochmal getestet: es kommt mit dem bitclear zB "test" zwischen "test (4. Kopie)" und "test (5. Kopie)" zum liegen.
--
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 - ]

09.01.2012, 20:35 Uhr

Holger
Posts: 8116
Nutzer

Zitat:
Original von AGSzabo:
es kommt mit dem bitclear zB "test" zwischen "test (4. Kopie)" und "test (5. Kopie)" zum liegen.

Ahh, so ergibt es einen Sinn. Das hat nichts mit dem Punkt zu tun, sondern mit dem Leerzeichen, das nach Löschen des Bits ein null-byte ist und wie ein String-Ende behandelt wird.

--
Good coders do not comment. What was hard to write should be hard to read too.

[ - Antworten - Zitieren - Direktlink - ]

1 2 -3-

[ - Beitrag schreiben - ]

amiga-news.de Forum > Programmierung > Wieviele Files in Dir?

[ - Suche - Neue Beiträge - Registrieren - Login - ]