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

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, как показано выше, а скорее древовидную структуру, которая представляет это.)

Что такое простой, эффективный код, который производит этот вывод?
У меня есть свое собственное решение, которое я опубликую в качестве ответа, но которое кажется мне менее чем идеальным.

Редактировать : Я забыл включить фактчто дерево должно быть отсортировано по убыванию на каждом уровне.Я добавил образцы узлов и изменил вывод, чтобы отразить это.

Answer 1

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

Answer 2

С чего начать?

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

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

Answer 3

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

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

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

Answer 4

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

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

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

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

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

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

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

Я знаю, что это больше, чем вы просили, но тот простой факт, что вы берете образцы стеков и ищете способ их суммировать, означает, что вы действительно на правильном пути, ИМО. Удачи.

---

P.S. Разве вы не хотите хранить включительно счетчиков на каждом узле, как в:

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

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

Answer 5

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

Answer 6

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

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)