递归地将Map[Int, Map[Int, X]]转换为Array[Array[X]]

Question

递归地将Map[Int, Map[Int, X]]转换为Array[Array[X]]

arraysscalamapsgeneric-programmingscala-collections

3

我正在尝试编写一个函数，将具有整数键的Map转换为相应的数组。我已经完成了基本情况，但正在尝试编写递归情况（即多维数组：将Map [Int，Map [Int，X]]转换为Array [Array [X]]）。

这个任务是因为需要在不知道流中元素数量的情况下构建一个数组，允许元素以随机顺序从流中出现并且可能会出现重复元素。

我已经有一个可以实现此功能的函数：

def toArrayHard[X:ClassManifest](x:scala.collection.Map[Int, X]):Array[X] =
{
    if (x.size == 0) new Array(0)
    else 
    {
        val max:Int = 1 + x.keys.max

        val a:Array[X] = new Array(max)

        var i = 0
        while (i < max)
        {
            a(i) = x(i)
            i += 1
        }
        a
    }
}

注意，我知道如果映射包含键k但不包含0 <= i < k的键i，则代码将失败。对于我的目的来说，这没关系。

现在我想要对任意深度的多维数组做同样的事情。例如，将Map [Int，Map [Int，X]]转换为Array [Array [X]]。不幸的是，我被类型所困扰。以以上为基础情况，这是我目前的进展：

def toArrayHardRec[X:ClassManifest](x:scala.collection.Map[Int, X]):Array[X] =
{
    import scala.collection.Map

    if (x.size == 0) new Array(0)
    else 
    {
        x match
        {
            case t:Map[Int, Map[Int, Y]] forSome { type Y } =>
            {
                val f0 = t.mapValues{m => toArrayHardRec[Map[Int, Y]](m)}
                toArrayHard(f0)
            }
            case _ => toArrayHard(x)
        }
    }
}

这是我收到的错误信息：

期望 '=>'，但找到了 'forSome'。

由于这是一个教育性的追求，任何反馈都非常感谢。具体来说，我希望对我的类似Java的代码进行代码审查，寻找现有的Scala函数来完成相同的任务，或者提出构建这些数组的替代方法的建议。

- dsg

你应该避免将 { 放在下一行。这可能会导致分号推断出现问题。 - BenjaminJackman

@KingCub：你是什么意思？能给个例子吗？ - dsg

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel C. Sobral · Accepted Answer

这是毫无意义的：

case t:Map[Int, Map[Int, Y]] forSome { type Y }

由于擦除，您只能检查到以下内容：

case t: Map[_, _]

事实上，这是你不会收到有关擦除的警告唯一的方式。此外，存在类型几乎总是不必要的，并且个人而言，我总是觉得它的语法有点棘手。但是，在这种情况下，使用 _ 表示存在类型是足够的。请注意，如果我这里自己的代码（第一个版本）中使用它，类型将不匹配。

接下来，任意深度的多维数组并不是一个特别好的想法。您必须知道将返回什么类型以声明它--如果深度是“任意”的，那么类型也是“任意”的。您可以使用 Array[AnyRef]，但使用起来会很痛苦。

不过，以下是一种方法。我放弃了所有循环，用 map 替换了它们。请注意，我利用了 Map 也是一个 Function1 的事实，通过调用 map m 来实现。还请注意，我只是在数组上使用 map（使用 toArray 创建），以避免管理映射的创建。

def deMap(m: Map[Int, AnyRef]): Array[AnyRef] = {
  def translate(x: AnyRef): AnyRef = x match {
    case map: Map[Int, AnyRef] => deMap(map)
    case s: String => s
    case other => throw new IllegalArgumentException("Expected Map or String, got "+other.getClass.toString)
  }
  m.keys.toArray.sorted map m map translate
}

有两个问题。首先，如果键不是连续的（例如Map(0 -> "a", 2 -> "b")），元素将会错位。以下是解决方法，将代码的倒数第二行替换为：

  Array.range(0, m.keys.max + 1) map (m getOrElse (_, "")) map translate

在这里，我使用空字符串来代表数组中的任何一个洞。

另一个问题是我假设所有的映射都是Map[Int, AnyRef]类型。为了解决这个问题，代码必须重写如下：

def deMap(m: Map[Int, AnyRef]): Array[AnyRef] = {
  def translate(x: AnyRef): AnyRef = x match {
    case map: Map[_, _] => 
      val validMap = map collect { case (key: Int, value: AnyRef) => (key -> value) }
      deMap(validMap)
    case s: String => s
    case other => throw new IllegalArgumentException("Expected Map or String, got "+other.getClass.toString)
  }
  Array.range(0, m.keys.max + 1) map (m getOrElse (_, "")) map translate
}

在这里，我舍弃了所有键不是Int和值不是AnyRef的对。可以进一步安全检查代码以测试是否有遗漏，并在这种情况下报告错误：

def deMap(m: Map[Int, AnyRef]): Array[AnyRef] = {
  def translate(x: AnyRef): AnyRef = x match {
    case map: Map[_, _] => 
      val validMap = map collect { case (key: Int, value: AnyRef) => (key -> value) }
      if (map.size > validMap.size) {
        val wrongPairs = map.toSeq diff validMap.toSeq
        throw new IllegalArgumentException("Invalid key/value pairs found: "+wrongPairs)
      }
      deMap(validMap)
    case s: String => s
    case other => throw new IllegalArgumentException("Expected Map or String, got "+other.getClass.toString)
  }
  Array.range(0, m.keys.max + 1) map (m getOrElse (_, "")) map translate
}

最后，关于性能问题。像我这样使用 map 会为每个 map 分配一个新的数组。有些人认为这意味着我必须进行三次迭代而不是一次，但由于每次都要执行不同的任务，所以实际上没做更多的工作。然而，每次分配一个新的数组都会影响性能 -- 部分因为分配惩罚 (Java 预先初始化所有数组)，还有因为缓存局部性问题。

避免这种情况的一种方法是使用 view。当你在 view 上进行 map、flatMap 和 filter 操作时，你会得到一个带有该操作的新的存储用于将来使用的 view（其他方法也可能以此方式工作--检查文档或在怀疑时测试）。当你最终对 view 对象执行 apply 时，它将应用所有必要的操作以获取你所请求的特定元素。每次你为该元素 apply 时它都会这样做，所以性能可能更好或更差。

在这里，我将从一个 Range 视图开始，以避免数组分配，然后在最后将视图转换为一个 Array。不过，keys 会创建一个集合，施加一些开销。之后我将解释如何避免这种情况。

def deMap(m: Map[Int, AnyRef]): Array[AnyRef] = {
  def translate(x: AnyRef): AnyRef = x match {
    case map: Map[_, _] => 
      val validMap = map collect { case (key: Int, value: AnyRef) => (key -> value) }
      if (map.size > validMap.size) {
        val wrongPairs = map.toSeq diff validMap.toSeq
        throw new IllegalArgumentException("Invalid key/value pairs found: "+wrongPairs)
      }
      deMap(validMap)
    case s: String => s
    case other => throw new IllegalArgumentException("Expected Map or String, got "+other.getClass.toString)
  }
  (0 to m.keys.max view) map (m getOrElse (_, "")) map translate toArray
}

你应该将view保留在必要的优化中，而不是主动使用它。它并不一定比普通集合更快，而且它的非严格性可能会很棘手。使用Stream作为另一种替代方法。 Stream很像List，只是它仅在需要时计算其元素。这意味着在必要时才应用map操作。要使用它，请将倒数第二行替换为以下内容：

  Stream.range(0, m.keys.max + 1) map (m getOrElse (_, "")) map translate toArray

Stream 相较于 view 的主要优势在于，一旦计算了 Stream 中的一个值，它就会保持计算状态。具有讽刺意味的是，这也是它相较于 view 的主要劣势。在这种情况下，我认为 view 更快。

最后，关于如何在不先计算 keys 的情况下执行 max。一个 Map 也是一个 Iterable，所有的 Iterable 都有一个 max 方法，因此你可以直接使用 m.max。然而，这将计算 Tuple2[Int, AnyRef] 的最大值，而该类型并没有 Ordering。然而，max 接收一个隐式参数，告诉它要使用哪个 Ordering，因此可以提供该参数：

m.max(Ordering by ((_: (Int, AnyRef))._1))

这有点啰嗦，所以我们可以定义需要的隐式内容并使用它，呃，隐式地。:-)

def deMap(m: Map[Int, AnyRef]): Array[AnyRef] = {
  implicit val myOrdering = Ordering by ((_: (Int, AnyRef))._1)
  def translate(x: AnyRef): AnyRef = x match {
    case map: Map[_, _] => 
      val validMap = map collect { case (key: Int, value: AnyRef) => (key -> value) }
      if (map.size > validMap.size) {
        val wrongPairs = map.toSeq diff validMap.toSeq
        throw new IllegalArgumentException("Invalid key/value pairs found: "+wrongPairs)
      }
      deMap(validMap)
    case s: String => s
    case other => throw new IllegalArgumentException("Expected Map or String, got "+other.getClass.toString)
  }
  (0 to m.max._1 view) map (m getOrElse (_, "")) map translate toArray
}

注意，max返回一个元组，包含key和value，因此我们需要使用_1来获取key。此外，请注意在每个deMap嵌套中创建了一个Ordering对象。这样做还不错，但是通过在其他地方定义它可以使其更好。

完成所有这些之后，while循环仍然会更快，尽管我不知道具体加速多少。足够的JVM优化可能会让它们非常接近。另一方面，如果你真的想要速度，可以将代码写成汇编语言。这取决于编写代码的易用性和快速性，维护它的易用性以及运行速度之间的平衡。