Autor Beitrag
LuMa86
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 76



BeitragVerfasst: Do 20.02.14 22:48 
Hallo,
Arrays zusammenführen ist ja einfach, allerdings würde ich gerne folgendes realisiern:
Ich habe 2 statische Arrays. Das erste ist eine Art "Sammelstelle", welche im 60-Minuten Takt abgearbeitet wird. Auf dieses Array werden alle 10-30 Sekunden Einträge aus dem zweiten Array, einer Art "Puffer", draufgepackt. Jetzt kann es aber vorkommen, das manche Einträge sowohl auf der Sammelstelle, als auch im Puffer sind, und somit doppelt oder mehrfach auftreten würden. Es gab mal für StringLists eine Unit (ich glaube in der CodeLib der DP) welche so eine Funktion parat hatte. Gibt es sowas vllt. auch für Arrays? Vllt. hatte mal jemand das selbe Problem :)

Ansonsten muss ich es manuell zusammenbasteln.

Gruß


Moderiert von user profile iconNarses: Topic aus Sonstiges (Delphi) verschoben am Do 20.02.2014 um 23:58
Narses
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Administrator
Beiträge: 10181
Erhaltene Danke: 1254

W10ent
TP3 .. D7pro .. D10.2CE
BeitragVerfasst: Fr 21.02.14 00:58 
Moin!

Hm, wie soll denn sowas allgemeingültig (ob nun in einer Unit oder sonstwo) gelöst werden können? :gruebel: "Ein Array" sagt doch nix über den Inhalt aus, und den musst du vergleichen, wenn du Duplikate erkennen willst. :idea: Gut, könnte man mit einer Vergleichsfunktion als Referenz abstrahieren, aber ob das so sinnvoll ist? :gruebel:

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.
ub60
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 762
Erhaltene Danke: 127



BeitragVerfasst: Fr 21.02.14 01:08 
Eine Stringliste hat eine Methode IndexOf, damit kann man nachfragen, ob bzw. an welcher Stelle ein String in der Liste vorkommt.
Eventuell kannst Du ja das statt Deines Arrays einsetzen.

ub60
Narses
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Administrator
Beiträge: 10181
Erhaltene Danke: 1254

W10ent
TP3 .. D7pro .. D10.2CE
BeitragVerfasst: Fr 21.02.14 01:12 
Moin!

@user profile iconub60:
Eine Stringliste kannst du auch gleich so konfigurieren, dass Duplikate gar nicht erst angenommen werden. :idea: ;)

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.
Xion
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
EE-Maler
Beiträge: 1952
Erhaltene Danke: 128

Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
BeitragVerfasst: Fr 21.02.14 12:12 
Wenn ich Duplikateliminierung höre, denke ich zuerst an Hashtabelle.

Je nachdem wie deine Daten aussehen, nimmst du ein deutlich größeres (idealerweise etwa doppelt so groß wie Elemente gesammelt werden sollen) Array für die Sammelstelle. Jeder Arrayeintrag erhält zusätzlich noch ein bit (frei/belegt).

Auslesen: Das Array durchlaufen und nur Einträge bearbeiten, wo belegt=true

Einfügen: Eine Hashfunktion auf deinen Auftrag ausführen, welchem diesem möglichst eindeutig einen Arrayindex zuweist. Dort dann den Auftrag reinschreiben. Kommt ein gleicher Eintrag wieder, wird wieder auf den selben Eintrag zugewiesen und es gibt keine Duplikate (es gibt da noch Feinheiten, wenn/weil die Hashfunktion nicht eindeutig ist).

Wenn du definierte Aufträge hast, dann ist es natürlich noch viel einfacher: Bit-Array anlegen, immer wenn ein Auftrag mit enstprechender ID ankommt, bit setzen.

Für Details müsste man genauer wissen, wie deine Daten aussehen.

_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)
WasWeißDennIch
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 653
Erhaltene Danke: 160



BeitragVerfasst: Fr 21.02.14 12:52 
Oder man sortiert die "Sammelstelle" und sucht mittels binärer Suche nach dem neu einzufügenden Eintrag. Nur, wenn kein entsprechender vorhanden ist, wird der Neueintrag vorgenommen. AFAIK entspricht das ziemlich genau der Vorgehensweise der TStringlist (diese muss ja auch sortiert sein, damit man Duplicates auf dupIgnore setzen kann).
LuMa86 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 76



BeitragVerfasst: Fr 21.02.14 17:12 
Also auf StringLists oder ähnliches umsteigen ist nicht möglich, da das Projekt wirklich uralt it und es zu aufwändig wäre, es komplett umzustellen, und nur wegen kleinen Anderungen lohnt sich eine "Neuauflage" auch nicht.

Es muss ja nicht allgemein gültig sein, allerdings habe ich folgendes Problem:

Die folgende Funktion wäre mit einem Array of String/Integer problemlos möglich (denke ich zumindestens). Mit meinem Array allerdings nicht:

ausblenden volle Höhe 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:
  
type
  TInetData = record
    ID, Port: Integer;
    Host, User : String;
  end;

  TInetArray = array of TInetData;

// Aufruf:
DeleteMultipleEntrys(TInetArray);

procedure DeleteMultipleEntrys(var AArray: TInetData);
var
  i, CurLength: Integer;
begin
  i := Succ(Low(AArray));
  if Length(AArray) > 0 then
    CurLength := 1
  else
    CurLength := 0;
  while i <= High(AArray) do
  begin
    if AArray[Pred(i)] <> AArray[i] then  // Fehler mit meinem "custom" Array!
    begin
      AArray[CurLength] := AArray[i];
      Inc(CurLength);
    end;
    Inc(i);
  end;
  SetLength(AArray, CurLength);
end;


Mit meinem "custom" Array bring die makierte Zeile allerdings einen Fehler. Deshalbsuche ich hierfür eine Lösung :)

[EDIT] Natürlich könnte ich es hier für alle Elemente des Records prüfen, allerdings wäre das bei 17 Elementen ein kleiner Aufwand und nicht sehr elegant :)

MfG
Narses
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Administrator
Beiträge: 10181
Erhaltene Danke: 1254

W10ent
TP3 .. D7pro .. D10.2CE
BeitragVerfasst: Fr 21.02.14 19:03 
Moin!

Du hast da mehrere "Probleme", würde ich sagen:
  • Das ständige Ändern der Array-Größe per SetLength() ist gar keine gute Idee! :shock: Damit hast du in nullkommanix deinen Speicher zerstückelt. :?
    :arrow: So machen, wie Delphi auch: eine gut geschätzte Größe am Anfang wählen und mit einem Belegungszähler/Zeiger verwalten. Nur bei Bedarf das Array tatsächlich größer machen (und dann ordentlich, Daumen: +1/4)
  • Wenn man strukturierte Daten vergleichen will und es nur auf die Gleichheit ankommt, dann bildet man bei der Anlage zusätzlich einen Hashwert aus den Daten. Diesen kann man dann schnell vergleichen, ohne alle Daten berücksichtigen zu müssen. :idea:
cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Sa 22.02.14 11:25 
Hallo,

man kann sich jetzt ( das EDIT kam ja etwas spät ) auch mal die "Dimension" des Problems vor Augen führen.
Alle 10..30 Sekunden 17 Einträge sind maximal ( 17/10 *3600 ) 6120 in einer Stunde.Da ist selbst eine unsortierte Liste schnell durchzusehen und sie die Daten blieben dabei chronologisch.
Wären Host und User vom Typ ShortString könnte man Comparemem benutzen.
ausblenden volle Höhe 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:
type
  TInetData = record
    ID, Port: Integer;
    Host, User : String;
  end;

  TInetArray = array of TInetData;

function CheckEqualInetData(const a,b: TInetData): boolean;
begin
  result := false;
  // Anordnung der Abfragen so, dass die Ungleichheit möglichst frueh erkannt wird
  IF a.ID <>b.ID then
    EXIT;  
  IF a.Port <>b.Port then
    EXIT;  
  IF a.Host <>b.Host then
    EXIT;  
  IF a.User <>b.User then
    EXIT;  
  result := true;
end;

function CheckPosInList(const aArr:TInetArray,const aItem: TInetData):integer;
begin
 //Von oben nach unten suchen ist wahrscheinlich wahrscheinlicher ;-)
  For result := High(aArr) downto 0 do
    // Bei Gleichheit einfach beenden
    IF CheckEqualInetData(aArr[result],aItem) then
      EXIT;  
//Nichts gefunden
  result := -1;
end;

procedure InsertNewItem(var aArr:TInetArray;const aItem : TInetData);
var
  i : integer;
begin
  IF CheckPosInList(aArr,aItem) < 0 then
  begin
    i := length(aArr);
    setlength(aArr,i+1);
    aArr[i]:= aItem;
  end;
end;


Gruß Horst
[Edit]
www.delphipraxis.net...le-wie-benutzen.html könnte noch helfen.
Ich habe mal versucht, es mittels zweier separater Listen und HashWerte, um schneller "rehashen" zu können, und deren Zuordnung zu machen.Als Gag mit Widestrings, die sind immer solitär, da sie keinen Referenzzähler haben, brauchen aber gewaltig an Platz ( ich schätze 20 Byte( 32 bei Delphi ) overhead pro String).
Mit einem CRC32 als Hashwert Mod aktuelle Größe komme ich auf ~1 Sekunde für 2178309 Items ( 330 MB ) , wobei vorher diese Zahl bekannt ist.Es muss also nur der Hashwert berechnet und die Strings kopiert werden.Die Items unterscheiden sich nur in der ID.
HashWert = ID -> nie Kollision.
Hashwert = Port= konst -> immer Kollision Lineare Liste
Hashwert = CRC32 -> 36% Kollision bei Anzahl Items= Länge Hashliste, aber maximale Länge der Liste ist bei 2 Mio zum Beispiel nur 7.
Ich wollte vermeiden, dass wie bei csDictionary Kopien der Daten erzeugt und ständig ein Hashwert berechnet werden muss.
Hier mal mit Zufallszahlen im Bereich der Elementeanzahl, was doch viele Doppelte ergibt, die aber nicht eingefügt werden:
ausblenden volle Höhe 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:
 Anzahl Elemente           2178309
 Groesze des Hash          2178309
 Belegung                   100,00%
 Speicherbelegung Item          16
 Speicherbelegung Hash          20
 Speicherbelegung String       144
 Gesamtspeicher Hash      ~  41,548 Mb
 Gesamtspeicher Daten     ~ 332,384 Mb
 Hash /  Daten               12,500%

 Versuchte Elemente            272288
 Eingefügte Elemente           256010
 Anzahl mehrere  Elemente       14205
 Anzahl doppelte Elemente       16278
 Anzahl Vollvergleiche          16278
 00.00.00.388
 relative Belegung              11,75%
 relative Anzahl Kollisionen     5,55%
 Maximale Kollisionslaenge          3
 Mittlere Kollisionslaenge       0,05

 Versuchte Elemente            544576
 Eingefügte Elemente           481930
 Anzahl mehrere  Elemente       49095
 Anzahl doppelte Elemente       62646
 Anzahl Vollvergleiche          62646
 00.00.00.377
 relative Belegung              22,12%
 relative Anzahl Kollisionen    10,19%
 Maximale Kollisionslaenge          4
 Mittlere Kollisionslaenge       0,10

 Versuchte Elemente           1089152
 Eingefügte Elemente           857583
 Anzahl mehrere  Elemente      147771
 Anzahl doppelte Elemente      231569
 Anzahl Vollvergleiche         231569
 00.00.00.737
 relative Belegung              39,37%
 relative Anzahl Kollisionen    17,23%
 Maximale Kollisionslaenge          6
 Mittlere Kollisionslaenge       0,15

 Versuchte Elemente           2178304
 Eingefügte Elemente          1377286
 Anzahl mehrere  Elemente      355296
 Anzahl doppelte Elemente      801018
 Anzahl Vollvergleiche         801018
 00.00.01.413
 relative Belegung              63,23%
 relative Anzahl Kollisionen    25,80%
 Maximale Kollisionslaenge          8
 Mittlere Kollisionslaenge       0,20
Einloggen, um Attachments anzusehen!