无法用XML表示的数据结构？

Question

什么可能是不能(明智地)用XML表达的数据结构的例子？这是一个面试问题,我找不到任何相关内容.

Answer 1

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个子节点的节点,并且不需要标识符,因为节点顺序(与属性顺序不同)会被保留.
• 字典:将它们视为(键,值)元组的序列.
• 集合没有顺序,但我所知道的每个集合数据结构都在内部对元素进行排序(通过比较,通过散列和碰撞,或者仅仅通过初始情况下的插入顺序).当您要求数据结构枚举其元素时,要么使用该顺序,要么使用元素产生的任何顺序(如果它不同).
• 缺少数据结构？将其编码为记录(用图形替换带有间接的指针),然后将记录映射到具有每个记录成员的子节点或属性的节点.对于像链接列表这样的东西来说,这会变得很难看,但是对于它们来说,存在如上所述的更简单的表示.

这些表述都不是像你一样实打实的,但你可以与他们就好了,建立在内存中的实际数据结构的工作与正确的库一个小而简单的循环(如lxml的Python中的问题,部分原因是由于XPath的).

有一类数据结构不能很容易地映射到树.布尔矩阵,位掩码,等等,这从越来越下降到每件单位获得他们的效率,炸毁明显,当你使用几十个字节为每个元素(或每个true元素或每个false元素-问题依旧) .但是,较少以树为中心的编码可以解决这个问题.例如,您可以为一维位掩码存储base64字符串,并使用更高维度的序列(包括布尔矩阵).将这些位连接起来形成一个数字,并在base64中对其进行编码 - 或者更确切地说是在线进行以避免大精度算术.结果不是完全XML,但仍然足够简单,可以生成和解析.

因此,我无法为您提供无法在XML中合理表示的数据结构.它太笼统了,特别是当我们利用在base64等中嵌入任意二进制数据的能力时.如果你因为不是纯XML而拒绝它,那么带回家:在纯 XML中无法有效地表示位掩码和布尔矩阵.但请注意,纯XML编码仍然是合理的,它只需要占用大量空间.如果伪值的真实值很少(例如,非常密集或稀疏图的邻接矩阵),通过仅存储稀有的值并使另一个隐含,则可以减轻这种情况.

但是,这并不意味着XML是编码这些数据结构的最佳选择,甚至是不错的选择.它是一种流行的数据交换格式,但对于任何给定的数据结构,都有更简单,更有效的表示.因此,如果您不需要灵活性并且可以承担额外的工作,请不要使用它.或者使用其他通用数据格式之一..以上所有完美的YAML工作用更少的冗长描述的编码,甚至优于之类的东西映射和阵列内置了一些工作的树木成为你必须将它们编码为嵌套记录轻轻比较难看(读:列表/映射) ,但这就是你用编程语言代表它们的方式.我也很确定JSON可以处理所有这些,但由于我没有花费大量时间生成和解析它(我使用XML和YAML),我不能肯定地说.

Answer 2

表示无限系列元素的结构.例如,在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>