Entwickler-Ecke :: Thema anzeigen - Mehrere Listen vergleichen

wurzel - Do 27.09.07 10:39
Titel: Mehrere Listen vergleichen

Hallo...

Hab 3 Listen, die im TXT-Format vorliegen. Was ich halt noch brauche, ist dass nicht nur Liste a mit Liste b verglichen wird, sondern auch mit Liste c...Und da werden in Zukunft halt noch serhr viele Listen kommen. Mein bisheriger Such-Code

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:

procedure TForm1.Button1Click(Sender: TObject);
var
  i, k, l : integer;
  target : String;
  temp : integer;

begin
  Memo1.Clear;
  count_dbl := 0;
  Liste_1 := TStringlist.Create;
  Liste_2 := TStringlist.Create;
  Liste_3 := TStringlist.Create;
  Liste_1.LoadFromFile(Edit1.Text + 'l1.txt');
  Liste_2.LoadFromFile(Edit1.Text + 'l2.txt');
  Liste_3.LoadFromFile(Edit1.Text + 'l3.txt');
  count_l1 := Liste_1.Count;
  count_l2 := Liste_2.Count;
  count_l3 := Liste_3.Count;
  Memo1.Lines.Add('Liste 1: ' + IntToStr(count_l1));
  Memo1.Lines.Add('Liste 2: ' + IntToStr(count_l2));
  Memo1.Lines.Add('Liste 3: ' + IntToStr(count_l3));
  for i := 0 to Liste_1.Count - 1 do
    begin
      target := Liste_1.Strings[i];
      Memo1.Lines.Add(target);
        for l := 0 to Liste_2.Count - 1 do
          begin
            if target = Liste_2.Strings[l] then
              begin
                count_dbl := count_dbl + 1;
                Memo2.Lines.Add(Liste_2.Strings[l]);
              end;
          end;
    end;     
  Label1.Caption := IntToStr(count_dbl);
end;

Narses - Do 27.09.07 10:42
Titel: Re: Mehrere Listen vergleichen

Moin!

wurzel hat folgendes geschrieben:

Hab 3 Listen, die im TXT-Format vorliegen. Was ich halt noch brauche, ist dass nicht nur Liste a mit Liste b verglichen wird, sondern auch mit Liste c...Und da werden in Zukunft halt noch serhr viele Listen kommen.

Und was soll das Ergebnis dieses Vergleichs sein? Identität, Differenz, Schnittmenge, ... :nixweiss:

cu
Narses

wurzel - Do 27.09.07 10:44

Als Ergebnis bekomme ich doppelte Einträge

ZeitGeist87 - Do 27.09.07 10:58

jede liste mit jeder?
oder hast du ne referenz-liste?

Narses - Do 27.09.07 11:03

Moin!

Also ich unterstelle mal die Schnittmenge (= Zeilen, die in allen Listen vorkommen). ;)

Ansatz: Schreib dir eine Prozedur, die zwei Stringlisten übergeben bekommt und dafür sorgt, dass nach dem Aufruf in der zweiten SL nur noch Strings enthalten sind, die auch in der ersten SL drin sind. Dann gehst du in einer Schleife von 1 bis (MaxSL-1) durch und übergibst paarweise die SLs. Am Ende hast du in der letzten Liste nur noch die Strings, die in allen Listen enthalten sind. :idea:

cu
Narses

wurzel - Do 27.09.07 11:38

ZeitGeist87 hat folgendes geschrieben:

jede liste mit jeder?
oder hast du ne referenz-liste?

Jede Liste mit jeder

Narses hat folgendes geschrieben:

Das klappt so net denke ich, weil ich am Ende auch noch wissen muss wo die doppelten Strings vorhanden waren

Moderiert von Narses: Doppelposting entfernt.

Narses - Do 27.09.07 11:48

Moin!

Dann verwendest du halt zum Sammeln der Schnittmenge eine weitere SL und lässt die anderen Listen unverändert.

Wenn du die Schnittmengenliste hast, gehst du in einem weiteren Lauf über alle Listen und kannst dann die Positionen der Schnittmengeelemente in der Originalliste z.B. mit .IndexOf() ermitteln. :idea: ;)

cu
Narses

wurzel - Do 27.09.07 11:52

Das klingt vernünftig, aber das Problem mit dem jede Liste mit Jeder ist noch nicht gelöst. Weil wenn ich es so wie du mache, dann hab ich ja nur die gleichen Einträge aus der 1. und 2. Liste und such damit die 3. ab. Macht für mich keinen Sinn, vllt gibt es ja in der 2. Liste Einträge die in der 3. sind, nicht aber in der 1.

ZeitGeist87 - Do 27.09.07 11:55

ganz einfach ;-)

rekursion ^^

wurzel - Do 27.09.07 11:59

Wenn du mir das jetzt noch erklärst ;)

ZeitGeist87 - Do 27.09.07 12:02

na klar ;-)

http://de.wikipedia.org/wiki/Rekursion

ich bastel dir mal n Beispiel..aber nur als denkanstoss^^
sonst krieg ich wieder ärger von Narses *g*

Narses - Do 27.09.07 12:04

Moin!

wurzel hat folgendes geschrieben:

Hm :? es handelt sich also nicht um eine Schnittmenge oder du weißt nicht, was "Schnittmenge" bedeutet... :nixweiss:

Vielleicht erklärst du nochmal kurz, WAS GENAU du eigentlich machen willst (z.B. mit sagen wir mal 3 oder 4 Listen); weil, diese Rekursionsgeschichte, das wird nicht ganz einfach... :|

cu
Narses

wurzel - Do 27.09.07 12:09

Also, im Moment habe ich 3 Listen, das woird in Zukunft aber über 60. Mein Programm soll nun die erste Liste nehmen, das mit allen anderen Listen vergleichen und mehrfache Einträge im Endeffekt in ne Datei mit Angabe in welcher Liste die Einträge gefunden worden sind. Dann wird die 2. Liste genommen und wieder mit allen anderen Listen verglichen und dann die 3. Liste und etc...Am Ende hab ich ne Liste, wo drin steht welcher Eintrag doppelt ist und in welcher Liste die Einträge zu finden sind.

ZeitGeist87 - Do 27.09.07 12:17

Suchen von doppelten Einträgen und Rückgabe dieser Einträge:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:

function getDoppelte(List1, List2: TStringList; var Dolist: TStringList): Boolean;
var i: Integer;
    doPos: Integer;
begin;

 getDoppelte:= false;

 //Datenprüfung
 if List1.Count = 0 then
  exit;

 if List2.Count = 0 then
  exit;

 doPos:= -1;
 for i:= 0 to list1.Count-1 do
 begin
  //Suche Eintrag
  doPos:= list2.IndexOf(list1.Strings[i]);
  //Eintrag vorhanden
  if doPos > -1 then //in DoppelteListe aufnehmen
   Dolist.Add(list1.strings[i] + ' (' + inttostr(doPos) + ')');
 end;

 getDoppelte:= true;
end;

Schnell geschrieben, sollte funktionieren..
Diese Funktion kannst du verwenden, um deine Rekursion aufzubauen.

LG
Stefan

Narses - Do 27.09.07 12:18

Moin!

OK, du willst also paarweise Duplikate auflisten. :think: Dafür brauchst du keine Rekursion, da reichen auch geschachtelte Schleifen. ;) Schau mal nach Suche in: Delphi-Forum, Delphi-Library

PERMUTATION, damit solltest du weiter kommen. :idea:

cu
Narses

ZeitGeist87 - Do 27.09.07 13:58

Testprogramm im Anhang..

Sogar ohne Rekursion ^^

Known "Bug":

Liste vergleicht sich mit sich selbst nochmal..

Horst_H - Do 27.09.07 13:59

Hallo,

mach es doch richtig kompliziert.
Siehe http://www.delphibasics.co.uk./RTL.asp?Name=TList
Du erstellst eine Liste aus Strings und einer Menge, die festhält, wo dieser String vorkommt, bei welcher Liste zuerst und wie oft.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

type
  // Meine ListenListe
  TAlleListe = class
    private
      // The data fields of this new class
      Eintrag  : String;
      Vorkommen : set of 0..255;
      PosErstesVorkommen : integer;
      Häufigkeit : Integer;
.....

Du fügst dieser neue Liste neue Werte zu(AlleList.insert(Eintrag,ListenNummer) muss selber komponiert werden) und achtest dabei darauf , ob es diesen Eintrag schon gibt.
Wenn nein dann
Eintrag eintragen,(sortiert am besten, und testen das Listennummer nicht > 255 wird, sonst TBits verwenden)
Listennummer in Vorkommen eintragen
ErstesVorkommen auf Listennummersetzen
Häufigkeit auf 1
sonst
Listennummer in Vorkommen eintragen
Häufigkeit erhöhen

Dadurch hast Du dann eine Liste, die nur einmal jede Liste einliest (und nicht n*(n-1)~n^2 , z.B 60 statt 3600) und schlußendlich alle Einträge enthält mit Angabe der Liste in der dieser Eintrag zuerst vorkam und in welchen Listen er zu finden ist.

Ich hoffe, das war nicht zu wüst.

Gruß Horst

P.S.
n^2 und nicht n! Permutation ist ja nicht nötig...

wurzel - Do 27.09.07 14:33

ZeitGeist87 hat folgendes geschrieben:

Testprogramm im Anhang..

Sogar ohne Rekursion ^^

Known "Bug":

Liste vergleicht sich mit sich selbst nochmal..

Hey danke, sowas hab ich gebraucht. Und der Quellcode ist auch verständlich, aber ich werde ihn mir nochmal genauer angucken.

wurzel - Fr 28.09.07 11:11

Ich hatte da ne Idee...man könnte ja i mit i2 vergleichen. Wenn i = i2, dann soll er i2 um 1 erhöhen. Aber das klappt nicht, da ich ne Variable einer FOR-Schleife nicht einfach so ändern kann. Wie kann ich das umgehen? Weil damir hätte ich den Vergleich mit sich selbst ausgeschaltet

ZeitGeist87 - Fr 28.09.07 11:17

while oder repeat..until

LG
Stefan

jaenicke - Fr 28.09.07 11:19

wurzel hat folgendes geschrieben:

Es gibt Continue, damit wird die Schleife sofort mit dem nächsten Durchlauf fortgesetzt ohne den weiteren Code der aktuellen Schleife auszuführen. Vielleicht geht das damit, ich habe mir den Code nicht angesehen.

ZeitGeist87 - Fr 28.09.07 11:22

jaenicke hat folgendes geschrieben:

wurzel hat folgendes geschrieben:

stimmt...

Delphi-Quelltext

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

 if listbox1.items.strings[i] = listbox1.items.strings[i2] then
  continue
 else
 begin
  //Untersuchung
 end;

LG
Stefan

wurzel - Fr 28.09.07 12:25

Und wie's läuft :D

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:

procedure Tmainform.Button2Click(Sender: TObject);
var l1, l2: TStringList;
    bl: TStringList;
    i, i2: Integer;
begin
 //Listen erzeugen
 l1:= TStringList.Create;
 l2:= TStringList.Create;
 bl:= TStringList.Create;

 for i:= 0 to listbox1.Items.Count-1 do
 begin
  l1.LoadFromFile(listbox1.items.strings[i]);
  i2 := 0;
  repeat
  begin
   if i2 = i then
    i2 := i2 + 1;
   if i2 > listbox1.Items.Count -1 then
    exit;
   memo1.Lines.Add('Vergleiche: ' + listbox1.Items.Strings[i] + ' mit ' + listbox1.items.strings[i2]);
   memo1.lines.add('');
   l2.loadfromfile(listbox1.items.strings[i2]);

   bl.Clear;

   if getDoppelte(l1, l2, bl) then
    begin
     if bl.Count <> 0 then
      memo1.Lines.add(bl.Text)
     else
      memo1.Lines.add('Kein doppelten Einträge');
    end;

   memo1.lines.add('=====================================================');

   i2 := i2 + 1;
  end; //repeat
 until (i2 = listbox1.Items.Count);
 end;   //for i:= 0 to listbox1.Items.Count-1 do

 l1.Free;
 l2.Free;
 bl.Free;
end;

THX

Horst_H - Fr 28.09.07 13:21

Hallo,

wird hier nicht doppelt untersucht?
1 mit 3 und später 3 mit 1
(Man denke an BubbleSort: was ich schon weiß, brauche ich nicht nochmals abfragen )

Es reicht doch

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

For i1 := 0 to DateiListe.count-2 do
  begin
  Einlesen Datei i1
  For i2 := i1+1 to DateiListe.count-1 do
    begin
    Einlesen Datei i2
    Aufdopelte testen
    end;
  Ausgeben;
  end;

Gruß Horst

Nachtrag:
neue getDoppelte Funktion

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:

function getDoppelte(List1, List2: TStringList; var Dolist: TStringList): Boolean;
var i,j: Integer;
begin;

 getDoppelte:= false;

 //Datenprüfung
 if List1.Count = 0 then
  exit;

 if List2.Count = 0 then
  exit;

 //Original Zeilennummer in der Objects Eigenschaft merken
 //und anschliessend sortieren
 for i:= 0 to list1.Count-1 do
   list1.Objects[i] := Pointer(i);
 list1.Sort;

 for i:= 0 to list2.Count-1 do
   list2.Objects[i] := Pointer(i);
 list2.Sort;

 i :=list1.count-1;
 j:= list2.count-1;
 {
 Jetzt pendelnd suchen:
 Wiederhole
   Solange List1 Element größer runterwandern,
     Bei Gleichheit eintragen
  wechseln zur list2 und ebenso runterwandern
     Bei Gleichheit eintragen
 bis Eine Liste komplett abgeklappert ist
 }
 repeat
   while (i>=0) AND (list1[i]>list2[j])  do
     dec(i);

   IF i< 0 then
     break;

   iF list1[i]=list2[j] then
     begin
     //Jetzt die original Zeilennummern eintragen
     Dolist.Add(Format('%.5d %.5d'+#13#10+'1: %s'+#13#10+'2: %s',[Dword(list1.Objects[i]),Dword(list2.Objects[j]),list1[i],list2[j]]));

     dec(i);
     IF i < 0 then
       break;
     end;

   while (j>=0) AND (list2[j]>list1[i])  do
     dec(j);

   IF j< 0 then
     break;

   If list1[i]=list2[j] then
     begin
     Dolist.Add(Format('%.5d %.5d'+#13#10+'1: %s'+#13#10+'2: %s',[Dword(list1.Objects[i]),Dword(list2.Objects[j]),list1[i],list2[j]]));
     dec(j);
     if j < 0 then
       break;
     end;
 until (i<=0) or (j<=0);
 dolist.sort;
 getDoppelte:= true;
end;


procedure Tmainform.Button2Click(Sender: TObject);
var l1, l2: TStringList;
    bl: TStringList;
    i, i2: Integer;
begin
 //Listen erzeugen
 l1:= TStringList.Create;
 l2:= TStringList.Create;
 bl:= TStringList.Create;

 // memo1.Lines.BeginUpdate;
 for i:= 0 to listbox1.Items.Count-1 do
 begin
  l1.LoadFromFile(listbox1.items.strings[i]);
  for i2:= i+1 to listbox1.items.count-1 do
    begin

   memo1.Lines.Add(Format('Vergleiche:%3d %s mit %3d %s',[i,listbox1.Items[i],i2,listbox1.Items[i2]]));
   memo1.lines.add('');
   l2.loadfromfile(listbox1.items.strings[i2]);

   bl.Clear;

   if getDoppelte(l1, l2, bl) then
   begin
    if bl.Count <> 0 then
     memo1.Lines.addstrings(bl)
    else
     memo1.Lines.add('Kein doppelten Einträge');
   end;

   memo1.lines.add('=====================================================');
  end;
 end;
 //memo1.Lines.EndUpdate;

 l1.Free;
 l2.Free;
 bl.Free;
end;