Problem beim Umsetzen einer Menge

  • C#

Es gibt 22 Antworten in diesem Thema. Der letzte Beitrag () ist von TheVBTutorialsVB.

    Problem beim Umsetzen einer Menge

    Hallo Forum,

    ich (versuche) gerade eine Mathebibliothek zu programmieren und hänge an einer eigentlich trivialen Stelle fest. Ich möchte Mengen im mathematischen Sinne integrieren (benutze dazu momentan eine Liste), d.h ich lege Wert darauf, dass die Menge keine Reihenfolge hat. Deshalb ist die Liste mit der ich arbeite private. Somit exisiert zwar theoretisch eine Reihenfolge, allerdings bleibt diese verborgen. Allerdings brauche ich zur Berechnung von Schnittmengen etc. Zugriff auf die Elemente der Menge, ohne, dass man von anderen Klassen aus Zugriff auf die Elemente der Menge hat. Gibt es irgendein Keyword dass C# dazu bereitstellt oder muss ich mir selbst ein Konstrukt erstellen. Falls ja bräuchte ich Tips dazu.

    LG

    Also wenn ich dich richtig verstehe, kann man deine Liste mit Schrödingers Katze vergleichen? Du brauchst den Zustand der Katze (bzw. die Items deiner Liste) zum arbeiten, darfst aber nicht die Katzenkiste öffnen um ihn zu prüfen oder was?

    Nicht im geringsten. Wenn man eine Menge hatM={1,2,3,8,9} dann kannst du nur sagen "Die 9 ist enthalten". Du kannst nicht sagen "Die 9 ist an Stelle 5". Das ist aber genau das, was jemand tut der von außen auf die Liste mit Elements zugreift. Die einzigen benötigten Methoden sind Add, Contains, Remove, Union und Intersection, dazu soll man keinen Zugriff auf die Liste haben.

    @~blaze~

    Das ist eins zu eins das, was ich programmieren wollte, danke! Kannst du mir erklären wie die Klasse intern funktioniert? Wie kann die Methode UnionWith funktionieren, wenn die Elemente privat sind und somit eine Schleife nicht funktioniert?

    Das vorgeschlagene trifft alles nicht genau die Definition einer Menge.
    Aber ich fund grade im Objectbrowser, bei System.Collection.Generics die ISet(of T) - Schnittstelle.
    Die definiert glaub genau, was der TE abbilden will: eine Menge.
    Nu müsste man mal gucken, obs iwelche Implementationen dieser Schnittstelle gibt - ja, SortedSet(of T) ist eine.
    SortedSet ist aber eiglich bischen zu streng definiert, weil Sortierung ist ja nicht Bestandteil des Mengen-Begriffs.
    Aber andererseits imo auch kein Problem: Wenn die Elemente einer Menge sortiert sind, ist deswegen ja nicht die Definition "Menge" verletzt. Die Sortierung hat beim SortedSet ganz praktische Gründe - Methoden sie IsSubSet, Contains, etc. sind in sortierten Mengen exorbitant performanter zu implementieren.

    Mist! SortedSet ist auf Icomparable Elemente angewiesen - idiotischerweise.

    Also weiter suchen, nach einer Klasse, die ISet(Of T) implementiert, und zwar ohne zusätzliche Einschränkungen zu erzwingen.
    Hashset(Of T) implementiert zB auch Iset, aber hat die Einschränkung, dass keine Dubletten zulässig sind.

    Bei einer mathematischen Menge sind auch mehrere Elemente nicht zulässig - wenn es sich nicht um eine Multimenge handelt. Bzw. zulässig schon, aber die Menge enthält dann dennoch nur die Zahl der voneinander verschiedenenen Elemente:
    |{1, 1, 1, 1, 5, 1}| hat im Falle einer normalen Menge die Kardinalität 2.

    Multimengen könnte man über ein internes struct implementieren, das noch einen Index enthält.

    C#-Quellcode

    1. private struct Entry : IEquatable<Entry>
    2. {
    3. public T Element {get; set; }
    4. public int Index {get; set; }
    6. public Entry(T element, int index)
    7. {
    8. Element = element;
    9. Index = index;
    10. }
    12. public override bool Equals(Entry other)
    13. {
    14. if (other.Index != Index)
    15. return false;
    17. if (Element == null)
    18. return other.Element == null;
    19. else if (other.Element == null)
    20. return false;
    22. return other.Element.Equals(other.Element);
    23. }
    25. public override int GetHashCode()
    26. {
    27. return (Element?.GetHashCode() ?? 0) ^ ~Index;
    28. }
    30. public bool Equals(object obj)
    31. {
    32. if (obj == null)
    33. return false;
    35. var el = obj as Element?;
    37. return el != null && Equals(el.Value);
    38. }
    39. }


    Anstatt T dann halt Element<T> in die Liste. Allerdings muss man dann manuell die Zahl der äquivalenten Elemente bestimmen (am besten direkt beim Befüllen der Menge). Den Index einfach immer hochzählen, bis das Element neu hinzugekommen ist (HashSet<T>.Add gibt ja ein bool zurück).
    Eine andere Möglichkeit wäre Dictionary<T, int>, wobei der Wert jeweils die Zahl der Wiederholungen angibt.

    Bzgl. deiner Frage bzgl. der Art der Implementation:
    Es gäbe mehrere Arten, das zu implementieren. Ich schätze, dass es die Hashes auf Array-Indices abbildet (z.B. Modulo einer Primzahl - das intern genutzte Array hätte dann eine Länge, die der Primzahl entspricht und ein Element würde auf den Array-Index GetHashcode() % array.Length abgebildet) und die Elemente dann in einer verketteten Liste hält. Das ist eine recht übliche Art, das zu verwalten.
    Das Array lässt sich dann relativ einfach neu berechnen, indem man einfach alle bestehenden Elemente erneut. Ist nicht so teuer.
    Im Fall "meiner" Multimengen-Implementation musst du dir halt was überlegen, die ist aber definitiv weit weniger effizient und man würde normalerweise auch wohl nicht um eine eigene Implementation herumkommen, wenn man auf Effizienz wert legt.

    SortedSet hatte ich nur vorgeschlagen, weil man mathematisch meist eine sortierte Darstellung wählt. Es ist übrigens auf einen Comparer angweisen, d.h. man kann beliebige Elemente reinwerfen, solange man einen Comparer dafür implementiert.
    Die Sortierung könnte man analog zu obigem struct so implementieren, dass die Reihenfolge der eingehenden Elemente erhalten bleibt (einfach den Index nicht bei Equality-Comparison verwenden und nur bei CompareTo).

    Viele Grüße
    ~blaze~

    Ups - ja ich bin kein Mathematiker. Ich stell mir unter Menge einen Sack voll Dinge gleichen DatenTyps vor - und da wären Dubletten zulässig.
    Etwa bei Permutationen redet man glaub von Sets (oder?), und je nachdem, ob die Sets Dubletten haben dürfen oder nicht kommt man zu unterschiedlichen Ergebnissen.

    ~blaze~ schrieb:

    SortedSet ... man kann beliebige Elemente reinwerfen, solange man einen Comparer dafür implementiert.
    Ah - dann Problem doch gelöst (zumindest in meiner Auffassung von Sets). Weil als Comparer kann man ja immer etwas basteln, was item.GetHashCode() comparet.

    @ErfinderDesRades

    Ist IComparable bei allen üblichen Datentypen implementiert? Brauche die Mengen für rein mathematische Berechnungen, d.h es wird nicht vorkommen, dass ich andere Klassen in Mengen zusammenfassen möchte.

    @~blaze~

    Das was du beschreibst werde ich vermutlich niemals performant implementieren können (zumindest nicht mit meine Kenntnissen :D) nehme ich an. Ist es die Mühe wert es selbst zu implementieren oder einfach auf sprachinterne Strukturen zurückzugreifen?

    TheVBTutorialsVB schrieb:

    Ist IComparable bei allen üblichen Datentypen implementiert?
    Definiere "üblicher Datentyp". ;)
    Also in meiner Welt gibts keine unüblichen Datentypen, von daher ist deine Frage zu verneinen: Nein, IComparable ist nicht bei allen Datentypen implementiert.

    TheVBTutorialsVB schrieb:

    Brauche die Mengen für rein mathematische Berechnungen, d.h es wird nicht vorkommen, dass ich andere Klassen in Mengen zusammenfassen möchte.
    Das ist keine klare Aussage, für welche Datentypen du die Menge-Klasse brauchst.
    Aber wenn du Zahlen meinst, hast du "Glück": Alle Zahl-Datentypen implementieren natürlich IComparable - somit sollte SortedSet deine Ansprüche vollkommen erfüllen.

    es sind nicht, weils keywords sind, sondern weils Datentypen sind.
    Komischerweise werden sie wie Keywords coloriert vonne IDE - ich weiss aber nicht wirklich, warum.
    Vermutlich weil die Zahlen zu den "primitiven Datentypen" gehören, aber genau das weiß ich nicht: was eiglich einen Primitiven Datentyp ausmacht (ausser, dass bei .Gettype().IsPrimitive True zurückgegeben wird).

    Übrigens muss ich mich korrigieren: Bei komplexen Zahlen bezweifel ich, dass die zu den primitiven gehören, und möglicherweise implementieren die nichtmal IComparable.
    K.A. - nie was mit gemacht.

    Aber du hast recht: Diese Datentypen werden mit bei die "Schlüsselworte" gelistet, neben Namespace, Option, Dim etc.. Klickst man allerdings drauf, kommt man zu einer Datentyp-Beschreibung - scheinbar werden manche Datentypen zu den Elementen der Sprache gezählt und andere nicht.

    Dieser Beitrag wurde bereits 6 mal editiert, zuletzt von „ErfinderDesRades“ ()

    ErfinderDesRades schrieb:

    Etwa bei Permutationen redet man glaub von Sets


    Permutationen kann man als Tupel darstellen. Häufig notiert man sie aber auch als Matrix (heißt, glaube ich, Cauchy-Notation). Als Menge könnte man sie darstellen, wenn man alle Permutationen meint, weil die Menge ungeordnet ist.
    Mengen an sich sind an sich nur ungeordnete Auflistungen von Dingen (wobei man z.B. bei den reellen Zahlen ziemlich mit der Aufzählung beschäftigt wäre. Sogar noch mehr, als bei den natürlichen Zahlen). Je nach Kontext wählt man Mengen dann eben als Darstellung.

    TheVBTutorialsVB schrieb:

    Ist es die Mühe wert es selbst zu implementieren oder einfach auf sprachinterne Strukturen zurückzugreifen?


    Das kommt völlig drauf an, was du vorhast. Wenn du es richtig implementierst, kannst du einiges an Performance herausholen. Das fällt aber erst ins Gewicht, wenn du mit wirklich großen Mengen arbeitest, d.h. mehrere hunderttausende Elemente. Vor allem sind Multimengen etwas, was ich jetzt noch nicht allzu häufig gebraucht habe. Insofern solltest du mit HashSet eigentlich eine Lösung haben, die erstmal reicht, sofern du nicht vorhast, jene Dinge zu machen, die ich nicht gemacht habe und die auf Multimengen zurückgreifen :P.
    Ich würde einfach mal sagen, dass du erst mal das fertigstellst, was du jetzt vorhast und es dann später um die Dinge erweiterst, die jetzt noch nicht nötig sind. Du hast eh einiges vor.

    Primitive Datentypen sind sbyte, byte, short, ushort, usw. (und nicht decimal und auch nicht string, die sind noch weiter zerlegbar in andere Datentypen). Datentyp bezeichnet wohl alle Typen.
    Außer bool sollten alle primitiven Datentypen IComparable bzw. IComparable<T> implementieren.
    Allgemein würde ich btw. zumindest sagen, dass jeder Typ IComparable<T> implementieren sollte, dessen Instanzen logisch gesehen verglichen werden können.

    Viele Grüße
    ~blaze~

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „~blaze~“ ()

    @~blaze~

    Ich brauche nur ganz kleine Mengen von wenigen Zahlen. Die Mathebibliothek soll nur das, was ich in der Schule lerne festigen und höchstens bei Vektorrechnung von irgendwelchen Jump'n Runs dienen. HashSets sollten für meine Zwecke ausreichen, danke :)

    ~blaze~ schrieb:

    Allgemein würde ich btw. zumindest sagen, dass jeder Typ IComparable<T> implementieren sollte, dessen Instanzen logisch gesehen verglichen werden können.
    wobei mit "logisch verglichen" gemeint sein muss, dass man größer, kleiner, gleich bestimmen kann.

    ~blaze~ schrieb:

    Permutationen kann man als Tupel darstellen.
    hmm offsichtlich gehen da mathematische und informatische Begrifflichkeiten ziemlich auseinander.
    Weil wenn du was mit Permutationen programmierst, dann sind die generischen Sytem.Tuple-Klassen komplett unbrauchbar.
    Aber lass uns das nicht vertiefen - ich werd wohl nie ein Mathematiker.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „ErfinderDesRades“ ()

    Die passen schon aufeinander. Ein Tupel muss nicht zwangsweise Elemente gleichen Typs enthalten. In der Mathematik hast du nur nicht die ausufernde Notation Tuple<T1, ..., Tn>(v1, ..., vn) sondern einfach (v1, ..., vn), wobei v1, ..., vn nicht Elemente der gleichen Menge sein müssen. Bzw. man kann auch v1, ..., vn in eine Menge zusammenfassen, das ist losgelöst voneinander.

    Und bzgl. der Vergleiche: Jep, also keine Äquivalenz-Vergleiche.

    Interessant wird es übrigens erst, wenn man die Mathematik in ihrem vollem Spektrum in .Net umzusetzen versucht. Für das, was man in der Schulmathematik so lernt, reicht es vollkommen aus, das einfach so herunterzuprogrammieren. Interessant wird es dann allerdings, wenn man alles weiter abstrahiert, d.h. Vektoren auf beliebigen Elementen zulässt und z.B. Additionen von Vektoren nur noch auf jenen "Mengen" anbietet, auf denen die Addition definiert ist - was auch nicht korrekt ist, da die Addition auf einer Menge definiert wird, aber man kann ja beliebig viele Additionsoperatoren für eine (überabzählbare) Menge definieren.
    Welcher Additionsoperator ist dann bei a + b gemeint? Gelten Assoziativ- und Kommutativgesetz?
    Ähnlich bei Vergleichen: Gilt, wenn a < b auch dass b < a? Folgt aus
    $a \le b \wedge b \le a$
    dass a = b? Das sind alles Dinge, die selbstverständlich erscheinen, wenn man in der Schulmathematik damit arbeitet, ist aber in der höheren Mathematik alles nicht mehr zwangsweise so und ich würde sogar sagen, dass .Net gänzlich ungeeignet ist, solche Konstrukte elegant zu implementieren (was meint, dass man nicht einen Konstruktor mit duzenden Tokens benötigt. Man will ja nicht dauernd angeben müssen, dass eine natürliche Zahl als solche gehandhabt werden soll).
    Und das sind sogar nur die Anfänge. Ich hatte vor ein paar Jahren mit der Definition einer eigenen Programmiersprache angefangen, die sich dann immer mehr richtung funktionale Programmierung entwickelt hat, um sowas umzusetzen. Man hatte quasi nur kein Prosa mehr in der Sprache, außer Kommentare. Ich habe es dann aber letztenendes mangels Zeit nicht umgesetzt.

    Viele Grüße
    ~blaze~

Facebook
Telefonspende