ruby - 将命名配置文件样本树合并为自上而下的总和

Question

我有一个名称数组，可以像这样用 Ruby 表示:

samples = [
  %w[a],
  %w[a c],
  %w[a],
  %w[a],
  %w[b],
  %w[b],
  %w[a],
  %w[a e],
  %w[a e],
  %w[a c d],
  %w[a c d],
  %w[b],
  %w[b c e],
  %w[b c e],
  %w[a c],
  %w[a e],
  %w[a e]
]

这些是采样分析器的输出，其中每个名称列表代表特定样本的调用堆栈。我想将它们显示为自上而下的命名值树，其中每个节点的值是对该特定调用路径的命中总和。

对于上面的示例输入，输出树应该是:

root:0
  a:4
    e:4
    c:2
      d:2
  b:3
    c:0
      e:2

(我不想要如上所示的 ASCII 输出，而是表示它的树结构。)

生成此输出的简单、高效的代码是什么？
我有自己的解决方案，我会将其作为答案发布，但在我看来不太理想。

编辑:我忘记包括树应该在每个级别按降序排序的事实。我添加了示例节点并更改了输出以反射(reflect)这一点。

Answer 1

[编辑] 具有函数式编程的递归 Tree 类(为了简单起见，我使用 ostruct):

require 'ostruct'

class Tree < OpenStruct 
  def self.new_from_array(plain)
    Tree.new(:node => "root", :count => 0, :children => children_from_array(plain))
  end

  def self.children_from_array(plain)
    plain.group_by(&:first).map do |node, group|
      terminal, leaves = group.map { |xs| xs.drop(1) }.partition(&:empty?)
      Tree.new(:node => node, :count => terminal.size, :children => children_from_array(leaves))
    end.sort_by(&:count).reverse    
  end

  def inspect(indent=0)
    node_info = " "*indent + "#{self.node}: #{self.count}" 
    ([node_info] + self.children.map { |tree| tree.inspect(indent+2) }).join("\n")
  end  
end

例子:

>> Tree.new_from_array(samples)
=>
root: 0
  a: 4
    e: 4
    c: 2
      d: 2
  b: 3
    c: 0
      e: 2

您可以自定义 inspect 以满足您的可视化需求。