Daten auf Einzigartigkeit überprüfen...

[Nelphin]

Folgende Problemstellung:

ich möchte Daten im Format:

A B C B C A D F E A B C D A D

komprimiert kopieren indem ich die doppelten weglasse und eine indexliste mitpflege... (A B usw sind hier platzhalter für große Datenmengen, die aber gleich sein können)

also sollte sowas rauskommen:
A B C D F E

und in der Indexliste sollte dann stehen:

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


Mein bisheriger Ansatz ist es die ersten drei Einträge zu kopieren (die sind immer unterschiedlich) und dann in zwei ineinandergeschachtelten for schleifen die kommenden einträge mit diesen dreien zu vergleichen... sind sie identisch, dann schreibe ich in den index, das funktioniert auch... sind sie unterschiedlich, will ich den unterschiedlichen eintrag kopieren und von hier an mit den jetzt 4 bereits kopierten vergleichen... usw usw und genau da verlassen mich meine Anfänger Programmier und Experimentierkünste... ich bekomme es einfach nicht hin.

weiss jemand rat oder kann mir einen (für einen Anfänger verständlichen) Stubs in die richtige Richtung geben?

vielen Dank schonmal!

[Uwe Raabe]

Du sagst leider nicht, um was für Daten es sich bei A, B, C, ... handelt. Falls es Strings sind oder etwas, das man als String darstellen kann, bietet sich eine TStringlist an:

Delphi-Quellcode:

var
  daten: TStringlist;
  idx: Integer;
begin
  ...
  daten := TStringList.Create;
  { dupIgnore sorgt dafür, daß bei Add für bereits vorhandene Einträge der alte Index zurückgegeben wird }
  daten.Duplicates := dupIgnore;      
  for x in <Eingangsdaten> do begin  // Schleife über Datenmenge
    idx := daten.Add(x);
    <add Index (idx)>                // wie auch immer das aussehen soll
  end;
  ...
end;

[xZise]

Hallo,

sind die Blöcke denn alle gleich groß? Also bei Strings könnte man einfach das einfach mit IndexOf machen. Du gehst jeden Block durch. Bei jedem Block prüfst du mit IndexOf ob er schon existiert und fügst diesen als Index in eine Integerliste ein. Ansonsten fügst du den der StringList hinzu und fügst den Rückgabewert von .Add der IntList hinzu.

MfG
Fabian

[Reinhard Kern]

Zitat:

Zitat von Nelphin

Folgende Problemstellung:

ich möchte Daten im Format:

A B C B C A D F E A B C D A D

komprimiert kopieren ...

Hallo,

da stellt sich die Frage, was dann? Wenn es um komprimierte Speicherung geht, bist du mit den modernen ZIP und Nachfolgern am besten bedient, da die sowas erkennen und ausserdem in Bezug Effektivität und Geschwindigkeit viel ausgefuchster sind als du das auf Anhieb realisieren könntest. Du kannst allerdings die Daten nicht direkt wieder lesen, sondern nur mit der entsprechenden Software.

Gruss Reinhard

[Uwe Raabe]

Zitat:

Zitat von xZise

Also bei Strings könnte man einfach das einfach mit IndexOf machen. Du gehst jeden Block durch. Bei jedem Block prüfst du mit IndexOf ob er schon existiert und fügst diesen als Index in eine Integerliste ein. Ansonsten fügst du den der StringList hinzu und fügst den Rückgabewert von .Add der IntList hinzu.

Wie in meiner Antwort beschrieben, reduziert das Setzen von Duplicates auf dupIgnore das Ganze auf ein simples Add.

[Nelphin]

Zitat:

Zitat von Uwe Raabe

Du sagst leider nicht, um was für Daten es sich bei A, B, C, ... handelt. Falls es Strings sind oder etwas, das man als String darstellen kann, bietet sich eine TStringlist an:

Delphi-Quellcode:

var
  daten: TStringlist;
  idx: Integer;
begin
  ...
  daten := TStringList.Create;
  { dupIgnore sorgt dafür, daß bei Add für bereits vorhandene Einträge der alte Index zurückgegeben wird }
  daten.Duplicates := dupIgnore;      
  for x in <Eingangsdaten> do begin  // Schleife über Datenmenge
    idx := daten.Add(x);
    <add Index (idx)>                // wie auch immer das aussehen soll
  end;
  ...
end;

erstmal vielen dank für die antwort(en)...
da meine daten ursprünglich aus einer stringlist kommen und ich sie erst später in vektoren umbaue würde das funktionieren...

aber...

dupIgnore funktioniert irgendwie nur, wenn die stringlist vorher sorted wird und damit würfel ich die daten komplett durcheinander, ich brauche sie aber in der urpsrungsreihenfolge....

und das mit dem index rausschreiben habe ich nicht verstanden... denn wenn das funzen würde, könnte es sein das mir die reihenfolge egal sein kann... hauptsache in der indexliste stimmt sie wieder.

denn das hier

Delphi-Quellcode:

idx := daten.Add(x);

bringt mir nur den fehler Inkompatible Typen string und Integer...

zur zeit habe ich folgendes:

Delphi-Quellcode:

procedure TForm1.Button19Click(Sender: TObject);
var i:integer;
var idx:integer;

begin

slopt.clear;
slopt.Sorted:=true;   // ohne das geht es nicht, aber mit kann ichs nicht gebrauchen.... oder doch??
slopt.duplicates:=dupignore;
for i := 0 to sl.count - 1 do
   slopt.Add(sl[i]);
 //  idx := (slopt.Add(i)); // auskommentiert, weils nicht funktioniert...
end;

[Nelphin]

ok nachdem ich mit dupignore nicht weiterkam habe ich mir die Lösung mit IndexOf angeschaut... und etwas programmiert, das zwar macht was ich will aber viel zu langsam:

hier mein jetziger code:

Delphi-Quellcode:

procedure TForm1.Button23Click(Sender: TObject);
var
i:integer;
var start,dauer:Cardinal;
begin
start := GetTickCount();
  slopt.Clear;   //slopt leer machen
  setlength(optvarrayindfirst,sl.Count); //index array bekommt seine länge verpasst...
  for i := 0 to 2 do begin //die ersten drei elemente kopieren, da die sowieso immer unterschiedlich sind

       slopt.Add(sl[i]);
       optvarrayindfirst[i]:=i+1; //und im indexarray speichern
       end;


   for I := 3 to sl.Count - 1 do //für den rest

    if slopt.IndexOf(sl[i])=-1 then //prüfen ob es das element schon gibt...
    try
       slopt.Add(sl[i]);           // wenn nicht, hinzufügen
     finally begin
       optvarrayindfirst[i]:=slopt.count; // und index in indexarray schreiben
     end;
       end else begin
       optvarrayindfirst[i]:=(slopt.IndexOf(sl[i])+1); //wenn doch, dann die position davon ins indexarray schreiben
       end;
       dauer  := GetTickCount() - start;
       panel2.Caption:='reduziert auf '+inttostr(slopt.count)+' hat '+floattostr(dauer/1000)+' Sekunden gedauert';
  end;

Wie ihr seht habe ich die zeit gestoppt die diese aktion dauert... und muß leider sagen das ist unbrauchbar für meine fälle... ein mittelgroßer datensatz hat 20 minuten gebraucht um von 122760 zeilen auf 20438 zeilen runtergekürzt zu werden...

ich erwarte aber datenmengen mit weit über 1 millionen zeilen...

dupignore kürzt den selben datensatz in 0,8 sekunden, würfelt ihn mir aber gnadenlos durcheinander und ich bekomme das mit dem indexarray nicht hin, das brauche ich aber zwingend.

hier mein Ansatz mit DupIgnore:

Delphi-Quellcode:

procedure TForm1.Button19Click(Sender: TObject);
var i:integer;
var idx:integer;

var start,dauer:Cardinal;
begin
start := GetTickCount();

slopt.clear;
slopt.Sorted:=true;   // ohne das geht es nicht, aber mit kann ichs nicht gebrauchen.... oder doch??
slopt.duplicates:=dupignore;
for i := 0 to sl.count - 1 do
   slopt.Add(sl[i]);

//panel2.caption:=inttostr(slopt.Add(i)); // auskommentiert, weils nicht funktioniert...

   listbox4.Items.Add(inttostr(idx));  //
     dauer  := GetTickCount() - start;
       panel2.Caption:='reduziert auf '+inttostr(slopt.count)+' hat '+floattostr(dauer/1000)+' Sekunden gedauert';
  end;

hat jemand eine idee, wie ich das indexarray mit dupignore hinbekommen kann?

danke schonmal

[Khabarakh]

Zitat:

Zitat von Nelphin

ein mittelgroßer datensatz hat 20 minuten gebraucht um von 122760 zeilen auf 20438 zeilen runtergekürzt zu werden...

Bei O(n²) kein Wunder :) . Um auf lineare Laufzeit zu kommen, musst du dein Indexarray durch eine Hashmap ersetzen: http://www.delphipraxis.net/internal...ct.php?t=53653

[Nelphin]

Zitat:

Zitat von Khabarakh

Zitat:

Zitat von Nelphin

ein mittelgroßer datensatz hat 20 minuten gebraucht um von 122760 zeilen auf 20438 zeilen runtergekürzt zu werden...

Bei O(n²) kein Wunder :) . Um auf lineare Laufzeit zu kommen, musst du dein Indexarray durch eine Hashmap ersetzen: http://www.delphipraxis.net/internal...ct.php?t=53653

erstmal danke für die Antwort!

ich dachte schon ich hätte einen trick gefunden mein indexarray nach dem sorted dupignore kram mit dieser procedure nachträglich zu erstellen:

Delphi-Quellcode:

procedure TForm1.Button21Click(Sender: TObject);
var i,g:integer;
var tauscher:integer;
var start,dauer:Cardinal;
begin
start := GetTickCount();
slopt.Sorted:=false;
setlength(optvarrayindfirst,sl.count); //länge vom indexarray festlegen
for g := 0 to sl.Count - 1 do
 optvarrayindfirst[g]:=9999999; // sinnloses befüllen damit mich die 0en nicht verwirren... kann später entfallen.


for i := 0 to slopt.count -1 do begin
tauscher:=sl.indexof(slopt[i]); // prüfen wo der eintrag in der alten liste stand
  while tauscher<>-1 do   begin

  optvarrayindfirst[sl.indexof(slopt[i])]:=i; //im listarray an die gefundene stelle die stelle der neuen liste geben
  sl[sl.indexof(slopt[i])]:= 'tausch tausch';// damit beim zweiten indexof nicht die selbe stelle gefunden wird
  tauscher:=sl.indexof(slopt[i]);// nächste stelle suchen
  end;
end;

     dauer  := GetTickCount() - start;
       panel2.Caption:='Listindex nachziehn hat '+floattostr(dauer/1000)+' Sekunden gedauert';
  end;

aber das gleiche problem... funktioniert bei kleinen datenmengen gut, aber bei großen zu langsam.

also werde ich mir morgen das mit den hashlists mal anschaun *seufz* komplettes WE weg und nix hinbekommen...

[Uwe Raabe]

Dann versuch doch mal folgenden Trick - sollte lineare Laufzeit bringen:

Delphi-Quellcode:

var
  i: integer;
  idx: Integer;
  refArray: array of Integer;
  ref: Integer;
  start, dauer: Cardinal;
begin
  start := GetTickCount();
  setlength(optvarrayindfirst, sl.Count);
  setlength(refArray, sl.Count);
  slopt.Clear;
  slopt.Sorted := true;
  slopt.Duplicates := dupIgnore;
  { als Referenz wird die Position im Original gespeichert }
  for i := 0 to sl.Count - 1 do begin
    { nur wenn der String noch nicht existiert, wird Objects belegt }
    idx := slopt.AddObject(sl[i], TObject(i));
    optvarrayindfirst[i] := Integer(slopt.Objects[idx]);
  end;

  { Hier wird ein temporäres Array zum Auflösen der Referenzen angelegt }
  for I := 0 to slopt.Count - 1 do begin
    ref := Integer(slopt.Objects[I]);
    refArray[ref] := I;
  end;

  { Nun könnnen wir die Referenzen auflösen }
  for I := 0 to Length(optvarrayindfirst) - 1 do begin
    optvarrayindfirst[I] := refArray[optvarrayindfirst[I]];
  end;

  dauer := GetTickCount() - start;
  Panel2.Caption := 'reduziert auf ' + inttostr(slopt.Count) + ' hat ' + floattostr(dauer / 1000)
    + ' Sekunden gedauert';

end;