Im Array besonders schnell suchen???

[romber]

Hallo!

Ich habe für meine Zwecke einen neuen Typ definiert und jeder Variante zusätzlich eine Zahl zugewiesen.

Delphi-Quellcode:

type TMeinTyp = (mtVariante1 = 1,
                         mtVariante2 = 15,
                         mtVariante3 = 35,
                         ...
                         mtVariante25 = 455);

Am liebsten würde ich einen Set erstellen, der dann mehrere Varianten enthält. Ich könnte dann ganz einfach und schnell mit "if in set" prüfen, ob eine bestimmte Variante drin ist. Das problem ist, dass ein Set maximal 256 Elemente besitzen kann. Und obwohl ich nur 25 potenzielle Elemente habe, ist ein Set in meinem Fall nicht möglich, weil Integerwerte einiger Varianten über 256 liegen.

Mit bleibt wohl nichts anderes, als ein Array zu erstellen. Wie kann ich besonders schnell und resourcensparend überprüfen, ob sich ein Wert im Array befindet?

[Apollonius]

Mittlerweile gibt es in der Unit Classes die Klasse TBits, die einen Bitvektor beliebiger Länge darstellt. Ich weiß allerdings nicht, ab welcher Delphi-Version sie vorhanden ist.

[jfheins]

Du könntest entweder ein Array wie folgt deklarieren:

Array[TMeinTyp] of Boolean;

Sozusagen ein selfmade-Set - prüfen kannst du dann schnell, indem du den Boolean-wert checkst ;)

[romber]

Danke für die schnelle Antwort!

Und wie hilft mir diese Klasse?

[romber]

Zitat:

Zitat von jfheins

Du könntest entweder ein Array wie folgt deklarieren:

Array[TMeinTyp] of Boolean;

Sozusagen ein selfmade-Set - prüfen kannst du dann schnell, indem du den Boolean-wert checkst ;)

Das habe ich jetzt ein bisschen nicht verstanden. Wie kann ich in diesem Fall prüfen, ob z.B. mtVariante2 im Array ist?

[thkerkmann]

Zitat:

Zitat von romber

Hallo!

Ich habe für meine Zwecke einen neuen Typ definiert und jeder Variante zusätzlich eine Zahl zugewiesen.

Delphi-Quellcode:

type TMeinTyp = (mtVariante1 = 1,
                         mtVariante2 = 15,
                         mtVariante3 = 35,
                         ...
                         mtVariante25 = 455);

Am liebsten würde ich einen Set erstellen, der dann mehrere Varianten enthält. Ich könnte dann ganz einfach und schnell mit "if in set" prüfen, ob eine bestimmte Variante drin ist. Das problem ist, dass ein Set maximal 256 Elemente besitzen kann. Und obwohl ich nur 25 potenzielle Elemente habe, ist ein Set in meinem Fall nicht möglich, weil Integerwerte einiger Varianten über 256 liegen.

Mit bleibt wohl nichts anderes, als ein Array zu erstellen. Wie kann ich besonders schnell und resourcensparend überprüfen, ob sich ein Wert im Array befindet?

Du solltest dir ein Set und ein Lookup array erstellen.

Delphi-Quellcode:

  type
    TMeinTyp = (mtVariante1, mtVariante2, mtVariante3,... mtVariante25);
  const
    cMeinTypOrdinal: array[TMeinTyp] of integer = (1,15,35,...455);

dann kannst du ein Set erstellen, um die Varianten zu speichern und wenn Du deren Ordinalwert benötigst greifst Du auf das Lookuparray zu.

Gruss

[Satty67]

[OT]Wenn ich das LookUp-Array sehe, muss ich an den Design-Fehler von QuickReport denken.[/OT]

[Apollonius]

Zitat:

Zitat von romber

Danke für die schnelle Antwort!

Und wie hilft mir diese Klasse?

Nun, ein Set ist letztlich auch nur ein Bitvektor. Um ein Element zum Set hinzuzufügen, setzt du das Bit mit der Position Cardinal(Element) und anstatt des in-Operators prüfst du den Status des Bits.

[Satty67]

Da seine Mengen-Elemente aber Unterschiedliche Werte haben (die er wohl braucht), wird er um ein LockUp-Array auch nicht rum kommen. Da kann er es einfacher lösen, wie thkerkmann vorgeschlagen hat.

[Apollonius]

Diesen Gedankengang verstehe ich nicht ganz.

[himitsu]

ich würde das Array dann nur andersrum anlegen

Delphi-Quellcode:

TMeinTypInternal = 1..25;
cMeinTypOrdinal:*array[0..455] of TMeinTyp
   = (0,1,0,0,0,0,0,...,0,0,0,2,0,...,0,3,...25);
//      ^1                    ^15       ^35  ^455
TMeinTyp = Set of TMeinTypInternal;

in cMeinTypOrdinal müssen dann nur an den entsprechenden Stellen (entsprechend der Zahlen seiner Varianten) durchnummeriert die Werte des Sets stehen

und dann

Delphi-Quellcode:

if cMeinTypOrdinal[zahl] in cMeinTyp then

[thkerkmann]

Zitat:

Zitat von himitsu

ich würde das Array dann nur andersrum anlegen

Delphi-Quellcode:

TMeinTypInternal = 0..24;
cMeinTypOrdinal: array[0..455] of TMeinTyp  = (1,0,0,0,0,0,...,0,0,0,15,...);
TMeinTyp = Set of TMeinTypInternal;

in cMeinTypOrdinal müssen dann nur an den entsprechenden Stellen die Zahlen seiner Varianten stehen

und dann

Delphi-Quellcode:

if cMeinTypOrdinal[zahl] in cMeinTyp then

Das ist genau das, was ich vermeiden wollte - ein grosses Array, welches nur zu einem geringen Teil gefüllt ist.
Ausserdem ist das Array jetzt redundant, da an der indexposition jeweils der index abgespeichert ist.

[OT] ich muss grad an die Negation denken [/OT]

[himitsu]

ja, sind aber "nur" 456 Bytes :roll:

und wenn du man das Array andersrum (siehe dein Code) anlegt, dann muß man erst das Array durchsuchen und so den Wert darin finden ... so könnte man aber direkt über den Wert umrechnen.

[Satty67]

Zitat:

Zitat von Apollonius

Diesen Gedankengang verstehe ich nicht ganz.

Ich vestehe die Aufgabe so, das er z.B. einmal Mengen-Element Nr.3 gesetzt und Mengen-Element Nr.3 = 455 haben will. Mit TBits alleine fehlt ja die Information, das Element Nr.3 den Wert 455 hat.

[thkerkmann]

@himitsu:
Will er (der TE) doch gar nicht.

Er hat diese Set Elemente und verwaltet damit ob eine Variante verwendet wird oder nicht.
Das geht dann sehr schnell mit in.
Wenn man aber jetzt den Ordinalwert (wozu auch immer) benötigt, kann mit z.B.

Delphi-Quellcode:

  i := cMeinTypOrdinal[mtVariante3];

abrufen.

Für Deinen Ansatz kann ich mir im Moment gar keine Anwendung vorstellen.

Gruss

[Klaus01]

Guten Abend,

sind die einzelnen Werte nicht berechenbar:

01 -> 1
02 -> 15 (index -2) * 20 + 15
03 -> 35 (index -2) * 20 + 15
04 -> 55
05 -> 75
..
25 -> 455 (index -3) *20 +15

könnte man sich dadurch nicht ein Set oder Array ersparen?

Grüße
Klaus

[jfheins]

Zitat:

Zitat von romber

Zitat:

Zitat von jfheins

Du könntest entweder ein Array wie folgt deklarieren:

Array[TMeinTyp] of Boolean;

Sozusagen ein selfmade-Set - prüfen kannst du dann schnell, indem du den Boolean-wert checkst ;)

Das habe ich jetzt ein bisschen nicht verstanden. Wie kann ich in diesem Fall prüfen, ob z.B. mtVariante2 im Array ist?

AAlso: Code ungefähr wie folgt (ist ausm Gedächnis in den Browser geschieben)

Delphi-Quellcode:

type TMeinTyp = (mtVariante1 = 1, 
                         mtVariante2 = 15, 
                         mtVariante3 = 35, 
                         ... 
                         mtVariante25 = 455);

TMeinSet = Array[TMeinTyp] of Boolean;


procedure whatever 
var
  MeinSet: TMeinSet;
begin
// setzen
Meinset[mtVariante3] := true;

// prüfen
if meinset[mtVariante3] then ...
end;

Ich weis aber nicht, ob das auch auf ein großes Array mit wenigen benutzten Elementen hinausläuft ...