Re: Objekt Identität

Stephan, ich verstehe nicht, /wonach/ du in einer Liste binär suchen willst. Dieser Suchwert muss ja auch eindeutig sein. Wenn du also einen Wert als Suchkriterium "irgendwo" her hast, dann kannst du /stattdessen/ auch gleich die Objektreferenz verwenden und musst auch nicht mehr suchen. Sehe ich das falsch?

Das ist z.B. sinnvoll, wenn ich einen Objekt-Graphen traversiere und Zyklen vermeiden möchte. Nachdem ich einen Knoten im Graphen (= ein Objekt) verarbeitet habe, füge ich ihn in den Container ein. Dann verfolge ich die Kanten des Graphen (= verbundene Objekte) und checke für jeden Knoten zuerst, ob ich ihn schon besucht habe, indem ich im Container nachschaue. Wenn der Container nach Objekt-Identität sortiert ist, ist dieser Check effizient.
Ein typischer Algorithmus, der so vor gehen könnte, wäre z.B. Objektserialisierung (btw.: wie funktioniert die effizient in .NET? hilft das Framework da mit? z.B. mit Objektmarkierung? oder erkennt die keine Zyklen?).

In Pseudo-Code z.B.

  class Knoten { ... };
  class Prozessor {
    IdentityContainer m_processed; // besuchte Knoten merken (Identität)
  public:
    // ...
    void Process(Knoten y) {
      if (m_processed.HasObject(y)) {  // effizient oder nicht?
        return; // Knoten schon bearbeitet
      }
      // ... bearbeite y ...
      m_processed.Insert(y);  // y merken
      foreach c in y.Connected() { Process(c); }
    }
  };

- Stephan
.

Relevant Pages

  • =?iso-8859-1?Q?Re:_Objekt_Identit=E4t?=
    ... Dann verfolge ich die Kanten des Graphen und checke für jeden Knoten zuerst, ob ich ihn schon besucht habe, indem ich im Container nachschaue. ... Also zuerst /alle/ Objekte im Wrapper verpacken und ihnen eine GUID verpassen - weil ich davon ausgehe, dass das Objekt selbst keinen eindeutigen Schlüssel hat, sonst hättest du die Frage ja nicht gestellt - und anschließend nur mit dem Wrapper-Objekten arbeiten und die GUID als Key verwenden. ...
    (microsoft.public.de.german.entwickler.dotnet.framework)
  • =?iso-8859-1?Q?Re:_Objekt_Identit=E4t?=
    ... Dann verfolge ich die Kanten des Graphen und checke für jeden Knoten zuerst, ob ich ihn schon besucht habe, indem ich im Container nachschaue. ...
    (microsoft.public.de.german.entwickler.dotnet.framework)
  • Re: kombinatorik-problem - oder schlimmer(?)
    ... einem Graphen ansehen, schreiben wir das ganze mal, wobei a ... ersten der rechten Seite, x die vierte der linken und y die vierte der ... Suche nach einem Pfad durch den Graphen, der jeden Knoten mindestens ...
    (de.sci.informatik.misc)
  • Re: Ich will auch, ich will auch
    ... Selbst ein Graphentheoretiker ... Vereinigung und Schnitt zweier Graphen so umdefiniert, ... Bezeichnungen für Objekte wie Knoten und Kanten ... die es erlaubt die Beweise zumindest ...
    (de.sci.mathematik)
  • Re: Ich will auch, ich will auch
    ... Selbst ein Graphentheoretiker ... Vereinigung und Schnitt zweier Graphen so umdefiniert, ... Bezeichnungen für Objekte wie Knoten und Kanten ... die es erlaubt die Beweise zumindest ...
    (de.sci.mathematik)
Loading