arrays - 在多个级别上同时合并哈希数组的复杂哈希

Question

我意识到有很多问题与这个问题有着不同程度的相似性。我已经为它们进行了详细搜索(使用:[ruby] merge array of hashes on key)，并且我尝试了每个答案的点点滴滴，试图自己解决这个问题。在来到 StackOverflow 之前，我什至与同样被难倒的同事们分享了我的问题。这似乎是一个独特的问题，或者我们都只是盯着它看得太近而看不到一个显而易见的答案。

基本要求

1. 该解决方案必须使用 Ruby 1.8.7 标准库(无 gem )。请随意额外说明适用于其他 Ruby 版本的解决方案，但这样做不会自动使一个答案比另一个更好。
2. 输入数据的结构不能被其提供者改变；整个数据结构按原样交付。如果需要临时重新排列数据以提供最有效的答案，只要输出与下面所需的样本相匹配就可以了。此外，该解决方案无法假设哈希中排序键的位置。
3. 源变量不能以任何方式改变；它在运行时是不可变的(已选中)，因此必须将结果提供给新变量。
4. 下面的示例数据是虚构的，但问题是真实存在的。还有其他级别的哈希数组也必须以相同的方式合并到其他键上；因此，最佳答案可以普遍应用于数据结构的任意级别。
5. 最好的解决方案是易于阅读、维护和适用于任意(尽管相似)数据结构。它不一定是单行代码，但如果您可以在一行 Ruby 代码中满足所有要求，那么恭喜您。

示例数据

如果我们将 Apache Tomcat server.xml 文件视为 Ruby 数据结构而不是 XML，它可以为这个问题提供一个很好的类比。进一步假设默认配置在上游(在交付给您之前)与数据合并，您必须在稍后的操作使用生成的数据结构之前合并这些数据。源数据看起来非常像这样:

source = {
  :Server => {
    :'attribute.port'     => 8005,
    :'attribute.shutdown' => 'SHUTDOWN',
    :Listener             => [
      { :'attribute.className'  => 'org.apache.catalina.startup.VersionLoggerListener' },
      { :'attribute.className'  => 'org.apache.catalina.core.AprLifecycleListener',
        :'attribute.SSLEngine'  => 'off'},
      { :'attribute.className'  => 'org.apache.catalina.core.JasperListener' },
      { :'attribute.className'  => 'org.apache.catalina.core.JreMemoryLeakPreventionListener' },
      { :'attribute.className'  => 'org.apache.catalina.core.AprLifecycleListener',
        :'attribute.SSLEngine'  => 'on'}
    ],
    :Service              => [
      { :'attribute.name' => 'Catalina',
        :Connector        => [
          { :'attribute.port'     => 8080,
            :'attribute.protocol' => 'HTTP/1.1'},
          { :'attribute.port'     => 8009,
            :'attribute.protocol' => 'AJP/1.3'}
        ],
        :Engine           => {
          :'attribute.name'         => 'Catalina',
          :'attribute.defaultHost'  => 'localhost',
          :Realm                    => {
            :'attribute.className'  => 'org.apache.catalina.realm.LockOutRealm',
            :Realm                  => [
              { :'attribute.className'    => 'org.apache.catalina.realm.UserDatabaseRealm',
                :'attribute.resourceName' => 'UserDatabase'}
            ]
          },
          :Host                     => [
            { :'attribute.name'     => 'localhost',
              :'attribute.appBase'  => 'webapps',
              :Valve                => [
                { :'attribute.className'  => 'org.apache.catalina.valves.AccessLogValve',
                  :'attribute.directory'  => 'logs'}
              ]
            }
          ]
        }
      },
      { :'attribute.name' => 'Catalina',
        :Connector        => [
          { :'attribute.port'         => 8080,
            :'attribute.protocol'     => 'HTTP/1.1',
            :'attribute.secure'       => true,
            :'attribute.scheme'       => 'https',
            :'attribute.proxyPort'    => 443}
        ]
      },
      { :'attribute.name' => 'JSVCBridge',
        :Connector        => [
          { :'attribute.port'         => 8010,
            :'attribute.protocol'     => 'HTTP/2'}
        ]
      },
      { :'attribute.name' => 'Catalina',
        :Engine           => {
          :Host => [
            { :'attribute.name'     => 'localhost',
              :Valve                => [
                { :'attribute.className'                => 'org.apache.catalina.valves.RemoteIpValve',
                  :'attribute.internalProxies'          => '*',
                  :'attribute.remoteIpHeader'           => 'X-Forwarded-For',
                  :'attribute.protocolHeader'           => 'X-Forwarded-Proto',
                  :'attribute.protocolHeaderHttpsValue' => 'https'}
              ]
            }
          ]
        }
      }
    ]
  }
}

挑战在于从中产生这个结果:

result = {
  :Server => {
    :'attribute.port'     => 8005,
    :'attribute.shutdown' => 'SHUTDOWN',
    :Listener             => [
      { :'attribute.className'  => 'org.apache.catalina.startup.VersionLoggerListener' },
      { :'attribute.className'  => 'org.apache.catalina.core.AprLifecycleListener',
        :'attribute.SSLEngine'  => 'on'},
      { :'attribute.className'  => 'org.apache.catalina.core.JasperListener' },
      { :'attribute.className'  => 'org.apache.catalina.core.JreMemoryLeakPreventionListener' },
    ],
    :Service              => [
      { :'attribute.name' => 'Catalina',
        :Connector        => [
          { :'attribute.port'         => 8080,
            :'attribute.protocol'     => 'HTTP/1.1',
            :'attribute.secure'       => true,
            :'attribute.scheme'       => 'https',
            :'attribute.proxyPort'    => 443},
          { :'attribute.port'     => 8009,
            :'attribute.protocol' => 'AJP/1.3'}
        ],
        :Engine           => {
          :'attribute.name'         => 'Catalina',
          :'attribute.defaultHost'  => 'localhost',
          :Realm                    => {
            :'attribute.className'  => 'org.apache.catalina.realm.LockOutRealm',
            :Realm                  => [
              { :'attribute.className'    => 'org.apache.catalina.realm.UserDatabaseRealm',
                :'attribute.resourceName' => 'UserDatabase'}
            ]
          },
          :Host                     => [
            { :'attribute.name'     => 'localhost',
              :'attribute.appBase'  => 'webapps',
              :Valve                => [
                { :'attribute.className'  => 'org.apache.catalina.valves.AccessLogValve',
                  :'attribute.directory'  => 'logs'},
                { :'attribute.className'                => 'org.apache.catalina.valves.RemoteIpValve',
                  :'attribute.internalProxies'          => '*',
                  :'attribute.remoteIpHeader'           => 'X-Forwarded-For',
                  :'attribute.protocolHeader'           => 'X-Forwarded-Proto',
                  :'attribute.protocolHeaderHttpsValue' => 'https'}
              ]
            }
          ]
        }
      },
      { :'attribute.name' => 'JSVCBridge',
        :Connector        => [
          { :'attribute.port'         => 8010,
            :'attribute.protocol'     => 'HTTP/2'}
        ]
      }
    ]
  }
}

问题

我们需要source 来变成result。为此，:Listener 被attribute.className 合并； :Service 被attribute.name合并； :Connector 的结果数组被 attribute.port 合并；等等。哈希数组在数据结构中的位置标识以及每个要合并的键应该很容易提供给解决方案。

这个问题的真正本质是找到可以应用于像这样的复杂数据结构的多个任意级别的通用解决方案，通过提供的键合并哈希数组，并在位置集之后生成合并结果并提供 key 对。

非常感谢大家花时间关注这个问题。

Answer 1

可能有更优雅的方法来压缩这段代码，但我最终找到了这个非常具有挑战性的问题的答案。虽然 Wand Maker 的答案很接近，但它基于一个站不住脚的假设，即哈希中键的顺序是可预测和稳定的。由于这是一个 Ruby 1.8.7 问题，而且由于数据提供者没有这样的保证，我不得不采取不同的途径；我们必须通知合并引擎为每个哈希数组使用哪个键。

我的(未优化的)解决方案需要三个函数和一个定义必要合并键的外部哈希:

1. deepMergeHash 遍历哈希，深度扫描数组
2. deepMergeArrayOfHashes 对哈希数组执行所需的合并
3. subMergeHelper 递归辅助deepMergeArrayOfHashes

诀窍不仅在于递归地处理散列，而且要始终注意散列中的“当前”位置，以便可以知道必要的合并 key 。建立了确定该位置的方法后，定义、查找和使用合并键变得微不足道。

解决方案

def subMergeHelper(lhs, rhs, mergeKeys, crumbTrail)
  lhs.merge(rhs){|subKey, subLHS, subRHS|
    mergeTrail = crumbTrail + ':' + subKey.to_s
    case subLHS
    when Array
      deepMergeArrayOfHashes(subLHS + subRHS, mergeKeys, mergeTrail)
    when Hash
      subMergeHelper(subLHS, subRHS, mergeKeys, mergeTrail)
    else
      subRHS
    end
  }
end

def deepMergeArrayOfHashes(arrayOfHashes, mergeKeys, crumbTrail)
  mergedArray = arrayOfHashes
  if arrayOfHashes.all? {|e| e.class == Hash}
    if mergeKeys.has_key?(crumbTrail)
      mergeKey = mergeKeys[crumbTrail]
      mergedArray = arrayOfHashes.group_by{|evalHash| evalHash[mergeKey.to_sym]}.map{|groupID, groupArrayOfHashes|
        groupArrayOfHashes.reduce({}){|memoHash, evalHash|
          memoHash.merge(evalHash){|hashKey, lhs, rhs|
            deepTrail = crumbTrail + ':' + hashKey.to_s
            case lhs
            when Array
              deepMergeArrayOfHashes(lhs + rhs, mergeKeys, deepTrail)
            when Hash
              subMergeHelper(lhs, rhs, mergeKeys, deepTrail)
            else
              rhs
            end
          }
        }
      }
    else
      $stderr.puts "[WARNING] deepMergeArrayOfHashes:  received an Array of Hashes without merge key at #{crumbTrail}."
    end
  else
    $stderr.puts "[WARNING] deepMergeArrayOfHashes:  received an Array containing non-Hashes at #{crumbTrail}?"
  end
  return mergedArray
end

def deepMergeHash(hashConfig, mergeKeys, crumbTrail = '')
  return hashConfig unless Hash == hashConfig.class
  mergedConfig = {}
  hashConfig.each{|nodeKey, nodeValue|
    nodeCrumb = nodeKey.to_s
    testTrail = crumbTrail + ':' + nodeCrumb
    case nodeValue
    when Hash
      mergedConfig[nodeKey] = deepMergeHash(nodeValue, mergeKeys, testTrail)
    when Array
      mergedConfig[nodeKey] = deepMergeArrayOfHashes(nodeValue, mergeKeys, testTrail)
    else
      mergedConfig[nodeKey] = nodeValue
    end
  }
  return mergedConfig
end

使用示例

使用问题中的数据，我们现在可以:

mergeKeys = {
  ':Server:Listener'                    => 'attribute.className',
  ':Server:Service'                     => 'attribute.name',
  ':Server:Service:Connector'           => 'attribute.port',
  ':Server:Service:Engine:Host'         => 'attribute.name',
  ':Server:Service:Engine:Host:Valve'   => 'attribute.className',
  ':Server:Service:Engine:Realm:Realm'  => 'attribute.className'
}

mergedConfig = deepMergeHash(source, mergeKeys)

我似乎无法执行像 (result == mergedConfig) 这样的成功相等性测试，但是对 mergedConfig 的目视检查表明它与 result 除了一些键的顺序改变。我怀疑这是使用 Ruby 1.8.x 的副作用，对于这个问题是可以接受的。

祝大家编码愉快，非常感谢您对本次讨论的兴趣。