Gibt es einen bestimmten Zweck für heterogene Listen?

13

Ich komme aus C # und Java und bin es gewohnt, dass meine Listen homogen sind, und das macht für mich Sinn. Als ich anfing, Lisp aufzunehmen, bemerkte ich, dass die Listen heterogen sein können. Als ich anfing, mit dem dynamicSchlüsselwort in C # herumzuspielen, bemerkte ich, dass es ab C # 4.0 auch heterogene Listen geben kann:

List<dynamic> heterogeneousList

Meine Frage ist, worum geht es? Es scheint, als würde eine heterogene Liste bei der Verarbeitung viel mehr Aufwand verursachen. Wenn Sie verschiedene Typen an einem Ort speichern müssen, benötigen Sie möglicherweise eine andere Datenstruktur. Bringt meine Naivität ihr hässliches Gesicht zur Geltung oder gibt es wirklich Zeiten, in denen es nützlich ist, eine heterogene Liste zu haben?

Jetti
quelle
1
Meinten Sie ... Ich habe bemerkt, dass die Listen heterogen sein können ...?
Ingenieur Welt
Was ist List<dynamic>(für Ihre Frage) anders als einfach zu tun List<object>?
Peter K.
@WorldEngineer ja, das tue ich. Ich habe meinen Beitrag aktualisiert. Vielen Dank!
Jetti
@PeterK. Ich denke für den täglichen Gebrauch gibt es keinen Unterschied. Da jedoch nicht jeder Typ in C # von System.Object abgeleitet ist, kann es zu Randfällen kommen, bei denen es Unterschiede gibt.
Jetti

Antworten:

16

Die Veröffentlichung Stark typisierte heterogene Sammlungen von Oleg Kiselyov, Ralf Lämmel und Keean Schupke enthält nicht nur eine Implementierung heterogener Listen in Haskell, sondern auch ein motivierendes Beispiel dafür, wann, warum und wie Sie HLists verwenden würden. Insbesondere verwenden sie es für den typsicheren, zur Kompilierungszeit überprüften Datenbankzugriff. (Denken Sie LINQ, in der Tat, das Papier , das sie verweisen, ist das Haskell Papier von Erik Meijer et al, die LINQ geführt.)

Zitat aus dem einleitenden Absatz des HLists-Papiers:

Hier ist eine offene Liste typischer Beispiele, die heterogene Sammlungen erfordern:

  • Eine Symboltabelle, in der Einträge unterschiedlichen Typs gespeichert werden sollen, ist heterogen. Es ist eine endliche Karte, bei der der Ergebnistyp vom Argumentwert abhängt.
  • Ein XML-Element ist heterogen typisiert. Tatsächlich sind XML-Elemente verschachtelte Auflistungen, die durch reguläre Ausdrücke und die 1-Ambiguity-Eigenschaft eingeschränkt sind.
  • Jede Zeile, die von einer SQL-Abfrage zurückgegeben wird, ist eine heterogene Zuordnung von Spaltennamen zu Zellen. Das Ergebnis einer Abfrage ist ein homogener Strom heterogener Zeilen.
  • Das Hinzufügen eines erweiterten Objektsystems zu einer funktionalen Sprache erfordert heterogene Sammlungen, die erweiterbare Datensätze mit Untertypen und einer Aufzählungsschnittstelle kombinieren.

Beachten Sie, dass die Beispiele, die Sie in Ihrer Frage angegeben haben, keine heterogenen Listen in dem Sinne sind, dass das Wort allgemein verwendet wird. Sie sind schwach typisierte oder untypisierte Listen. Tatsächlich handelt es sich um homogene Listen, da alle Elemente vom gleichen Typ sind: objectoder dynamic. Sie sind dann gezwungen, Casts oder ungeprüfte instanceofTests oder ähnliches durchzuführen, um tatsächlich mit den Elementen sinnvoll arbeiten zu können, wodurch sie schwach getippt werden.

Jörg W. Mittag
quelle
Vielen Dank für den Link und Ihre Antwort. Sie weisen darauf hin, dass die Listen wirklich nicht heterogen, sondern schwach typisiert sind. Ich freue mich darauf, diese Zeitung zu lesen (wahrscheinlich morgen, habe ich heute Abend eine Halbzeit bekommen :))
Jetti
5

Lange Rede, kurze, heterogene Container tauschen Laufzeitleistung gegen Flexibilität aus. Wenn Sie eine „Liste von Dingen“ ohne Rücksicht auf die jeweilige Art von Dingen haben möchten, ist Heterogenität der richtige Weg. Lisps sind charakteristisch dynamisch typisiert, und fast alles ist ohnehin eine Liste von Box-Werten, so dass der kleinere Performance-Hit erwartet wird. In der Lisp-Welt ist die Produktivität von Programmierern wichtiger als die Laufzeitleistung.

In einer dynamisch typisierten Sprache hätten homogene Container tatsächlich einen geringen Overhead im Vergleich zu heterogenen Containern, da alle hinzugefügten Elemente typüberprüft werden müssten.

Ihre Intuition, eine bessere Datenstruktur zu wählen, ist klar. Im Allgemeinen gilt: Je mehr Verträge Sie für Ihren Code einrichten können, desto mehr wissen Sie über die Funktionsweise des Codes und desto zuverlässiger, wartbarer und c. es wird. Manchmal möchten Sie jedoch wirklich einen heterogenen Container, und es sollte Ihnen gestattet sein, einen zu haben, wenn Sie ihn benötigen.

Jon Purdy
quelle
1
"Manchmal möchte man jedoch wirklich einen heterogenen Container, und man sollte einen haben dürfen, wenn man ihn braucht." - Warum allerdings? Das ist meine frage Warum sollten Sie jemals nur ein paar Daten in eine zufällige Liste packen müssen?
Jetti
@Jetti: Angenommen, Sie haben eine Liste der vom Benutzer eingegebenen Einstellungen verschiedener Typen. Sie könnten eine Schnittstelle erstellen IUserSettingund mehrfach implementieren oder eine generische UserSetting<T>, aber eines der Probleme bei der statischen Typisierung besteht darin, dass Sie eine Schnittstelle definieren, bevor Sie genau wissen, wie sie verwendet werden soll. Die Dinge, die Sie mit Integer-Einstellungen tun, unterscheiden sich wahrscheinlich sehr von den Dingen, die Sie mit String-Einstellungen tun. Welche Operationen sind also sinnvoll, um eine gemeinsame Schnittstelle zu erstellen? Bis Sie es mit Sicherheit wissen, ist es besser, die dynamische Eingabe mit Bedacht anzuwenden und sie später zu konkretisieren.
Jon Purdy
Seht, da stoße ich auf Probleme. Für mich scheint das nur ein schlechtes Design zu sein. Machen Sie etwas, bevor Sie wissen, was es tun / verwenden wird. In diesem Fall können Sie das Interface auch mit einem Objektrückgabewert versehen. Entspricht der heterogenen Liste, ist jedoch übersichtlicher und einfacher zu beheben, wenn Sie genau wissen, welche Typen in der Benutzeroberfläche verwendet werden.
Jetti
@Jetti: Das ist im Wesentlichen das gleiche Problem - eine universelle Basisklasse sollte überhaupt nicht existieren, da es unabhängig von den definierten Operationen einen Typ gibt, für den diese Operationen keinen Sinn ergeben. Aber wenn C # es einfacher macht, ein objectanstelle eines zu verwenden dynamic, dann verwenden Sie sicher das erstere.
Jon Purdy
1
@ Jetti: Darum geht es beim Polymorphismus. Die Liste enthält eine Reihe von "heterogenen" Objekten, obwohl sie Unterklassen einer einzelnen Superklasse sein können. Aus Java-Sicht können Sie die Klassendefinitionen (oder Schnittstellendefinitionen) richtig definieren. Für andere Sprachen (LISP, Python usw.) hat es keinen Vorteil, alle Deklarationen richtig zu machen, da es keinen praktischen Unterschied bei der Implementierung gibt.
S.Lott,
2

In funktionalen Sprachen (wie lisp) verwenden Sie den Mustervergleich, um zu bestimmen, was mit einem bestimmten Element in einer Liste geschieht. Das Äquivalent in C # wäre eine Kette von if ... elseif-Anweisungen, die den Typ eines Elements prüfen und eine darauf basierende Operation ausführen. Es erübrigt sich zu erwähnen, dass der funktionale Mustervergleich effizienter ist als die Überprüfung des Laufzeit-Typs.

Die Verwendung von Polymorphismus wäre eine engere Übereinstimmung mit der Musterübereinstimmung. Das heißt, die Objekte einer Liste stimmen mit einer bestimmten Schnittstelle überein, und für jedes Objekt wird eine Funktion für diese Schnittstelle aufgerufen. Eine andere Alternative wäre die Bereitstellung einer Reihe überladener Methoden, die einen bestimmten Objekttyp als Parameter verwenden. Die Standardmethode, die Object als Parameter verwendet.

public class ListVisitor
{
  public void DoSomething(IEnumerable<dynamic> list)
  {
    foreach(dynamic obj in list)
    {
       DoSomething(obj);
    }
  }

  public void DoSomething(SomeClass obj)
  {
    //do something with SomeClass
  }

  public void DoSomething(AnotherClass obj)
  {
    //do something with AnotherClass
  }

  public void DoSomething(Object obj)
  {
    //do something with everything els
  }
}

Dieser Ansatz liefert eine Annäherung an den Lisp-Musterabgleich. Das Besuchermuster (wie hier implementiert, ist ein großartiges Anwendungsbeispiel für heterogene Listen). Ein weiteres Beispiel wäre das Versenden von Nachrichten, bei dem sich Listener für bestimmte Nachrichten in einer Prioritätswarteschlange befinden und die Verantwortungskette verwendet wird. Der Dispatcher übergibt die Nachricht und der erste Handler, der mit der Nachricht übereinstimmt, verarbeitet sie.

Die Kehrseite benachrichtigt alle, die sich für eine Nachricht registrieren (z. B. das Ereignisaggregatormuster, das häufig für die lose Kopplung von ViewModels im MVVM-Muster verwendet wird). Ich benutze das folgende Konstrukt

IDictionary<Type, List<Object>>

Die einzige Möglichkeit, dem Wörterbuch etwas hinzuzufügen, ist eine Funktion

Register<T>(Action<T> handler)

(und das Objekt ist eigentlich eine WeakReference zum übergebenen Handler). Hier MUSS ich also List <Object> verwenden, da ich zur Kompilierungszeit nicht weiß, wie der geschlossene Typ aussehen wird. Zur Laufzeit kann ich jedoch erzwingen, dass es der Typ ist, der den Schlüssel für das Wörterbuch darstellt. Wenn ich das Ereignis auslösen möchte, rufe ich an

Send<T>(T message)

und wieder löse ich die liste auf. Die Verwendung von List <dynamic> bietet keinen Vorteil, da ich sie ohnehin umsetzen muss. Wie Sie sehen, haben beide Ansätze ihre Vorzüge. Wenn Sie ein Objekt mithilfe der Methode "Überladen" dynamisch versenden möchten, können Sie dies mithilfe der Methode "Dynamisch" tun. Wenn Sie trotzdem gezwungen sind, zu zaubern, können Sie auch Object verwenden.

Michael Brown
quelle
Bei der Mustererkennung werden die Fälle (normalerweise - zumindest in ML und Haskell) durch die Angabe des Datentyps, auf den sie zutreffen, in Stein gemeißelt. Listen, die solche Typen enthalten, sind ebenfalls nicht heterogen.
Ich bin mir bei ML und Haskell nicht sicher, aber Erlang kann gegen alles mithalten. Wenn Sie hier angekommen sind, weil keine anderen Spiele zufrieden waren, tun Sie dies.
Michael Brown
@MikeBrown - Dies ist nett, aber es wird nicht erläutert, warum heterogene Listen verwendet werden und was nicht immer mit List <dynamic> funktioniert
Jetti
4
In C # werden Überladungen zur Kompilierungszeit behoben . Daher ruft Ihr Beispielcode immer aufDoSomething(Object) (zumindest bei Verwendung objectin der foreachSchleife; dynamicist eine ganz andere Sache).
Heinzi
@Heinzi, du hast recht ... Ich bin heute müde: P behoben
Michael Brown
0

Sie haben Recht, dass Heterogenität die Laufzeit überfordert, aber was noch wichtiger ist, sie schwächt die Garantie für die Kompilierungszeit, die der Typechecker bietet. Trotzdem gibt es einige Probleme, bei denen die Alternativen noch teurer sind.

Nach meiner Erfahrung stoßen Sie beim Umgang mit unformatierten Bytes über Dateien, Netzwerk-Sockets usw. häufig auf solche Probleme.

Um ein reales Beispiel zu geben, betrachten Sie ein System für die verteilte Berechnung unter Verwendung von Futures . Ein Worker auf einem einzelnen Knoten kann Arbeit von jedem serialisierbaren Typ erzeugen, was eine Zukunft dieses Typs ergibt. Hinter den Kulissen sendet das System die Arbeit an einen Kollegen und speichert dann einen Datensatz, in dem diese Arbeitseinheit mit der jeweiligen Zukunft verknüpft ist, die ausgefüllt werden muss, sobald die Antwort auf diese Arbeit zurückkehrt.

Wo können diese Aufzeichnungen aufbewahrt werden? Intuitiv ist das, was Sie wollen, so etwas wie ein Dictionary<WorkId, Future<TValue>>, aber dies beschränkt Sie auf die Verwaltung nur einer Art von Futures im gesamten System. Der geeignetere Typ ist Dictionary<WorkId, Future<dynamic>>, da der Arbeiter den geeigneten Typ wählen kann, wenn er die Zukunft erzwingt.

Hinweis : Dieses Beispiel stammt aus der Haskell-Welt, in der wir keine Untertypen haben. Es würde mich nicht wundern, wenn es in C # eine idiomatischere Lösung für dieses spezielle Beispiel gibt, die aber hoffentlich immer noch illustrativ ist.

Adam
quelle
0

ISTR, dass Lisp keine anderen Datenstrukturen als eine Liste hat. Wenn Sie also einen Typ eines aggregierten Datenobjekts benötigen, muss es sich um eine heterogene Liste handeln. Wie bereits erwähnt, sind sie auch nützlich, um Daten für die Übertragung oder Speicherung zu serialisieren. Ein nettes Feature ist, dass sie auch offen sind, sodass Sie sie in einem System verwenden können, das auf einer Pipes-and-Filter-Analogie basiert, und aufeinanderfolgende Verarbeitungsschritte ausführen, um die Daten zu erweitern oder zu korrigieren, ohne dass entweder ein festes Datenobjekt oder eine Workflow-Topologie erforderlich ist .

TMN
quelle