8

XMLで（賢明に）表現できなかったデータ構造の例は何でしょうか？これはインタビューの質問であり、私はこれについて何も見つけることができません。

4

8 に答える 8

6

tl; drわからないので、たくさんのデータ構造を試しました。ただし、一部の表現は適度に非効率的であるため、完全に賢明な場合でも、必ずしも最良のオプションとは限りません。

それは難しい質問です。XMLはかなり制限のないツリーであり、すでにすべてのデータ構造の半分をカバーしています。最もエキゾチックで複雑なツリーでさえ、まだツリーです。vBEツリーの作成と操作についてはまだよくわかりませんが、特定のvBEツリーをXMLに変換できるように、それがツリーであることはわかっています。

各ノードにIDを割り当てるか、リファラーの子にすることなくノードを参照するための別の軽量スキームを考案すれば、あらゆる種類のグラフを問題なく作成できます。そして、グラフは、一般的なデータ構造のほとんどすべてであり、すべてです。たとえば、有向非巡回グラフは次のようになります。

<graph>
  <vertex id="1">
    <!-- vertex data -->
    <edge to="3"/>
  </vertex>
  <vertex id="2">
    <!-- vertex data -->
    <edge to="1"/>
    <edge to="3"/>
  </vertex>
  <vertex id="3">
    <!-- vertex data -->
    <edge to="1"/>
    <edge to="2"/>
  </vertex>
</graph>

これが隣接リストにどのようにマッピングされるかは明らかです。ハイパーグラフ（エッジには任意の数の頂点を含めることができます）などのさらに複雑なグラフがサポートされている場合は、頂点参照のリストを含むエッジの個別のリストが必要です（リストについては以下を参照）。

より一般的なデータ構造は、XMLへのマッピングがさらに簡単です。

  • 配列、リスト、キュー、スタック、およびその他の順序付けられたフラットなコレクション：各アイテムをノードにし、<seq>兄弟になるように単一の親ノードに配置します。
  • タプル（k値）：各アイテムに識別子を割り当ててから、それらを属性にします。または、<tuple>k個の子を持つノードを作成します。ノードの順序（属性の順序とは異なり）が保持されるため、識別子は必要ありません。
  • 辞書:(キー、値）タプルのシーケンスとして扱います。
  • セットには順序はありませんが、私が知っているすべてのセットデータ構造は、要素を内部的に順序付けます（比較、ハッシュと衝突、または単純な場合は挿入順序）。データ構造に要素を列挙するように要求するときは、その順序、または要素が生成される順序（異なる場合）を使用します。
  • データ構造がありませんか？それをレコードとしてエンコードし（グラフで使用されるようにポインターを間接参照に置き換えます）、レコードをすべてのレコードメンバーの子ノードまたは属性を持つノードにマップします。これは、リンクリストのようないくつかのものでは醜くなりますが、それらの場合、上記で概説したように、より単純な表現が存在します。

これらの表現はどれも実際の取引ほど優れていませんが、それらをうまく処理でき、メモリ内に実際のデータ構造を構築することは、適切なライブラリ（たとえば、Pythonのlxmlなど）を使用した小さくて単純なループの問題です。 XPath）。

木に簡単にマッピングできないデータ構造のクラスが1つあります。要素ごとに1ビットまで下げることで効率を上げるブール行列やビットマスクなどは、各要素（または各true要素、または各false要素-問題は残ります）に数十バイトを使用すると大幅に爆発します。ただし、ツリー中心ではないエンコーディングで解決できます。たとえば、1次元ビットマスクのbase64文字列を格納し、それらのシーケンスを高次元（ブール行列を含む）に使用できます。ビットを連結して数値を形成し、base64でエンコードします。つまり、高精度の算術演算を回避するためにオンラインでエンコードします。結果は完全にXMLではありませんが、それでも生成および解析するのに十分単純です。

したがって、XMLで適切に表現できないデータ構造を提供することはできません。特にbase64などに任意のバイナリデータを埋め込む機能を悪用する場合は、一般的すぎます。純粋なXMLではないという理由でそれを拒否する場合は、持ち帰ってください。ビットマスクとブール行列は純粋なXMLでは効率的に表現できません。ただし、純粋なXMLエンコーディングは依然として賢明であり、多くのスペースを必要とすることに注意してください。そして、それでも、偽の値の真のいずれかがまれである場合（たとえば、非常に密なグラフまたはまばらなグラフの隣接行列）、よりまれな値のみを格納し、もう一方を暗黙的にすることで軽減できます。

ただし、それはXMLが最適であることを意味するものではありません、またはこれらのデータ構造をエンコードするための適切な選択です。これは一般的なデータ交換形式ですが、特定のデータ構造に対して、より単純で効率的な表現があります。したがって、柔軟性が不要で、余分な作業を行う余裕がある場合は、それを使用しないでください。または、他の汎用データ形式の1つを使用します。上記のすべてのエンコーディングは、冗長性の少ないYAMLで完全に機能し、マッピングや配列などが組み込まれているため、さらにうまく機能するものもあります。ツリーは、ネストされたレコードとしてエンコードする必要があるため、少し醜くなります（読み取り：リスト/マッピング）。 、しかしそれはとにかくプログラミング言語でそれらを表現する方法です。また、JSONがそれらすべてを処理できることもかなり確信していますが、JSONの生成と解析に多くの時間を費やしていなかったため（XMLとYAMLを使用しました）、はっきりとは言えません。

于 2012-06-23T09:58:58.853 に答える
5

無限の一連の要素を表す構造。たとえば、scalaでは、次のようにフィボナッチ数列を作成できます。

lazy val fibs: Stream[Int] 
  = 0 #:: 1 #:: ((fibs zip fibs.tail) map { case (n, s) => n + s })

誰かがこの構造をXMLでどのように表現しますか？私はあなたがこれがうまくいくと主張することができると思います:-)

<structure lang="scala">
  <[[CDATA [
  lazy val fibs: Stream[Int] 
    = 0 #:: 1 #:: ((fibs zip fibs.tail) map { case (n, s) => n + s })
  ]>
</structure>
于 2012-06-25T21:22:34.797 に答える
4

これが面接の質問であるなら、私は謙虚にあなたが結局その仕事を望まないかもしれないことを提案します...

于 2012-06-25T22:41:29.633 に答える
2

HashTableのデータ構造をXMLで「賢明に」表現することはできなかったと思います。HashTableの基本では、O（1）回でデータを取得する必要があると述べているため、すべてのオブジェクトのインデックスを作成することで、配列でデータを取得できるようになります。しかし、XMLではそれは不可能であり、オブジェクトを取得するために毎回xmlをトラバースする必要があります。

于 2012-07-01T06:29:35.660 に答える
1

ほとんどすべてのものをXMLで表現できます。次の場合は避けてください。

  1. XMLのエンコード/解析は、目的（ビデオゲームなど）には遅すぎるか、メモリの消費量が多すぎます（携帯電話アプリなど）。

  2. また、独自のアプリケーション以外でフォーマットを読み取る必要はありません。

于 2012-06-23T10:37:10.867 に答える
1

すべてのデータ構造は、xmlを使用して表現できます。

すべてのデータは、0と1、または「バイト」として表すことができます。すべてのデータを印刷可能な形式にエンコードできます。たとえば、base64エンコードを使用して、次のように記述します。

<data>your_base64_data</data>

そしてあなたはXMLを持っています！：D

于 2012-06-25T21:29:24.077 に答える
1

PS：質問された質問の「賢明な」とはどういう意味ですか？

[...] XMLで（賢明に）表現できなかったデータ構造。

XMLを手動で書き出す場合、信号対雑音比が低い（つまり、山かっこが多すぎる、要素名が頻繁に繰り返される）ことが、XMLを「意味がない」と判断する理由になる可能性があります。

私の答えはそのような問題を考慮していません。XMLは、人間ではなく機械によって読み書きされるデータ交換形式としてより有用であると私は信じています。この観点から、「賢明な」とは別のことを意味します（繰り返しの入力や解読、およびXMLシリアライザーソフトウェアを実行しなくなったため）どちらも文句を言わない）：

「データ構造を適切なXMLスキーマに概念的にマッピングすることはどれほど難しいですか？」

これは、使用される具体的なXMLスキーマに依存すると思います。

XML自体は、非常に一般的な形式です。表現できるものを制限するのは、XML形式ではありません。自然言語と比較すると、XML自体は、文法よりも大文字と句読点（「正書法」）のようなものに似ています。「文法」、つまり有効なコンテンツの構造は、XMLスキーマ（XSD）により正確に配置されます。この点で、通常1つの固定文法を持つほとんどのプログラミング言語とは異なります。

簡単に逸脱して、類推してみましょう。エスキモー語には英語よりも雪の単語が多いと仮定しましょう。それは、英語がさまざまな形の雪を正確に説明できないことを意味しますか？いいえ、それは、1つの正確な単語ではなく、同じ意味を転送するために1文全体が必要になる可能性があることを意味するだけです。言い換えれば、英語は限界を許容するのに十分な柔軟性があります。

XMLに戻る：雪を記述するためのXMLスキーマが必要であり、 「17日後に通常と同じように凍結する雪」frobbleを正確に意味する要素がない場合は、必要な要素をに導入できます。その説明を表現できるスキーマ。

別のプログラミング言語では、型システムがデータ構造を記述するのに十分なほど強力ではないことがわかった場合、言語デザイナーとして何をしますか？型システムを拡張するだけかもしれません。（たとえば、ジェネリックは最初からJavaとC＃では利用できませんでした。CスタイルunionをC＃に導入することも可能です。）XMLでも同じことができますが、ここでのみ拡張する必要はありません。 XML仕様でもXMLスキーマ仕様でもありませんが、使用されている具体的なXMLスキーマです。

結論として、私の主なポイントはこれです。フォーマットとしてのXMLはコンテンツに制限を課さず、コンテンツの表現形式（「正書法」）にのみ制限を課します。一方、具体的なXMLスキーマは、有効なコンテンツとそうでないコンテンツ（文法）を定義します。ニーズに合わせて、任意の単純または複雑な文法を考え出すことができます。

したがって、 XMLで任意のデータ構造を記述できると確信しています。

于 2012-06-23T10:38:04.337 に答える
1

ビットのシーケンスで任意のデータ構造を表すことができるのと同じように、XMLで任意のデータ構造を表すことができます。それはすべて、表現がどれほど便利かという問題です。たとえば、XMLは一般的なグラフを表すのに特に理想的ではありませんが、確かに実行できます。

于 2012-06-23T13:35:37.490 に答える