2 dimensionale sets?

[dajuhsa]

ist es möglich eine Liste von Koordinaten zu erstellen?
Also eine bessere alternative zu

Delphi-Quellcode:

XYInListeEnthalten: Array[0..9,0..9] of Boolean;

//oder

XYListe: set of [0..99];

sowas wie set of set sozusagen.
ist so etwas möglich?

[DeddyH]

AFAIK ist ein Set kein Ordinaltyp, somit geht das nicht.

[Namenloser]

Sagen wir du hast den typen

Delphi-Quellcode:

tMySet = set of char

und

Delphi-Quellcode:

tMySetSet = set of tMySet

Jetzt machst du eine Variable SetA mit den inhalten ['A','b','Y','2'] und prüfst, ob dieses Set in einem tMySetSet enthalten ist :gruebel:
Hab ich das richtig verstanden? Was sollte der Sinn sein? Oder steh ich jetzt irgendwie aufm Schlauch?
Glaub nicht, dass das geht, und mir erschließt sich der Sinn irgendwie nicht.

[dajuhsa]

ich meine:

mit einem
set of [0..9]
kann man genausoviel anfangen wie mit einem
array[0..9] of boolean.

mit einem
XYZ
kann man soviel machen wie mit einem
array[0..9,0..9] of boolean;

die frage: was ist ein XYZ

[3_of_8]

So geht das nicht. Ich würde hier ein Hashset verwenden, dann brauchst du nur eine zweidimensionale Hashfunktion. Alternativ geht auch eine Bitvektor mit einer Zuordnungsfunktion, die deine zwei Koordinaten umrechnet. D.h. du verwendest sowas wie TBits und wenn du sehen willst, ob (X|Y) enthalten ist, fragst du den Wert Y*Width+X ab.

[dajuhsa]

aha,äähm..leichtes ( :freak: ), aber ich denke ich weiß was du meinst.
Danke für den tipp aber dann nehm ich doch lieber das 2D-Boolean-Array :)

[3_of_8]

Nur so nebenbei: Bei einem Bitvektor wäre der Speicherverbrauch um den Faktor 32 geringer.

[dajuhsa]

sry aber ich hab keine ahnung was ein bitverktor is *schamvoll in der ecke verkriech :oops: *

[3_of_8]

Ein Bitvektor ist im Prinzip das, was die Pascal/Delphi-Sets machen oder auch die Klasse TBits: Man benutzt einfach einzelne Bits, um einen Boolean-Wert zu speichern.

In einem 32-Bit-Cardinal hat man z.B. 32 Bits, kann also 32 Booleans darin kodieren. Realisiert wird das über die binären Operatoren von Delphi.

Zum Abfragen eines Bits verwendet man sowas:

Delphi-Quellcode:

function GetBit(const Vector, Index: Cardinal): Boolean;
begin
  Result:=Vector and (1 shl Index)>0;
end;

Und zum Setzen:

Delphi-Quellcode:

procedure SetBit(var Vector: Cardinal; const Index: Cardinal; const Value: Boolean);
begin
  if Value then
    Vector:=Vector or (1 shl Index)
  else
    Vector:=Vector and not (1 shl Index);
end;

[Namenloser]

Ich versteh immer noch nicht, was ein 2 dimensionales Set bringen soll. Ein Set ist dazu da, um zu prüfen, ob ein Wert in einer Menge enthalten ist. Dabei ist es doch ganz egal, ob die Menge eindimensional, zweidimensional, dreidimensional, dreickig, viereckig oder rund ist :gruebel:

[add] ich glaub ich halt mich lieber hier raus, da ich wohl irgendwie auf dem Schlauch stehe... [/add]

[3_of_8]

Hat er doch oben geschrieben: Er will eine Menge, in der er (kartesische) Koordinaten speichern kann. In einem normalen Set kannst du nur ordinale Typen speichern, und Koordinaten der Form (x|y) sind nunmal nicht ordinal, weder in Delphi noch in der Mathematik. ;)

[Apollonius]

Wenn die Koordinaten Bytes oder Words sind, dann könnte man nach Word bzw. DWord casten und hätte einen Ordinaltypen. Ich verstehe nicht, warum Delphi die Byte-Grenze fordert. Die Assembler-Befehle würden auch über einen größeren Bereich funktionieren.

[3_of_8]

Klar kann man das so machen. Bei Words hat man dann aber sogar bei Bitvektoren einen Speicherverbrauch von 128 MB.

[alzaimar]

Zitat:

Zitat von Apollonius

Ich verstehe nicht, warum Delphi die Byte-Grenze fordert.

Tut Delphi doch gar nicht. Such mal nach TBits in der OH. Wenn Du Delphi wegen der Fehlenden Unterstützung für beliebig große Sets geißeln willst, dann bitte auch wegen der fehlenden Unterstützung für beliebig lange Zahlen und Fießkommazahlen mit beliebig vielen Nachkommastellen.

[3_of_8]

Beliebig lange Gleit(!)kommazahlen geben die gängigen Prozessoren nicht her, beliebig lange (bzw. fast beliebig lange) Sets schon. Die Bytegrenze ist vermutlich ein Relikt aus alten Zeiten.

[Apollonius]

@Alzaimar: Ich meinte aber mit Sprachunterstützung, also Operatoren für Element enthalten (in lässt sich nicht einmal überladen), Vereinigung, Schnittmenge etc.

[alzaimar]

Wieso heißen die auf einmal Gleit(!)kommazahlen? Also 'Gleitkomma' kenn ich ja, aber was willst Du mir mit dem Emoticon '(!)' nur mitteilen? :gruebel:

Eine effiziente Implementierung der Set-Operationen (insbesondere der Speicherung) ist ohne Kenntnis der Obergrenze imho nicht möglich. Und da stellen 256 Elemente eine praktikable Obergrenze dar.

@Appolonius: Ich weiss, aber 'Include (S,x)' sollte doch sowieso dem 'S := S + [x]' vorgezogen werden, also was solls.

[3_of_8]

Weil du "Fließkommazahlen" geschrieben hast, was falsch ist. ;)

Und der Compiler kann die Obergrenze ja leicht ermitteln, indem er sich das größte Element ansieht.

[Namenloser]

Also Wikipedia leitet bei "Fließkommazahl" auf "Gleitkommazahl" weiter. Von daher würde ich mal darauf schließen, dass das als Synonym zu verstehen ist.

[3_of_8]

Cum hoc ergo propter hoc?

Oder anders gesagt: Du schließt falsch. Du solltest den Artikel schon weiterlesen. Im ersten Satz steht:

Zitat:

Eine Gleitkommazahl (auch Gleitpunktzahl oder Fließkommazahl als falsche Übersetzung aus engl. floating point number)

[alzaimar]

Zitat:

Zitat von 3_of_8

Weil du "Fließkommazahlen" geschrieben hast, was falsch ist.

Echt? Also, ich kenn das seit meinem Studium, in meinen Büchern als Fließkomma, Google spuckt fast so viele Artikel zu 'Fließkomma' aus, wie zu 'Gleitkomma'. Ich denke mal, ich schließe mich den fast 50% Dummen an, die eine falsche Ausdrucksweise verwenden.

Zitat:

Zitat von 3_of_8

Und der Compiler kann die Obergrenze ja leicht ermitteln, indem er sich das größte Element ansieht.

Äh, woher weiss er das? Das größte Element, das die Menge enthalten wird, ist zur Kompilierzeit nichtbekannt. Wie groß soll der Speicherbereich werden? Oder meinst Du allen Ernstes, das Delphi sowas unterstützen sollte?

Delphi-Quellcode:

Var 
  X : Set Of Int64; // Das wird ganz schön groß.
  Y : Set Of TObject; // Das auch.

[3_of_8]

Nein, tue ich nicht. TObject ist kein Ordinaltyp, Int64 auch nicht (zumindest nicht in 32 Bit-Delphi). Spätestens bei Cardinal sollte Schluss sein, das sind ja bereits 128 MB pro Set. Aber zumindest Words sollten drin sein.

Aber der Compiler kann definitiv die Obergrenze sehen, in dem Fall ist es zum Beispiel high(Cardinal).

[Apollonius]

Das sehe ich auch so. Die Koordinaten-Tupel müsste man eben in den entsprechenden Ordinaltyp casten, wie ich bereits in Post 12 vorgeschlagen habe.

[3_of_8]

Was dann aber zu unnötigem Speicherverbrauch führen kann. Eine Hashset-Implementation oder eine sortierte Liste von Sets oder sogar eine sortierte Liste von getaggten, sortierten Listen von Integern könnte hier sinnvoller sein. Dann kann man immerhin in logarithmischer Zeit nach Koordinaten suchen.

[alzaimar]

@3_of_8, @Apollonius:Meint ihr allen Ernstes, daß ein 128MB großer Basistyp in einer seriösen Programmiersprache etwas zu suchen hat? Aber ich sehe gerade, ihr widmet euch wieder dem Thema, bei dem mit 3_of_8's Vorschlag eigentlich die optimale Lösung vorgeschlagen wurde. Man kann ja die X-Koordinate in den höherwertigen 16/32-bit ablegen, die Y-Koordinate in den unteren. Dann kann man aufs Casten verzichten und mappt mit einfachen MOD in die Hashmap.

[3_of_8]

Wenn array[Cardinal] of <Typ> geht, warum nicht set of Cardinal? Letzteres ist sogar kleiner.

[alzaimar]

@3_of_8: Gähn.

[3_of_8]

Was heißt da gähn? Nach deiner Begründung dürfte array[Cardinal] ja auch nicht gehen und der Compiler müsste da dann auch eine Obergrenze setzen.

[alzaimar]

Zitat:

Zitat von 3_of_8

Was heißt da gähn? Nach deiner Begründung dürfte array[Cardinal] ja auch nicht gehen und der Compiler müsste da dann auch eine Obergrenze setzen.

'Gähn' ist deutsch und eine Lautmalerei. Ich wollte damit zum Ausdruck bringen, das mich deine Rechthaberei langweilt.

Von mir aus ist 'SET OF CARDINAL' ein wichtiger Datentyp, der unverständlicherweise in ObjectPascal und allen anderen Programmiersprachen nicht implementiert wurde, obwohl er durchaus abgebildet werden könnte. So wie 128-stelliges BCD, Ganzzahlen mit beliebiger Stellenanzahl, Tristate Logic usw. Allerdings bezweifle ich, das die Person, die dieses Sprachfeature implementiert, am nächsten Tag noch seinen Job innhalten dürfte.

Bei meinen Einwänden bezüglich einer effizienten Umsetzung eines Compilers bin ich nicht davon ausgegangen, das jemand allen Ernstes ein 128MB-Monster im Speicher halten würde, wo man so etwas mit sparse sets wesentlich komprimierter darstellen könnte.

Noch Einwände, bei denen ich nicht einschlafe?

[dajuhsa]

ich will mich ja in eure Diskussion nicht einmischen, aber hier geht es wohl nicht mehr um mich, oder? ^^"