Объединение дерева выборок именованных профилей в нисходящее суммирование

[edit] Рекурсивный класс 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 в соответствии с вашими потребностями в визуализации.

Это поможет вам начать?

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

Извините, я ухожу сейчас, так что у меня мало времени... Если этого недостаточно, напишите комментарий, и я постараюсь ответить позже.

Вот гораздо лучший ответ, чем мой первый, вдохновленный @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

Вот простой рекурсивный метод, который создаст дерево. Это может быть легко адаптировано на основе методов, которые вам понадобятся.

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

Метод, который в настоящее время печатает дерево, можно легко изменить, чтобы вместо этого создать объект дерева.

Чтобы попытаться ответить на вопрос, нельзя ли просто построить дерево, вставляя каждый образец по одному? и сортировать их по ходу или в конце?

Если вы не возражаете против некоторых дополнительных предложений, проиллюстрированных этим примером :

• Если вы беспокоитесь об эффективности из-за того, что у вас есть миллионы образцов стека, если вы просто случайным образом используете около 100 из них, вы получите достаточно информации для поиска узких мест. И вот почему.< /а>

• Проблема с построением дерева, корнем которого является основная программа, заключается в том, что на самом деле может не быть «горячего пути», даже если есть добросовестное «горячее узкое место», как показано в этом примере. Решение состоит в том, чтобы позволить пользователю выбрать любую процедуру в качестве «корня», например c в вашем примере, которая активна 6/17 времени.

• Когда вы получаете каждый образец стека, вы получаете не только имя подпрограммы, но и номер строки. Если пользователя интересует "горячая" процедура (которая появляется во многих образцах), он захочет знать, где внутри процедуры было потрачено время. Эта информация содержится в этих номерах строк. Поэтому я предлагаю использовать линии, а не подпрограммы, в качестве основной единицы построения дерева.

• Предположим, что есть рекурсия, поэтому одна и та же процедура/строка может появляться в образце более одного раза. Что вы делаете? Ну, независимо от того, сколько раз подпрограмма/строка появляется в сэмпле, это все равно только один семпл. Стоимость строки — это просто доля выборок, которые ее содержат, с рекурсией или без нее, потому что предположим, что вы берете выборки каждые 10 мс. Если бы эту подпрограмму/строку можно было сделать так, чтобы она не требовала времени (скажем, путем ее удаления или исключения), все образцы, содержащие ее, исчезли бы из общего количества, рекурсии или нет.
  Итак, если я создаю представление бабочки, ориентированное на одну строку, мне нужно показать только один слой вызовов под ним и один выше. Поэтому я строю локальное нисходящее дерево, показывающее только те строки, которые появились ниже фокуса (в образцах), а также для восходящего дерева, независимо от рекурсии.

• По моему опыту, я часто делаю это вручную, и автоматизация могла бы помочь, но когда я хочу исследовать конкретную горячую линию, я хочу иметь возможность видеть отдельные образцы стека, проходящие через эту линию. Причина в том, что я не забочусь об измерении. Я знаю, что это жарко. Меня волнует, почему он делал то, что делал, поэтому я знаю, смогу ли я обойтись без него. Вот что говорят мне образцы стека. Простого взгляда на горячую линию недостаточно.

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

потому что это скажет вам стоимость (в смысле потенциальной экономии) каждого узла. Если вас беспокоит «эксклюзивное время», обратите внимание на пункт 8 этого поста.

Вот мое далеко не идеальное решение. В свою защиту скажу, что он был создан с изменяющимся вводом, поэтому сначала он преобразуется в структуру данных, которая была изначально введена:

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)