根据散列中的键值对散列数组进行排序？

Question

我正在尝试与 Vagrant 合作，在启动 Docker 容器时执行一些自动化操作。 Vagrantfiles 本质上是 Ruby，因此我应该能够应用 Ruby 逻辑来帮助解决这个问题。

我正在阅读一个 conf.d 目录，该目录充满了包含配置数据的 YAML 文件，然后将配置项的哈希值推送到一个数组中。完成后，我将使用 .each 遍历数组，并根据散列中某些键的值将配置应用于数组中的每个条目。其中一个键是 "link"。 link 的值将关联到另一个键 "name".

的值

我基本上需要确保带有 link => 'name' 的散列在带有 name => 'value' 的散列之前的数组中。

输入和预期输出示例：

输入

containers = [{"name"=>"foo", "ports"=>["80:80", "443:443"], "links"=>["bar", "baz"]}, {"name"=>"bar", "ports"=>["8888:8888"]}, {"name"=>"baz","ports"=>"80:80"}]

预期输出

containers = [{"name"=>"bar", "ports"=>["8888:8888"]}, {"name"=>"baz", "ports"=>"80:80"}, {"name"=>"foo", "ports"=>["80:80", "443:443"], "links"=>["bar", "baz"]}]

最终结果是，任何带有 "link" 的条目都会出现在数组中哈希的名称键与其匹配的条目之后。（基本上是基于 link 键的依赖排序。）

请注意，一个 linked 容器 link 到另一个 linked 容器可能会发生。

这让我有点困惑，因为我知道我需要做什么，但缺乏实际弄清楚的技术印章 "How?" :)

在此先感谢您的帮助。

Answer 1

在我看来最简单的事情是这样的：

linkless_configs = []
linked_configs = []
if config_hash.has_key?("links")
  linked_configs.push(config_hash)
else
  linkless_configs.push(config_hash)
end

然后您可以遍历 linkless_configs + linked_configs 并确保每个 linked 配置都在相应的 link-less 配置之后。

或者，如果您必须排序，您可以

containers.sort_by { |config| config.has_key?("links") ? 1 : 0 }

Answer 2

[编辑： @DavidGrayson 指出了我的回答中的一个缺陷。我会看看是否可以找到修复程序，但如果找不到，我担心可能是这种情况，我会删除答案。 [编辑#2：天哪！在我最初编辑后，有人对我的回答投了赞成票。我不确定现在是否可以删除它，但说实话，我已经决定不这样做，主要是因为我的解释对 OP 问题的任何拟议解决方案都有影响。天平上有 10 分，留下来现在更有说服力。 2#tidE]

我相信我理解了这个问题。 sort 需要全序，这是一个偏序，其中每对元素为 a <= b 或 a <= b。 ref 后者不是问题，偏序要求是。偏序必须满足以下公理：

自反性 (x ≤ x),
反对称（如果 x ≤ y 和 y ≤ x 那么 x = y）和
传递性（如果 x ≤ y 和 y ≤ z，则 x ≤ z）。

我的排序只满足自反性公理。大卫给出了反例：

containers = [h0, h1, h2]

哪里

h0 = {'name'=>'foo', 'links'=>['bar']},
h1 = {'name'=>'a'},
h2 = {'name'=>'bar'},

containers.sort
  #=> [{"name"=>"foo", "links"=>["bar"]},
  #    {"name"=>"a"}, {"name"=>"bar"}]

我的方法Hash#<=>建立：

h0 = h1
h0 > h2
h1 = h2

如果 sort 找到 h0 = h1 = h2，它会根据传递性得出结论 h0 = h2（而不检查 h0 <=> h2），这可能会导致不正确的结果。

David 还指出 o.follows?(self) 应该引发异常，因为我将其定义为 private。由于我还没有遇到异常，我断定语句没有被执行，但我没有追查原因，但这是一个小问题（尽管无疑是一个有用的线索）。

感谢 David 发现了问题。当然，不正确的答案需要曝光，但我觉得我也学到了一些有用的东西。

tidE]

如果我正确理解了问题，并且数据提供了有效的排序，我想你可以按如下方式进行。

class Hash
  def <=>(o)
    case
    when   follows?(o)    then  1
    when o.follows?(self) then -1
    else                        0
    end
  end

  private

  def follows?(o)
    key?("links") && self["links"].include?(o["name"])
  end
end

containers = [{"name"=>"foo", "ports"=>["80:80", "443:443"],
               "links"=>["bar", "baz"]},
              {"name"=>"bar", "ports"=>["8888:8888"]},
              {"name"=>"baz","ports"=>"80:80"}]

containers.sort
  #=> [{"name"=>"baz", "ports"=>"80:80"},
  #    {"name"=>"bar", "ports"=>["8888:8888"]},
  #    {"name"=>"foo", "ports"=>["80:80", "443:443"],
  #     "links"=>["bar", "baz"]}]

附录

尽管我以数据提供有效排序的假设开头，@Ajedi32 询问当存在循环引用时会发生什么。让我们找出答案：

containers = [{"name"=>"foo", "links"=>["bar"]},
              {"name"=>"bar", "links"=>["baz"]},
              {"name"=>"baz", "links"=>["foo"]}]
containers.sort
  #=> [{ "name"=>"baz", "links"=>["foo"] },
  #    { "name"=>"bar", "links"=>["baz"] },
  #    { "name"=>"foo", "links"=>["bar"] }]

containers = [{"name"=>"foo", "links"=>["bar"]},
              {"name"=>"bar", "links"=>["foo"]}]
containers.sort
  #=> [{ "name"=>"bar", "links"=>["foo"] },
  #    { "name"=>"foo", "links"=>["bar"] }]

这表明，如果不确定是否存在循环引用，则应在排序前进行检查。

Answer 3

这应该适合你：

def order_containers(containers)
  unordered = containers.dup
  ordered = []
  names_from_ordered = {}
  name_is_ordered = names_from_ordered.method(:[])
  until unordered.empty?
    container = unordered.find do |c|
      c.fetch('links', []).all? &name_is_ordered
    end
    raise 'container ordering impossible' if !container
    ordered << container
    unordered.delete(container)
    names_from_ordered[container.fetch('name')] = true
  end
  ordered
end

containers = [
  { 'name'=>'foo', 'links'=>['bar'] },
  { 'name'=>'a', 'links'=>['goo'] },
  { 'name'=>'bar' },
  { 'name'=>'goo', 'links'=>['foo'] },
]

containers = order_containers(containers)

require 'pp'
pp containers
# => [{"name"=>"bar"},
#     {"name"=>"foo", "links"=>["bar"]},
#     {"name"=>"goo", "links"=>["foo"]},
#     {"name"=>"a", "links"=>["goo"]}]

基本思路是我们使用循环，循环的每次迭代都会从输入列表中找到一个适合添加到输出列表的容器。如果一个容器所依赖的所有容器都已经添加到输出列表中，则该容器适合添加到输出列表中。然后容器从输入列表中删除并添加到输出列表中。

这个循环可以通过两种主要方式终止：

当输入列表为空时，表示成功，或者
当我们找不到可以启动的容器时，这将是循环依赖导致的错误。

根据散列中的键值对散列数组进行排序？

Sort array of hashes based on value of key in hash?

ruby

vagrant