Как удалить частичные элементы в Hash of Arrays?

Question

У меня есть этот хэш:

{"path_1" => [1,2,3], "path_2" => [1,4,5], "path_3" => [1,2,3,4]}

Я хочу удалить все "частичные" пути из хеша. Так что path_1 нужно будет идти, потому что это часть path_3; [1,2,3] является "незаконченным" массивом [1,2,3,4]. Все "частичные" должны быть удалены из этого хеша.

Вот мой текущий код, который работает, но работает медленно при работе с большими хэшами:

# hash sorted by length of value
hash_array = {"path_1" => [1,2,3], "path_2" => [1,4,5], "path_3" => [1,2,3,4]}
# make a separate copy of the hash
cloned_hash_array = hash_array.clone

hash_array.each {|path_index, path|
  # delete this path from the cloned hash so it doesn't match itself
  cloned_hash_array.delete(path_index)

  cloned_hash_array.each{|cloned_path_index, cloned_path|
    if cloned_path[0,path.length] == path.clone
      hash_array.delete(path_index)
    end
  }
}

Answer 1

Зависит от того, насколько быстро вы хотите и сколько элементов у вас есть.Вы можете попробовать что-то вроде этого (выглядит сумасшедшим, но это действительно быстро):

scatter = 
  lambda { |tree, path, name|
    if path.empty?
      tree[:tag] = name
      tree[:path] unless tree.has_key?(:path)
    else
      head, *tail = path
      unless tree[:path].has_key?(head)
        tree[:path][head] = {:path => {}}
      end
      scatter[tree[:path][head], tail, name]
    end
  }

gather = 
  lambda { |tree|
    if tree[:path].empty?
      [[tree[:tag], []]]
    else
      tree[:path].map { |k, v|
        gather[v].map do |tag, path|
          [tag, [k] + path]
        end
      }.flatten(1)
    end
  }

scatter_gather =
  lambda { |paths|
    tree = {:path => {}}
    paths.each do |tag, path|
      scatter[tree, path, tag]
    end
    Hash[gather[tree]]
  }

scatter_gather["path_1" => [1,2,3], "path_2" => [1,4,5], "path_3" => [1,2,3,4]]
#=> {"path_2"=>[1, 4, 5], "path_3"=>[1, 2, 3, 4]}

Answer 2

Вы можете попробовать это, должно быть немного быстрее (двойной петли нет).

h = {"path_1" => [1,2,3], "path_2" => [1,4,5], "path_3" => [1,2,3,4]}

h2 = {}

a = h.sort{|l, r| r[1] <=> l[1]}
puts a.inspect
# => [["path_2", [1, 4, 5]], ["path_3", [1, 2, 3, 4]], ["path_1", [1, 2, 3]]]

last_path = nil
a.each do |key, path|
  # now all paths are sorted in descending order. 
  # if a current path is a prefix for last_path, then discard it.
  # otherwise, write it to a result and start comparing next ones against it.
  if !last_path || last_path[0, path.length] != path
    h2[key] = path
    last_path = path
  end
end

puts h2.inspect
# => {"path_2"=>[1, 4, 5], "path_3"=>[1, 2, 3, 4]}

Answer 3

Как насчет этого:

hash_array = {"path_1" => [1,2,3], "path_2" => [1,4,5], "path_3" => [1,2,3,4]}
cloned_hash_array = hash_array.clone

cloned_hash_array.each do |key, value|

  hash_array.each do |key2, value2|
    if key != key2 and value.length <= value2.length
      if value.all? { |i| value2.include?(i) }
        cloned_hash_array.delete(key)
        break
      end
    end
  end
end

puts cloned_hash_array.inspect