Stringlisten abgleichen

Flamefire · Verfasst: Mi 01.10.08 13:02

So ich hab da noch eine PerformanceFrage:

Ich habe 2 sortierte Stringlisten, wie z.b.:

1 1
2 3
3 4
5 5

Und die will ich abgleichen. Also eine Unterscheidung, welche Elemente wo überflüssig sind oder gleich sind.

Ich mache es z.zt. so:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

is:=0;
it:=0;
while (is<l1.ct) and (it<l2.ct) do begin
  icmp:=CompareText(l1[is],l2[it]);
        if(icmp>0) then begin
          //l2[it] vor l1[is]
          Inc(it);
        end else if(icmp<0) then begin
          //l1[is] vor l2[it]
          Inc(is);
        end else begin
          //Beide gleich
          Inc(is);
          Inc(it);
        end;
end;

Ich hoffe das Prinzip ist verständlich

Hat da noch jmd Optimierungsideen?
Gibts schnellere Text-Sortier-Funktionen als CompareText?

Danke schonmal

jasocul · Verfasst: Mi 01.10.08 13:15

Ich würde mit IndexOf arbeiten.

Ehemaliges Mitglied Erhaltene Danke: 1

IndexOf geht die Liste aber immer wieder von Anfang an durch.

elundril · Verfasst: Mi 01.10.08 13:22

vielleicht kannst du ne klasse ableiten die ein indexof mit offset anbietet. (der vorteil von indexof ist das du keine der listen sortieren musst)

_________________

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

jasocul · Verfasst: Mi 01.10.08 13:27

DeddyH hat folgendes geschrieben :

IndexOf geht die Liste aber immer wieder von Anfang an durch.

Stimmt einwandfrei. Bei kleinen Listen ist das aber zu vernachlässigen. Bei großen Listen, gibt es echte Performance-Probleme.

Flamefire · Verfasst: Mi 01.10.08 14:14

indexof hat einen nachteil:
ich müsste jeweils alles durchsuchen-->dauert
und ich müsste 2 listen durchgehen und immer löschen

das wäre dann sowas:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

for i:=0 to liste1.ct-1 do 
if(list2.indexof(liste1[i])) then //Element da..behandeln...aus liste2 löschen
else //element nicht da


for i:=0 to list2.ct-1 do //list2[i] ist nicht in list1

wäre vermutlich zu langsam
darum hab ich ebn gedacht: von oben nach unten durchgehen und wenn ein element aus einer liste vor dem anderen ist ist es neu

dürfte doch schneller sein als die vielen vergleiche...
hat da mal jmd ne gute berechnung zum worst-case szenario?

Edit: habe mal ne berechnung gemacht:
Worst Case bei IndexOf (2 verschiedene listen): Aufwand: x*y (x=liste1.ct; y=list2.ct), da alles mit allem verglichen wird
Worst Case bei meiner variante (s.o.): Aufwand: x+y, da erst liste1 einmal durchgegangen wird mit je 1 vergleich, dann liste 2 komplett durchgerattert...

Wäre also im prinzip schonmal optimal...
Nur könnte es sein, dass ein Stringvergleich auf Gleichheit schneller ist, als einer auf größer/kleiner/gleich

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme