Geek asks and answers

Combining the tree of named profile profiles in top-down summarization

I have an array of name arrays that can be represented in Ruby as follows:

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]
]

This is the output of the sampler, where each list of names represents a call stack for a particular pattern. I want to show them as a drop-down tree with named values, where the value in each node is the sum of the calls to this particular call path.

In the above input example, the output tree should be:

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

(I do not want to output ASCII as shown above, but is a tree structure that represents this.)

What is simple, efficient code that produces this output?
I have my own solution, which I will lay out as an answer, but which seems less ideal to me.

. , . , .

+3
6

[edit] ( ):

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 .

+3

?

>> samples.each_with_object(Hash.new(0)) { |arr, h| h[arr] += 1 } 
#=> {["a"]=>4, ["a", "c"]=>2, ["b"]=>3, ["a", "c", "d"]=>2, ["b", "c", "e"]=>2}

, group_by - .

, 1.8, inject each_with_object:

>> samples.inject(Hash.new(0)) { |h, arr| h[arr] += 1 ; h} 
#=> {["a"]=>4, ["a", "c"]=>2, ["b"]=>3, ["a", "c", "d"]=>2, ["b", "c", "e"]=>2}

, , ... , , .

+2

, , @MichaelKohl:

require 'pnode' # see below
root = PNode.new("root",0)
samples.group_by{ |o| o }.each do |callstack,instances|
  n = root; last_index = callstack.length-1
  callstack.each_with_index do |name,i|
    n = n[name]
    n.time += instances.length if i==last_index 
  end
end

root.sort!
puts root

# pnode.rb
class PNode
  attr_accessor :name, :time, :parent, :kids
  def initialize(name,time=0,parent=nil)
    @name, @time, @parent = name, time, parent
    @kids = []; @by_name = {}
  end
  def []( name )
    kids << (@by_name[name] = self.class.new(name,0,self)) unless @by_name[name]
    @by_name[name]
  end
  def sort!
    @kids.each(&:sort!).sort_by!{ |n| [-n.time,n.name] }
    self
  end
  def to_s(lv=0)
    [ "#{'..'*lv}#{name}:#{time}", *kids.map{|k| k.to_s(lv+1) } ].join("\n")
  end
end
+1

, , ? ?

, :

  • , , 100 , . .

  • , , , " ", , . , "", c , 6/17 .

  • , , . "" ( ), , . . , , .

  • , , / . ? , , /, - . - , , , 10 . / , (, ), , , , .
    , , , , . , , ( ), , .

  • , , , , . , . , . , , , , . , . .

, , , , , , , IMO. .

P.S. node, :

root:17
  a:12
    e:4
    c:4
      d:2
  b:5
    c:2
      e:2

( ) node. " ", 8 .

+1

, . , .

def to_tree(data)
  tree =  data.inject([0,{}]) do |cont, element|
    if element.empty?
      cont[0] += 1
    else
      node = element.shift
      cont[1][node] ||= []
      cont[1][node] << element
    end

    cont
  end

  tree[1].map do |k, v|
    tree[1][k] = to_tree(v)
  end

  [tree[0],tree[1].sort{|a,b| b[1][0] <=> a[1][0]}]
end

def p_tree(node_tree, node_name='root', node_level=0)
  p "#{' '*node_level}#{node_name}:#{node_tree[0]}"
  node_tree[1].each do |node|
    p_tree(node[1], node[0], node_level + 1)
  end
end

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]
]

p_tree(to_tree(samples))

, , , .

+1

Here is my less than perfect solution. In its defense, it was created with a change in input, so it is first converted to a data structure that was originally loaded:

PNode = Struct.new(:name,:time,:parent) do
  attr_writer :kids
  def kids; @kids||=[]; end
  def add( name, time=0 )
    self.class.new( name, time, self ).tap{ |n| kids << n }
  end
  def to_s(lv=0)
    [ "#{'..'*lv}#{name}:#{time}", *kids.map{|k| k.to_s(lv+1) } ].join("\n")
  end
end

module Enumerable
  def sum(init=0,method=:to_i)
    inject(init){ |sum,o| sum+o.send(method) }
  end
end

# Build a tree of calls
root = PNode.new('root',0)
samples.each do |callstack|
  n = root; last_index = callstack.length-1
  callstack.each_with_index do |name,i|
    n = n.add( name, i==last_index ? 1 : 0 )
  end
end

# Sum the tree values at each level
def top_down(nodes,lv=0,parent=nil)
  nodes.group_by(&:name).sort_by{ |name,ns|
    [ -ns.map(&:time).sum, name ]
  }.map{ |name,same_name_calls|
    self_time = same_name_calls.map(&:time).sum
    PNode.new(name,self_time,parent).tap do |x|
      x.kids = top_down( same_name_calls.map(&:kids).flatten, lv+1, x )
    end
  }
end

puts top_down(root.kids).map(&:to_s)
0
source

More articles:


All Articles