add Node to List sorted Algorithmus

amiga-news.de Forum > Programmierung > add Node to List sorted Algorithmus

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

-1-

[ - Beitrag schreiben - ]

30.12.2011, 13:07 Uhr

AGSzabo
Posts: 1663
Nutzer

Hallo,

hat zufällig jemand einen Algo im Kopf, mit dem ich eine Node in eine Exec-Liste an der alphabetisch richtigen Position einfügen kann? Pseudocode reicht.

ags
--
Author of Open eXternal User Interfaces - Sam mini os4.1 upd. 2 / e-uae 39bb2 / A4000D 3.0 & 3.9 2mbchip 8mbfast Ariadne_II ide DVD und HD / A500 3.1 (mkick) adide 50mb / Athlon ii X2 Ubuntu Linux

[ - Antworten - Zitieren - Direktlink - ]

30.12.2011, 13:34 Uhr

thomas
Posts: 7718
Nutzer

Fang am Anfang der Liste an und suche die erste Node, die größer ist als die neue und füge die neue davor ein.

Wenn zu erwarten ist, dass die reinkommenden Einträge größtenteils schon sortiert sind, dann ist es vielleicht besser, am Ende der Liste anzufangen und rückwärts die erste Node zu suchen, die kleiner ist.

Oder du machst es so, dass du von vorne suchst, wenn die neue mit A bis M anfängt und von hinten bei N bis Z.

Solange die Nodes nur einfach verkettet sind, läuft es jedenfalls immer auf eine sequentielle Suche heraus.

--
Email: thomas-rapp@web.de
Home: thomas-rapp.homepage.t-online.de/

[ - Antworten - Zitieren - Direktlink - ]

30.12.2011, 13:40 Uhr

Thore
Posts: 2266
Nutzer

Wenn die Liste lang wird, kann auch eine Interpolationssuche in Frage kommen. Du fängst in der Mitte an. Kommt dein Text vorher, dann such im linken Block weiter, kommt er später, im rechten Block. Aus diesem Block suchst du nun wieder die Mitte und dann den linken oder rechten Teil dieses Blocks.
Das geht natürlich nur in sortierten Listen. Aber das ist deine ja ohnehin, wenn du von Anfang an sortierst durch Einfügen.
Der Vorteil ist hier bei langen und sehr langen Listen, weil man mit wenigen Sprüngen zum Ziel kommt.
Bei kurzen Listen ist sequenziell besser, da der Aufwand der Interpolationssuche größer sein kann als das durchforsten weniger Listen-Einträge.

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

[ - Antworten - Zitieren - Direktlink - ]

30.12.2011, 14:10 Uhr

AGSzabo
Posts: 1663
Nutzer

Das Directory hat 2000 Files und es geht jetzt mit der sequentiellen Suche berauschend schnell. Auch das Refreshen passiert jetzt im Intuiticks-Takt. Der Flaschenhals war tatsächlich die Bubble-Sortierung nach jedem neuen Eintrag. Außerdem speichere ich die Nodes nimmer zwischen, sondern hänge sie nach dem Einlesen des Dateieintrages direkt gleich in die Liste. Refresht wird aber nur wenn ein Tick kommt und auch nur dann wenn nicht gerade schon refresht wird.

Hier zum Überblick mein AddSorted code:

code:

LV_addsorted	bsr	new_row

		push	d0
		beq	.pop

		move.l	d0,a1

		move.l	oxLV_contentgroup(a3),a0

		pushm	a0/a1

		sub.l	a2,a2

		; get new node texts, add at head if none

		move.l	a1,a0
		move.w	#oxLRA_texts,d0
		jsr	_LVOoxGetAttr(a6)
		tst.l	d0
		beq	.add

		; get first column text of new node, add head if none

		move.l	d0,a4
		move.l	(a4),d0
		beq	.add
		move.l	d0,a4

		; get first (and next) node, add at head if none

		move.l	(a7),a0

		lea	oxO_list(a0),a3
.loop		move.l	(a3),a3
		tst.l	(a3)
		beq	.add

		; get that node texts, skip if none

		move.l	a3,a0
		move.w	#oxLRA_texts,d0
		jsr	_LVOoxGetAttr(a6)
		tst.l	d0
		beq	.loop

		; get first column text of that node, skip if none

		move.l	d0,a0
		move.l	(a0),d0
		beq	.loop
		move.l	d0,a0

		move.l	a4,a1
		bsr	.strcmp
		bgt	.add

		move.l	a3,a2
		bra	.loop

.add		popm	a0/a1
		jsr	_LVOoxAddMemberAfter(a6)

		tst.l	d0
		beq	.dispose

.pop		pop	d0
		rts

.dispose	pop	a0
		jsr	_LVOoxDispose(a6)
		moveq	#0,d0
		rts

.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

Da es so schnell genug geht und Directorys selten mehrere Tausend Einträge haben (?), verzichte ich auf die Interpolationssuche oder ähnliches. Ich weiß auch momentan garnicht, wie ich da schneller als jetzt schon ist immer die Mitten finden kann.

Meine Methode wirkt ein bischen aufgeblasen, das rührt daher, dass man a) in einer späteren Version auch nach anderen Spalten soriteren können muss und b) dass die Listview die für das Adden zuständig ist, den Offset für den Zeiger auf das Spaltentexte-Zeiger Array im Listenzeilen-Objekt nicht kennt.

danke
--
Author of Open eXternal User Interfaces - Sam mini os4.1 upd. 2 / e-uae 39bb2 / A4000D 3.0 & 3.9 2mbchip 8mbfast Ariadne_II ide DVD und HD / A500 3.1 (mkick) adide 50mb / Athlon ii X2 Ubuntu Linux

[ Dieser Beitrag wurde von AGSzabo am 30.12.2011 um 14:13 Uhr geändert. ]

[ - Antworten - Zitieren - Direktlink - ]

30.12.2011, 19:20 Uhr

Thore
Posts: 2266
Nutzer

>Ich weiß auch momentan garnicht, wie ich da schneller als jetzt schon ist immer die Mitten finden kann.

Das ist einfach. Jeder Node bekommt seine Position als ID und du speicherst in der Hauptklasse der Liste (oder der Struct) einfach die Anzahl der Items mit.
Aber wenn es nur für Directories ist, hast du vll maximal 15000 Einträge, da ist sequenzielle/lineare Suche noch erträglich.
Freut mich wenns so klappt.

[ - Antworten - Zitieren - Direktlink - ]

30.12.2011, 19:27 Uhr

AGSzabo
Posts: 1663
Nutzer

@Thore:

Das verstehe ich noch nicht. Wie hilft mit die Anzahl der Nodes beim Finden der Mitte?
--
Author of Open eXternal User Interfaces - Sam mini os4.1 upd. 2 / e-uae 39bb2 / A4000D 3.0 & 3.9 2mbchip 8mbfast Ariadne_II ide DVD und HD / A500 3.1 (mkick) adide 50mb / Athlon ii X2 Ubuntu Linux

[ - Antworten - Zitieren - Direktlink - ]

30.12.2011, 21:59 Uhr

Der_Wanderer
Posts: 1229
Nutzer

Ich würde auf jedenfall das Sortieren auf O(n*log(n)) drücken, d.h. Quicksort oder Binärsuche (http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche) zum Einfügen.
Du musst für den Fall optimieren, wenn es viele Einträge sind, nicht versuchen zu sparen wenn es wenig Einträge sind. Wenn es wenige sind, dann ist es immer schnell genug.

--
--
Author of
HD-Rec, Sweeper, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, TKPlayer, AudioConverter, ScreenCam, PerlinFX, MapEdit, AB3 Includes und viele mehr...
Homepage: http://www.hd-rec.de

[ Dieser Beitrag wurde von Der_Wanderer am 30.12.2011 um 22:00 Uhr geändert. ]

[ - Antworten - Zitieren - Direktlink - ]

30.12.2011, 22:03 Uhr

AGSzabo
Posts: 1663
Nutzer

Ich war auf Bubblesort. Das war in jedem Fall zu langsam.

Das Adden an der richtigen Position ist mir schnell genug, bzw quicksort oder gar binärsort versteh ich vorne und hinten nicht. Interessant wäre evtl noch diese Interpolationssuche...

ps: ich möchte jetzt noch mit rein nehmen, dass zusätzlich zum Alfabet als Kriterium eine Node Priorität verwendet wird. Damit kann man dann Verzeichnisse an den Anfang stellen. Wie berücksichtigt man das im Algo?

[ Dieser Beitrag wurde von AGSzabo am 30.12.2011 um 22:22 Uhr geändert. ]

[ - Antworten - Zitieren - Direktlink - ]

30.12.2011, 23:10 Uhr

Der_Wanderer
Posts: 1229
Nutzer

Deine Vergleichsfunktion muss bei Verzeichnissen größer (oder kleiner) als Files zurückgeben. Die Vergleichsfunktion muss also die Information haben.
Im simpelsten Fall stellst du jedem Verzeichnis ein "a" vornedran, und jedem File ein "b". Aber ich würde das als extra Parameter für die Vergleichsfunktion machen.

... oder, wenn es fix immer diese Zeit Kategorien gibt, dann lege einfach zwei Listen an.

--
--
Author of
HD-Rec, Sweeper, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, TKPlayer, AudioConverter, ScreenCam, PerlinFX, MapEdit, AB3 Includes und viele mehr...
Homepage: http://www.hd-rec.de

[ Dieser Beitrag wurde von Der_Wanderer am 30.12.2011 um 23:11 Uhr geändert. ]

[ - Antworten - Zitieren - Direktlink - ]

03.01.2012, 12:06 Uhr

Holger
Posts: 8116
Nutzer

Zitat:
Original von AGSzabo:
ps: ich möchte jetzt noch mit rein nehmen, dass zusätzlich zum Alfabet als Kriterium eine Node Priorität verwendet wird. Damit kann man dann Verzeichnisse an den Anfang stellen. Wie berücksichtigt man das im Algo?

Ist das wirklich ein Problem für Dich?

1. Überprüfe nach wichtigerem Kriterium. Wenn ungleich ⇒ fertig
2. Ansonsten überprüfe nach zweitwichtigem Kriterium

Du kannst beliebig viele Vergleichskriterien zu einem zusammenfassen. Darauf sollte man aber wirklich von selbst kommen.

Wie packst Du Schuhe in ein Regal?

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

[ - Antworten - Zitieren - Direktlink - ]

03.01.2012, 12:07 Uhr

AGSzabo
Posts: 1663
Nutzer

@Holger:

> Ist das wirklich ein Problem für Dich?

das hab ich schon längst gelöst.
--
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 - ]

03.01.2012, 12:25 Uhr

Holger
Posts: 8116
Nutzer

Zitat:
Original von AGSzabo:
@Holger:
> Ist das wirklich ein Problem für Dich?
das hab ich schon längst gelöst.

War es wirklich ein Problem für Dich?

Oder stellst Du auch gerne mal Fragen, bevor Du selber drüber nachdenkst?

[ - Antworten - Zitieren - Direktlink - ]

03.01.2012, 12:30 Uhr

AGSzabo
Posts: 1663
Nutzer

@Holger:

Es war mir nicht gleich ganz klar. Ich hatte darüber schon nachgedacht.
--
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-

[ - Beitrag schreiben - ]

amiga-news.de Forum > Programmierung > add Node to List sorted Algorithmus

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