Entwickler-Ecke

Delphi Language (Object-Pascal) / CLX - Stringlisten abgleichen


Flamefire - Mi 01.10.08 13:02
Titel: Stringlisten abgleichen
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:


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 - Mi 01.10.08 13:15
Ich würde mit IndexOf arbeiten.


Delete - Mi 01.10.08 13:19
IndexOf geht die Liste aber immer wieder von Anfang an durch.


elundril - 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)


jasocul - Mi 01.10.08 13:27
user profile iconDeddyH hat folgendes geschrieben Zum zitierten Posting springen:
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 - 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:


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


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!