Sets durchlaufen

[RSE]

Hallo,

Ich habe ein Set of Char und möchte nun für jedes Element in dem Set etwas tun. Die lauffähige und langsame Variante sieht so aus:

Delphi-Quellcode:

  for c := Low(Char) to High(Char) do
    if c in MyCharSet then
      Tuewas(c);

Effizienter wäre es natürlich, wenn man gar nicht erst jedes irgend mögliche Element auf Zugehörigkeit zum Set prüfen müsste, sondern gleich direkt das Set durchlaufen würde. Intern liegt dem Set ja ein ordinaler Typ zugrunde, der eine Ordnung hat. Diese Ordnung könnte man theoretisch dazu nutzen, um ein Element nach dem anderen zu durchlaufen. Aber wahrscheinlich ist diese Möglichkeit unerwünscht, da sie sich nicht an die Semantik eines Sets als Menge ohne Ordnung hält.

[jfheins]

Zitat:

Zitat von RSE

Die lauffähige und langsame Variante sieht so aus: ...

Langsam??
Ein set kann doch eh nur 256 Elemente beinhalten - so langsam kann das doch nicht sein?
Und nein, sowas wie du es dir vorstellt gibt es imho nicht - ein Set besteht ja auch nur aus 8 Byte, in denen für jedes Element ein Bit angibt, ob es drin ist oder nicht. Die Bits da rauszuwurschteln dürfte auch wieder darauf hinauslaufen, dass man alle durchgeht und prüft ob sie drin sind.

Was natürlich geht, ist: Du machst dir eine Liste, in der alle Elemente drin sind, die auch im Set drin sind.

[himitsu]

Ein SET hat intern keinen Ordinalen Type ... ein SET ist eine Reihe von Bits.
Der ENUM (die Elemente des SETs) sind ordinalen Typs.

Zitat:

Zitat von RSE

Diese Ordnung könnte man theoretisch dazu nutzen, um ein Element nach dem anderen zu durchlaufen.

Rate mal, was deine Schleife macht?

Ja, es gäbe (wenn das SET nicht zu voll ist) eine kleine Optimierungsmöglichkeit, aber bei nur 256 Werten bringt das fast garnichts, da diese 256 Möglichkeiten alleine schon sehr schnell durchgelaufen sind.

(Bei meinem größeren WideCharSet sah das schon anders aus, denn da gibt es schon über 65.000 Möglichkeiten, wo sich soeine Optimierung schon eher anbot.)

PS: in neueren Delphis ginge auch sowas,

Delphi-Quellcode:

for c in MyCharSet do

welches theoretisch deiner FOR+IF-Schleife entspricht.

Zitat:

Zitat von jfheins

ein Set besteht ja auch nur aus 8 Byte, in denen für jedes Element ein Bit angibt, ob es drin ist oder nicht.

8 Integer/LongInt aka 32 Byte

[mkinzler]

Zitat:

Rate mal, was deine Schleife macht?

Nein, er hat eine Schleife über die möglichen Elemente

[RSE]

Zitat:

Zitat von jfheins

Ein set kann doch eh nur 256 Elemente beinhalten

Das wusste ich nicht, ich dachte, man könnte auch z.B. Set of Integer definieren. Dann wäre das Durchlaufen von rund 4 Milliarden Werten schon langsam. Vor allem, wenn im Set letztlich nur 3 Werte drinstehen.

Zitat:

Zitat von himitsu

Ein SET hat intern keinen Ordinalen Type ... ein SET ist eine Reihe von Bits.

OK, eine Reihe von Bits muss man nicht unbedingt als Ordinal ansehen, aber darin hat jedes Bit seine Position, sie haben also eine Ordnung.

Zitat:

Zitat von himitsu

Zitat:

Zitat von jfheins

ein Set besteht ja auch nur aus 8 Byte, in denen für jedes Element ein Bit angibt, ob es drin ist oder nicht.

8 Integer/LongInt aka 32 Byte

Mein Delphi 5 sagt, dass ein Set maximal 256 Elemente enthalten kann. Offenbar liegt also ein (maximal) 256 Bit langer Bitstring dahinter, 256 Bit = 8 * 32 Bit, somit hat himitsu hier offenbar Recht.

Ich werde mich einfach mit meiner doch nocht so langsamen Lösung begnügen :zwinker:

[himitsu]

Zitat:

Zitat von RSE

Das wusste ich nicht, ich dachte, man könnte auch z.B. Set of Integer definieren.

Nee, die 256 sind schon das Maximum, darum gibt es ab Delphi 2009 ein Problem mit dem Set of Char, da dort alles Unicode ist.

Bis Delphi 2007 ist ein Set of Char ein Set of AnsiChar
und ab Delphi 2009 wäre es ein Set of WideChar, welches allerdings nicht geht. Eben wegen der 256er Byte-Grenze.

Die Adressierung der Bits wird direkt über einen Assembler-Befehl vorgenommen, und dieser unterstützt nur eine ByteAdresse.

Darum auch so umständliche CharSet-Ersätze, wie z.B. http://www.delphipraxis.net/internal...t.php?t=169966 .

[RSE]

Von welchem Typ ist dann eigentlich ['a', 'ß', '0']? Geht das ab D2009 auch nicht mehr? Dann würde ich das komplett umbauen... Ich hab auch im Moment einen sehr eigenartigen Fehler:

Delphi-Quellcode:

TKeys = record
  Keys: set of Char;
end;

TNeu = class
private
  FKeys: TKeys;
published
  property MyKeys: TKeys read FKeys write FKeys;
end;

Neu.MyKeys.Keys := [] // Fehler: Der linken Seite kann nichts zugewiesen werden

[mleyen]

Fehlt da nicht ein "property" vor 'MyKeys'? :gruebel:

[RSE]

Sorry, Tippfehler, das steht im Origionalquelltext natürlich drin ;-) fixed

[himitsu]

Zitat:

Zitat von RSE

Von welchem Typ ist dann eigentlich ['a', 'ß', '0']? Geht das ab D2009 auch nicht mehr?

Set of Char wird automatisch auf Set of AnsiChar gekürzt.

['a', 'ß', '0'] bleibt unter Delphi 2009/2010 ein AnsiCharSet, bzw. es gibt einen Typen dafür TSysCharSet.

Der ShortString, String[x] und das CharSet bleiben also weiterhin nur ANSI.

(darum auch der in Beitrag #6 verlinkte Code)

Zitat:

Zitat von RSE

Fehler: Der linken Seite kann nichts zugewiesen werden

Der Linken seite konnte hier noch nie was zugewiesen werden, nur daß die alten Kompiler es noch nicht gesagt hatten.

Dieses Verhalten wird auch immer mal wieder hier im Forum genannt.
Es wird entweder eine Getter oder eine Setter aufgerufen.
Neu.MyKeys.xxx ruft den Getter auf, damit weiter auf .Keys zugegriffen werden kann.

Delphi-Quellcode:

Neu.MyKeys.Keys := [];

// wird also zu

DemphiinterneTemporäreVariable := Neu.MyKeys;  // bzw. Neu.GetMyKeys
DemphiinterneTemporäreVariable.Keys := [];

Tja, und nun rate mal, was mit dem zugewiesenem Wert passiert?
Genau ... nix, denn die TempVar wird irgendwann wieder gelöscht und im Property ändert sich nix.
Und darum warnt jetzt Delphi davor.