Как удалить частичные файлы в массиве массивов?

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