Referenz auf eine Variable in C#

Chryzler · Beiträge: 1097 Erhaltene Danke: 2

Servus

,

ich sitz grad vor nem saftigen Problemchen. Ich will eine Graphen-Klasse in C# schreiben, d.h. ich muss erstens alle Knoten abspeichern, und zweitens alle Verbindungen zwischen den Knoten. Ein einzelner Knoten könnte dann ungefähr so aussehen:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:

class Knoten
{
    Knoten[] verbindungen;  // speichert die Endknoten aller Verbindungen dieses Knotens 

    // ...
}

D.h. ich muss bei jedem Knoten alle anderen Knoten nochmal speichern, zu denen dieser Knoten eine Verbindung hat. Dadurch steigt aber der Speicherverbrauch schon bei relativ wenig Knoten enorm. Eigentlich auch kein Wunder, die ganzen Knoten werden ja x-mal gespeichert. Das was ich bräuchte wären Pointer, nur die gibts in C# nicht (jedenfalls nicht auf managed-Typen). Was nun? Ich muss C# irgendwie sagen, dass ich nicht dauernd Kopien von einem Knoten machen will, sondern nur eine Referenz zu den anderen Knoten machen will.

Hat irgendjemand ne Idee? *ratlos*

Chryzler

EDIT: Ach und noch was, wenn ich dann den Knoten knotenX.verbindungen[17] in irgendeiner Weise verändere, ändert sich dann der Original-Knoten auch? Eigentlich nicht, denn es ist ja eine Kopie des Original-Knotens, oder?

Christian S. · Beiträge: 20451 Erhaltene Danke: 2264 Win 10 C# (VS 2019)

Genau wie in Delphi sind Klassen in C# bereits Referenzdatentypen. Du arbeitest also eigentlich nur mit Referenzen. Bei Structs sieht's dann so aus wie Delphi-Records, das sind Werttypen.

Ich würde aber eher List<Knoten> verwenden als ein Knoten[]

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".

Chryzler · Beiträge: 1097 Erhaltene Danke: 2

Christian S. hat folgendes geschrieben:

Genau wie in Delphi sind Klassen in C# bereits Referenzdatentypen. Du arbeitest also eigentlich nur mit Referenzen. Bei Structs sieht's dann so aus wie Delphi-Records, das sind Werttypen.

Ich würde aber eher List<Knoten> verwenden als ein Knoten[]

Hmm. List<Knoten> verwend ich eigentlich sowieso schon, hatte jetzt nur im Beispiel ein Array genommen. Dann wäre die Frage eigentlich schon beantwortet, ich such mal nach ner Möglichkeit, den Speicherverbrauch etwas zu senken. 400 MB + 400 MB virtuell bei 20000 Knoten und einigen Verbindungen ist schon heftig, find ich.

Christian S. · Beiträge: 20451 Erhaltene Danke: 2264 Win 10 C# (VS 2019)

Du kannst ja mal alle Felder der Knoten-Klasse zeigen, vielleicht fällt da was auf.

Wieviel Verbindungen gibt es denn so im Schnitt von einem Knoten zu den anderen?

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".

Kha · Verfasst: Di 02.10.07 21:15

20000 Knoten sind schon heftig. Bei 800 MB wären das ja aber (im nicht erreichbaren Idealfall) 10000 Kanten pro Knoten, also ein äußerst dichter Graph; da könnte eine Adjazenzmatrix platzschonender sein. Das wären dann mit einem bool-Array "nur" 381 MB, als Bitvektor (BitArray-Klasse) sogar nur ein Achtel davon, 48 MB.

Chryzler · Beiträge: 1097 Erhaltene Danke: 2

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:

class GraphLink
{
    public GraphNode GraphNode1;
    public GraphNode GraphNode2;

    public GraphLink(GraphNode GraphNode1, GraphNode GraphNode2)
    {
        this.GraphNode1 = GraphNode1;
        this.GraphNode2 = GraphNode2;
    }
}

class GraphNode
{
    public List<GraphLink> Links = new List<GraphLink>();
    public float Data;

    public GraphNode(float Data)
    {
        this.Data = Data;
    }

    public void AddLink(GraphNode graphNode)
    {
        Links.Add(new GraphLink(this, graphNode));
        graphNode.Links.Add(new GraphLink(graphNode, this));
    }
}

class Graph
{
    public List<GraphNode> Nodes = new List<GraphNode>();

    public void DeleteNode(GraphNode graphNode)
    {
        for (int i = 0; i < graphNode.Links.Count; i++)
        {
            for (int j = 0; j < graphNode.Links[i].GraphNode2.Links.Count; j++)
                if (graphNode.Links[i].GraphNode2.Links[j].GraphNode2 == graphNode)
                {
                    graphNode.Links[i].GraphNode2.Links.RemoveAt(j);
                    break;
                }
        } 

        Nodes.Remove(graphNode);             
    }        
}

Das sind jetzt die Klassen, etwas vereinfacht. Bei 20000 Knoten hat jeder Knoten ungefähr 1000 Kanten. Auch das Löschen eines Knotens dauert viel zu lang, aber ich komm um die verschachtelten For-Schleifen nicht drumrum.

Khabarakh hat folgendes geschrieben:

20000 Knoten sind schon heftig. Bei 800 MB wären das ja aber (im nicht erreichbaren Idealfall) 10000 Kanten pro Knoten, also ein äußerst dichter Graph; da könnte eine Adjazenzmatrix platzschonender sein. Das wären dann mit einem bool-Array "nur" 381 MB, als Bitvektor (BitArray-Klasse) sogar nur ein Achtel davon, 48 MB.

Hab mich gerade bei Wikipedia schlaugemacht. Eine Adjazenzmatrix hätte bei mir hier einige Vorteile (Löschen eines Knotens wäre relativ schnell), allerdings dauert dann die Suche im Graph wieder länger, aber ich versuchs mal zu implementieren und meld mich dann wieder.

Kha · Verfasst: Di 02.10.07 22:41

Halthalthalt

, bei nur 1000 Kanten pro Knoten wird dir eine Matrix nichts nützen. Der größte Speicherfresser ist jetzt jedenfalls klar: die Kanten-Klasse. Sicher, dass du die benötigst und nicht einfach eine Referenz auf den verbundenen Knoten genügt? Nach meinen (höchstwahrscheinlich komplett falschen) Berechnungen machen diese Kanten-Instanzen zwei Drittel des Speicherverbrauchs aus.

Christian S. · Beiträge: 20451 Erhaltene Danke: 2264 Win 10 C# (VS 2019)

Khabarakh hat folgendes geschrieben:

Sicher, dass du die benötigst und nicht einfach eine Referenz auf den verbundenen Knoten genügt?

Ich würde auf "Nein" tippen, denn eines der beiden Felder der Klasse ist eh immer this und muss daher nicht nochmal gespeichert werden.

Was mich hierzu führt:

markieren

C#-Quelltext

1:	graphNode.Links[i].GraphNode2.Links[j].GraphNode2 == graphNode

graphNode.Links - beim Erzeugen wird bei jedem Element von Links das Feld GraphNode2 auf "this" (also graphNode) gesetzt.
--> graphNode.Links[i].GraphNode2 ist graphNode

folglich:
graphNode.Links[i].GraphNode2.Links[j] = graphNode.Links[j]

daher:
graphNode.Links[i].GraphNode2.Links[j].GraphNode2 = graphNode.Links[j].GraphNode2 = graphNode

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".

Chryzler · Beiträge: 1097 Erhaltene Danke: 2

Khabarakh hat folgendes geschrieben:

Halthalthalt

, bei nur 1000 Kanten pro Knoten wird dir eine Matrix nichts nützen. Der größte Speicherfresser ist jetzt jedenfalls klar: die Kanten-Klasse. Sicher, dass du die benötigst und nicht einfach eine Referenz auf den verbundenen Knoten genügt? Nach meinen (höchstwahrscheinlich komplett falschen) Berechnungen machen diese Kanten-Instanzen zwei Drittel des Speicherverbrauchs aus.

Stimmt, die Matrix verbaucht zwar im Gegensatz zu 800 MB nur 48 MB, aber das Suchen im Graph ist viel langsamer. Kann ich also auch nicht brauchen. Ich muss im Graphen nach bestimmten Kanten suchen, deswegen brauch ich bei jeder Kante beide Knoten, aber ich guck mir das nochmal an, vielleicht gehts doch irgendwie.

Christian S. hat folgendes geschrieben:

markieren

C#-Quelltext

1:	graphNode.Links[i].GraphNode2.Links[j].GraphNode2 == graphNode

graphNode.Links - beim Erzeugen wird bei jedem Element von Links das Feld GraphNode2 auf "this" (also graphNode) gesetzt.
--> graphNode.Links[i].GraphNode2 ist graphNode

folglich:
graphNode.Links[i].GraphNode2.Links[j] = graphNode.Links[j]

daher:
graphNode.Links[i].GraphNode2.Links[j].GraphNode2 = graphNode.Links[j].GraphNode2 = graphNode

Da hast du glaub ich was durcheinander gebracht. GraphNode1 ist immer der eigene Knoten, GraphNode2 ist immer der andere Knoten. D.h. knoten[1].verbindungen[17].GraphNode2 ist knoten[2], und knoten[2].verbindungen[17].GraphNode2 ist knoten[1].

Christian S. · Beiträge: 20451 Erhaltene Danke: 2264 Win 10 C# (VS 2019)

Stimmt, das war falsch.

Aber Du kannst Dir trotzdem die Link-Liste sparen, IMHO:

markieren

C#-Quelltext

1:
2:

Links.Add(new GraphLink(this, graphNode));
        graphNode.Links.Add(new GraphLink(graphNode, this));

Das Erste fügt dem Links-Feld von this einen GraphLink zu, dessen erstes Feld this ist.
Das Zweite fügt dem Links-Feld von graphNode einen GraphLink zu, dessen erstes Feld graphNode ist.

Immer die Instanz, welche die Links-Liste hält, ist auch das erste Feld eines Links. Die Information ist dann redundant.

Oder hab ich's wieder verpeilt? ;-)

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".

Kha · Verfasst: Mi 03.10.07 13:07

Chryzler hat folgendes geschrieben:

Ich muss im Graphen nach bestimmten Kanten suchen, deswegen brauch ich bei jeder Kante beide Knoten, aber ich guck mir das nochmal an, vielleicht gehts doch irgendwie.

Das solltest du dir wirklich noch einmal anschauen, ich habe noch nie eine Klasse für die Kanten gebraucht :gruebel:

. Stell am Besten einmal das konkrete Problem, bei dem du die Kanten-Klasse benötigst.

Chryzler · Beiträge: 1097 Erhaltene Danke: 2

So, das wäre dann auch erledigt. Mir ist nämlich gestern Abend eine sehr wirkungsvolle Lösung eingefallen, die aber nichts mit dem eigentlichen Graphen an sich zu tun hatte. Das wäre dann erledigt.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme