Datenstruktur, die nicht in XML ausgedrückt werden konnte?

tl; dr Ich kenne keinen, und ich habe viele Datenstrukturen ausprobiert. Einige Darstellungen sind jedoch mäßig ineffizient, daher ist es nicht unbedingt die beste Option, selbst wenn sie vollkommen sinnvoll ist.

Das ist eine schwierige Frage. XML ist ein ziemlich unbeschränkter Baum, der bereits die Hälfte aller Datenstrukturen abdeckt. Selbst die exotischsten, kompliziertesten Bäume sind immer noch Bäume - ich verstehe immer noch nicht wirklich die Erstellung und Manipulation von vBE Bäumen Ich weiß, dass es ein Baum ist, damit ich einen gegebenen vBE-Baum in XML umwandeln kann.

Weisen Sie jedem Knoten eine ID zu, oder entwickeln Sie ein anderes leichtgewichtiges Schema, um auf einen Knoten zu verweisen, ohne ihn zu einem Kind des Referrers zu machen, und Sie können jede Art von Graphen ohne große Schwierigkeiten erstellen. Und Diagramme sind so ziemlich das A und O aller allgemeinen Datenstrukturen. Zum Beispiel geht ein gerichteter, zyklischer Graph so:

Es ist offensichtlich, wie dies zu einer Adjazenzliste passt. Noch kompliziertere Graphen, wie Hypergraphen (eine Kante kann eine beliebige Anzahl von Stützpunkten enthalten) werden unterstützt, Sie brauchen nur eine separate Liste von Kanten, von denen jede eine Liste von Vertex-Referenzen enthält (siehe unten für Listen).

Noch einfachere Datenstrukturen lassen sich noch einfacher auf XML abbilden:

• Arrays, Listen, Warteschlangen, Stapel und andere geordnete flache Sammlungen: Machen Sie jedes Element zu einem Knoten und fügen Sie sie in einen einzelnen übergeordneten Knoten <seq> ein, damit sie Geschwister sind.
• Tupel (k-Werte): Weisen Sie jedem Element einen Bezeichner zu und machen Sie ihm Attribute. Alternativ können Sie einen Knoten <tuple> mit k untergeordneten Elementen erstellen, und Sie benötigen keine Bezeichner, da die Knotenreihenfolge (im Gegensatz zur Reihenfolge der Attribute) beibehalten wird.
• Wörterbücher: Behandle sie als Folge von (Schlüssel-, Wert-) Tupeln.
• Mengen haben keine Reihenfolge, aber jede Menge Datenstruktur, die mir bekannt ist, sortiert die Elemente intern aus (durch Vergleich, durch Hashes und Kollisionen oder einfach durch die Reihenfolge im naiven Fall). Verwenden Sie diese Reihenfolge oder die Reihenfolge, in der die Elemente zurückgegeben werden (wenn sie anders ist), wenn Sie die Datenstruktur zum Aufzählen ihrer Elemente auffordern.
• Eine Datenstruktur fehlt? Codieren Sie es als Datensatz (Ersetzen von Zeigern durch eine Indirektion wie für Diagramme verwendet), und ordnen Sie den Datensatz dann einem Knoten mit einem untergeordneten Knoten oder Attribut für jedes Datensatzelement zu. Dies wird für einige Dinge wie verknüpfte Listen hässlich, aber für sie existiert eine einfachere Darstellung wie oben beschrieben.

Keine dieser Darstellungen ist so schön wie das wirkliche Geschäft, aber Sie können mit ihnen gut arbeiten und das Erstellen der realen Datenstruktur im Speicher ist eine Sache einer kleinen und einfachen Schleife mit den richtigen Bibliotheken (zB lxml in Python, teilweise aufgrund von XPath).

Es gibt eine Klasse von Datenstrukturen, die nicht so einfach zu Bäumen ganz passt. Boolesche Matrizen, Bitmasken und dergleichen, die ihre Effizienz beim Abstieg auf ein einzelnes Bit pro Element steigern, explodieren erheblich, wenn Sie für jedes Element (oder jedes true -Element oder jedes false ) ein paar Dutzend Bytes verwenden. Element - das Problem bleibt bestehen). Eine weniger baumzentrierte Codierung kann dies jedoch auflösen. Sie könnten zum Beispiel eine Base64-Zeichenfolge für eine eindimensionale Bitmaske speichern und deren Folgen für höhere Dimensionen (einschließlich boolescher Matrizen) verwenden. Verknüpfen Sie die Bits zu einer Zahl und codieren Sie sie in base64 - oder besser online, um eine Arithmetik mit hoher Genauigkeit zu vermeiden. Das Ergebnis ist nicht ganz XML, aber immer noch einfach genug zum Generieren und Parsen.

Daher kann ich Ihnen keine Datenstruktur geben, die in XML nicht sinnvoll dargestellt werden kann. Es ist einfach zu allgemein, besonders wenn wir die Fähigkeit ausnutzen, beliebige binäre Daten in base64 und dergleichen einzubetten. Wenn Sie dies ablehnen, weil Sie kein reines XML sind, dann nehmen Sie es mit nach Hause: Bitmasken und boolesche Matrizen können nicht effizient in reinem XML dargestellt werden. Beachten Sie jedoch, dass eine reine XML-Codierung immer noch sinnvoll ist und nur wenig Platz benötigt. Und selbst das kann gemildert werden, wenn entweder wahre Falschwerte selten sind (z.B. Adjazenzmatrix eines sehr dichten oder spärlichen Graphen), indem nur der seltenere gespeichert wird und der andere implizit gemacht wird.

Das bedeutet jedoch nicht, dass XML die beste oder sogar eine gute Wahl für die Codierung dieser Datenstrukturen ist. Es ist ein gängiges Datenaustauschformat, aber für jede gegebene Datenstruktur gibt es eine einfachere und effizientere Darstellung. Wenn Sie also nicht die Flexibilität benötigen und sich zusätzliche Arbeit leisten können, verwenden Sie sie nicht. Oder verwenden Sie eines der anderen universellen Datenformate. Alle oben beschriebenen Kodierungen funktionieren perfekt in YAML mit weniger Ausführlichkeit, und einige funktionieren sogar besser, wenn Dinge wie Mappings und Arrays eingebaut werden. Bäume werden leicht hässlicher, da Sie sie als verschachtelte Datensätze kodieren müssen (lesen: lists / mappings) , aber so würden Sie sie ohnehin in einer Programmiersprache darstellen.Ich bin mir auch ziemlich sicher, dass JSON mit allen von ihnen umgehen kann, aber da ich nicht viel Zeit damit verbracht habe, sie zu generieren und zu parsen (ich habe mit XML und YAML), kann ich das nicht sicher sagen.

Eine Struktur, die eine unendliche Reihe von Elementen darstellt . Zum Beispiel kann ich in scala die fibonacci -Sequenz wie folgt erstellen:

Wie würde jemand diese Struktur in XML darstellen? Ich denke, Sie könnten argumentieren, dass das funktioniert: -)

Wenn das eine Interviewfrage ist, dann schlage ich demütig vor, dass Sie den Job vielleicht doch nicht wollen ...

Ich denke, wir konnten die HashTable-Datenstruktur in XML nicht "vernünftig" ausdrücken. Weil HashTable-Basis sagt, dass wir Daten in O (1) -Zeiten erhalten müssen, und wir machen es in Array möglich, indem wir jedes Objekt indexieren. Aber in XML ist es nicht möglich, wir müssen jedesmal xml durchlaufen, um ein Objekt zu erhalten.

So ziemlich alles kann in XML ausgedrückt werden. Ich denke, du würdest es vermeiden, wenn:

1. Encoding / Parsing XML wäre zu langsam für Ihren Zweck (zB in einem Videospiel) oder verbraucht zu viel Speicher (zB in einer Handy-App).

2. UND, Sie müssen nicht das Format von nichts außerhalb Ihrer eigenen Anwendung gelesen werden.

  

P.S .: Was bedeutet "sinnvoll" in der gestellten Frage?

     

    

[...] eine Datenstruktur, die nicht (vernünftig) in XML ausgedrückt werden kann.

  

     

Wenn Sie Ihr XML manuell schreiben, dann könnte ein niedriger Signal-zu-Rausch-Verhältnis (dh zu viele spitze Klammern, oft wiederholte Elementnamen) ein Grund sein, das XML als "nicht sinnvoll" zu bewerten. .

     

Meine Antwort berücksichtigt solche Probleme nicht. Ich glaube, dass XML als Datenaustauschformat besser geeignet ist, das von Computern geschrieben und gelesen wird, nicht von Menschen , und unter diesem Gesichtspunkt bedeutet "sinnvoll" etwas anderes (weil Sie nicht mehr das wiederholte Tippen oder Entschlüsselung, und die XML-Serializer-Software wird sich auch nicht beschweren):

     

    

"Wie schwierig ist es, konzeptionell eine Datenstruktur einem geeigneten XML-Schema zuzuordnen?"

  

Ich nehme an, das hängt vom konkreten verwendeten XML Schema ab.

XML selbst ist ein sehr allgemeines Format. Es ist nicht so sehr das XML-Format, das das begrenzt, was sich darin ausdrücken lässt. Im Vergleich zur natürlichen Sprache ähnelt XML eher Dingen wie Großschreibung und Zeichensetzung ("Orthographie") als Grammatik. Die "Grammatik" oder die Struktur eines gültigen Inhalts würde genauer in einem XML-Schema (XSD) platziert werden. In dieser Hinsicht ist es anders als die meisten Programmiersprachen, die normalerweise eine feste Grammatik haben.

Lassen Sie uns kurz abschweifen und eine Analogie machen. Nehmen wir an, die Eskimo-Sprache hat mehr Wörter für Schnee als die englische Sprache . Bedeutet das, dass die englische Sprache nicht in der Lage ist, die verschiedenen Schneearten genau zu beschreiben? Nein, es bedeutet nur, dass Sie anstelle eines präzisen Wortes einen ganzen Satz benötigen, um dieselbe Bedeutung zu übertragen. Mit anderen Worten, die englische Sprache ist flexibel genug, um Zirkumskriptionen zu erlauben.

Zurück zum XML: Wenn Sie ein XML-Schema benötigen, um Schnee zu beschreiben, und es fehlt für ein Element frobble genau das, "Schnee, der so gefroren ist, wie er normalerweise nach 17 Tagen ist" , dann können Sie vielleicht die notwendigen Elemente in das Schema einführen, mit denen Sie genau diese Beschreibung ausdrücken können.

Was würden Sie in einer anderen Programmiersprache als Sprachdesigner tun, wenn Sie herausfinden würden, dass Ihr Typsystem nicht leistungsfähig genug ist, um eine Datenstruktur zu beschreiben? Sie können das Typsystem einfach erweitern . (Zum Beispiel waren Generika in Java und C # nicht von Anfang an verfügbar. Es wäre auch möglich, C-style union s in C # einzuführen.) Dasselbe kann in XML getan werden, nur hier würden Sie nicht müssen die XML-Spezifikation oder die XML-Schema-Spezifikation erweitern, aber das konkrete XML-Schema verwenden.

Zusammenfassend möchte ich sagen, dass XML als Format keine Beschränkung für Inhalte, sondern nur für die Darstellungsform des Inhalts ("Orthographie") darstellt. Auf der anderen Seite definiert ein konkretes XML-Schema, was gültiger Inhalt ist und was nicht (Grammatik). Sie können eine beliebig einfache oder komplexe Grammatik erstellen, die Ihren Bedürfnissen entspricht.

Ich bin also überzeugt, dass es möglich ist, beliebige Datenstrukturen in XML zu beschreiben.

Jede Datenstruktur kann mit xml ausgedrückt werden.

Alle Daten können als Nullen und Einsen oder als "Bytes" ausgedrückt werden. Sie können alle Daten in druckbare Form codieren, z. mit Base64-Codierung, dann schreiben Sie einfach

und Sie haben XML! : D