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.

[RSE]

Also ist ein Record als Property auch nicht zu gebrauchen... Ich bau mir doch ´ne Klasse, damit kenn ich mich aus, da gibt´s keine bösen Überraschungen...

Zitat:

Zitat von himitsu

['a', 'ß', '0'] bleibt unter Delphi 2009/2010 ein AnsiCharSet

Und wenn man da nun Chars reinpackt, die im Ansi nicht drin sind? Meckert der Compiler? Oder ist der Quelltext weiter in Ansi codiert, so dass man auf diese Weise gar nix anderes erzeugen könnte? Was wäre, wenn ich mich richtig bemühe und sowas wie [#13, #56, #3423] schreibe (angenommen, dass man mit #3423 ein WideChar-Zeichen beschreiben kann).

[himitsu]

Per Standard sind die Units Ansi, aber man kann es umstellen
und falls Delphi beim Speichern Zeichen entdeckt, welche nicht in Ansi reinpassen, dann warnt es und fragt ob es das umstellen soll.
(wird dann meißt als UTF-8 kodiert)

Delphi-Quellcode:

var x: Set of Char;
begin
  x := ['a', '猇'];
  //    ^^^ Delphi weiß, daß es ein SET ist und macht 'a' somit zum AnsiChar
  if 'a' in x then ;
  // ^^^ hier ist 'a' allerdings per Standard ein WideChar und darum wird gemeckert
  // Delphi erfährt erst nach dem IN, daß dort ein SET kommt und kan darum das 'a' nicht anders behandeln
end;

Zitat:

[DCC Warnung] Unit3.pas(28): W1050 WideChar in Set-Ausdrücken auf ByteChar verkürzt. Ziehen Sie die Verwendung der Funktion 'CharInSet' aus der Unit 'SysUtils' in Betracht.

[DCC Warnung] Unit3.pas(30): W1061 Bei Umwandlung der angegebenen WideChar-Konstante (#$7307) in AnsiChar gehen Informationen verloren

[DCC Warnung] Unit3.pas(31): W1050 WideChar in Set-Ausdrücken auf ByteChar verkürzt. Ziehen Sie die Verwendung der Funktion 'CharInSet' aus der Unit 'SysUtils' in Betracht.

[RSE]

Also gibt es auch weiterhin nur Set of AnsiChar. Danke für den Test!