草庐IT

xml - scala.xml.RuleTransformer 的复杂性真的呈指数级增长吗？

coder 2024-06-26 原文

这是 one 的后续行动我以前的帖子。

我试图理解为什么 RuleTransformer性能太差了。现在我相信它之所以这么慢是因为它的复杂度是 O(2n)，其中 n 是输入 XML 树的高度。

假设我需要将所有元素的所有标签重命名为标签“b”:

import scala.xml._, scala.xml.transform._

val rule: RewriteRule = new RewriteRule() {
  override def transform(node: Node): Seq[Node] = node match {
    case e: Elem => e.copy(label = "b")
    case other => other
  }
}

def trans(node: Node): Node = new RuleTransformer(rule).apply(node)

让我们数一数 transform 出现了多少次访问输入中的每个节点 <a3><a2><a1/></a2></a3> .
为了计算访问次数，我们添加了一个缓冲区 visited , 最开始初始化，存储访问过的节点，最后打印。

import scala.collection.mutable.ListBuffer

// buffer to store visited nodes
var visited: ListBuffer[Node] = ListBuffer[Node]()

val rule: RewriteRule = new RewriteRule() {
  override def transform(n: Node): Seq[Node] = {
    visited append (n) // count this visit
    n match {
      case e: Elem => e.copy(label = "b")
      case other => other
    }
  }
}

def trans(node: Node): Node = {
  visited = ListBuffer[Node]() // init the buffer
  val r = new RuleTransformer(rule).apply(node)
  // print visited nodes and numbers of visits 
  println(visited.groupBy(identity).mapValues(_.size).toSeq.sortBy(_._2))
  r
}

现在让我们在 REPL 中运行它并查看 visited 

scala> val a3 = <a3><a2><a1/></a2></a3>
a3: scala.xml.Elem = <a3><a2><a1/></a2></a3>

scala> trans(a3)
ArrayBuffer((<a3><b><b/></b></a3>,2), (<a2><b/></a2>,4), (<a1/>,8))
res1: scala.xml.Node = <b><b><b/></b></b>

所以 a1被访问了 8 次。

如果我们转换 <a4><a3><a2><a1/></a2></a3></a4>然后 a1将被访问 16 次，对于 <a5><a4><a3><a2><a1/></a2></a3></a4></a5> -- 32 等。所以复杂度看起来呈指数。

有意义吗？你如何通过分析 code 来证明它？ ？

最佳答案

这不是一个非常严格的分析，但问题似乎出在 BasicTransformer 的 transform(Seq[Node]) 方法 [1] 上。

对于改变的节点，子变换方法将被调用两次。由于这个原因，特别是在您的示例中，所有节点都将被调用两次。你是对的，高度为 h 的每个节点将被调用 2^(h-1) 次。另请注意，由于使用跨度和代码，最多一个节点的一个子节点将被调用两次，在特定示例中，节点的所有子节点将被调用两次。

只是为了验证这一点，为修改后的 RulesTransformer 编写了这些代码示例。 (我也可以覆盖 RulesTransformer。但无论如何)

// This is same as library RuleTransformer added with print statement
class CopiedRuleTransformer(rules: RewriteRule*) extends BasicTransformer {
    override def transform(n: Node): Seq[Node] = {
        println(n)
        rules.foldLeft(super.transform(n)) { (res, rule) => rule transform res }
    }
}

我修改后的 RuleTransformer

class MyRuleTransformer(rules: RewriteRule*) extends BasicTransformer {
    override def transform(n: Node): Seq[Node] = {
        println(n)
        rules.foldLeft(super.transform(n)) { (res, rule) => rule transform res }
    }  
    override def transform(ns:Seq[Node]): Seq[Node] = {
        ns.flatMap(n => transform(n))
    } 
}

这些代码仅用于演示目的。 您可以将它们称为 

new CopiedRuleTransformer(rule).apply(node)

或

new MyRuleTransformer(rule).apply(node)

[1] 行:34 https://github.com/scala/scala-xml/blob/master/src/main/scala/scala/xml/transform/BasicTransformer.scala

关于xml - scala.xml.RuleTransformer 的复杂性真的呈指数级增长吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30861880/

RuleTransformerxmlscalacodetransformtime-complexity

有关xml - scala.xml.RuleTransformer 的复杂性真的呈指数级增长吗？的更多相关文章

  1. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

    我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为

  2. ruby - 分布式事务和队列，ruby，erlang，scala - 2

    我有一个涉及多台机器、消息队列和事务的问题。因此，例如用户点击网页，点击将消息发送到另一台机器，该机器将付款添加到用户的帐户。每秒可能有数千次点击。事务的所有方面都应该是容错的。我以前从未遇到过这样的事情，但一些阅读表明这是一个众所周知的问题。所以我的问题。我假设安全的方法是使用两阶段提交，但协议(protocol)是阻塞的，所以我不会获得所需的性能，我是否正确？我通常写Ruby，但似乎Redis之类的数据库和Rescue、RabbitMQ等消息队列系统对我的帮助不大——即使我实现某种两阶段提交，如果Redis崩溃，数据也会丢失，因为它本质上只是内存。所有这些让我开始关注erlang和

  3. ruby - 使用 AES 的 Rails 加密，过于复杂 - 2

    我在加密来self正在使用的第三方供应商的值时遇到问题。他们的指令如下:1)Converttheencryptionpasswordtoabytearray.2)Convertthevaluetobeencryptedtoabytearray.3)Theentirelengthofthearrayisinsertedasthefirstfourbytesontothefrontofthefirstblockoftheresultantbytearraybeforeencryption.4)EncryptthevalueusingAESwith:1.256-bitkeysize,2.25

  4. ruby - 测试一个复杂的方法 - 2

    我正在开发西洋跳棋实现，其中有许多易于测试的方法，但我不确定如何测试我的主要#play_game方法。我的大多数方法都可以很容易地确定输入和输出，因此也很容易测试，但这种方法是多方面的，实际上并没有容易辨别的输出。这是代码:defplay_gameputs@gui.introwhile(game_over?==false)message=nil@gui.render_board(@board)@gui.move_requestplayer_input=getscoordinates=UserInput.translate_move_request_to_coordinates(play

  5. ruby - 是否有用于复杂比较的漂亮语法？ - 2

    方法应返回-1,0或1分别表示“小于”、“等于”和“大于”。对于某些类型的可排序对象，通常将排序顺序基于多个属性。以下是可行的，但我认为它看起来很笨拙:classLeagueStatsattr_accessor:points,:goal_diffdefinitializepts,gd@points=pts@goal_diff=gdenddefothercompare_pts=pointsother.pointsreturncompare_ptsunlesscompare_pts==0goal_diffother.goal_diffendend尝试一下:[LeagueStats.new(

  6. ruby-on-rails - 我真的需要在 Rails 中使用 csv gem 吗？ - 2

    我的问题很简单:我是否必须在使用RubyonRails的类上require'csv'？如果我打开一个railsconsole并尝试使用CSVgem它可以工作，但我必须在文件中这样做吗？ 最佳答案 CSVlibrary是ruby​​标准库的一部分；它不是gem(即第三方库)。与所有标准库(与核心库不同)一样，csv不会由ruby​​解释器自动加载。所以是的，在您的应用程序中某处您确实需要要求它:irb(main):001:0>CSVNameError:uninitializedconstantCSVfrom(irb):1from/Us

  7. ruby-on-rails - 如何构建复杂的 Rails 系统 - 2

    关闭。这个问题需要更多focused.它目前不接受答案。想改进这个问题吗？更新问题，使其只关注一个问题editingthispost.关闭8年前。Improvethisquestion我们有以下(以及更多)系统，我们将数据从一个应用推送/拉取到另一个:托管CRM(InsideSales.com)Asterisk电话系统(内部)横幅广告系统(openx，我们托管)潜在客户生成系统(自行开发)电子商务商店(spree，我们托管)工作板(本土)一些工作网站抓取+入站工作提要电子邮件传送系统(如Mailchimp，自主开发)事件管理系统(如eventbrite，自主开发)仪表板系统(大量图表和

  8. ruby-on-rails - 如何在 Rails 3 中禁用 XML 解析 - 2

    我想禁用HTTP参数的自动XML解析。但我发现命令仅适用于Rails2.x，它们都不适用于3.0:config.action_controller.param_parsers.deleteMime::XML(application.rb)ActionController::Base.param_parsers.deleteMime::XMLRails3.0中的等价物是什么？ 最佳答案 根据CVE-2013-0156的最新安全公告你可以将它用于Rails3.0。3.1和3.2ActionDispatch::ParamsParser::

  9. ruby - 强制 Ruby 不以标准形式/科学记数法/指数记数法输出 float - 2

    我遇到了同样的问题here对于python，但对于ruby​​。我需要输出这样一个小数字:0.00001，而不是1e-5。有关我的特定问题的更多信息，我正在使用f.write("Mynumber:"+small_number.to_s+"\n")输出到一个文件对于我的问题，准确性不是什么大问题，所以只做一个if语句来检查是否small_number那么更通用的方法是什么？ 最佳答案 f.printf"Mynumber:%.5f\n",small_number您可以将.5(小数点右侧5位数字)替换为您喜欢的任何特定格式大小，例如，%8

  10. ruby - 如何使用 Nokogiri::XML::Builder 生成动态标签？ - 2

    我正在遍历数组中的一组标签名称，我想使用构建器打印每个标签名称，而不是求助于“我认为:builder=Nokogiri::XML::Builder.newdo|xml|fortagintagsxml.tag!tag,somevalendend会这样做，但它只是创建名称为“tag”的标签，并将标签变量作为元素的文本值。有人可以帮忙吗？这个看起来应该比较简单，我刚刚在搜索引擎上找不到答案。我可能没有以正确的方式提问。 最佳答案 尝试以下操作。如果我没记错的话，我添加了一个根节点，因为Nokogiri需要一个。builder=Nokogi

随机推荐