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

Question

我正在尝试编写一个函数,使用整数键将Maps转换为相应的数组.我已完成基本情况,但我正在尝试编写递归情况(即多维数组:将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但是不包含密钥i,其中0 <= i <k,代码将失败.这对我来说没问题.

现在我希望对任意深度的多维数组做同样的事情.例如,在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'找到了.

由于这是一项教育追求,所以非常感谢任何反馈.具体来说,我将非常感谢任何代码批评我的看起来很糟糕的代码,现有的scala函数做同样的事情,或建议构建这些数组的替代方法.

Answer 1

这没有意义:

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

因为擦除,你可以检查的是:

case t: Map[_, _]

事实上,这是你不会收到关于擦除的警告的唯一方法.此外,存在类型几乎总是不必要的,而且,就个人而言,我总是发现它的语法有点棘手.尽管如此,这是_用于表示存在类型是足够的一种情况.但请注意,在我自己的代码(第一个版本)中,我无法使用它,因为如果我这样做,类型将不匹配.

下一个,

任意深度的多维数组

这不是一个特别好的主意.你必须知道你将返回什么类型来声明它 - 如果深度是"任意的",那么类型也是如此.你可以逃脱Array[AnyRef],但使用起来会很痛苦.

不过,这是一种方式.我取消了所有循环,用地图替换它们.注意我通过调用来利用a Map也是a 的事实.另请注意,我只是使用数组(使用)创建,以避免必须管理地图创建.Function1map mmaptoArray

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预初始化所有数组)以及缓存局部性问题.

避免这种情况的一种方法是使用a view.当你这样做map,flatMap并filter在view,你会得到一个新的视图回来,与操作储存以备将来使用(其他方法可能工作方式太-查看文档,或测试有疑问时).当您最终apply对该view对象执行操作时,它将应用获取您要求的特定元素所需的所有操作.每次你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但是,您应该留下必要的优化,而不是主动使用它们.它不一定比普通集合更快,并且它的非严格性可能很棘手.使用的另一种替代方法view是使用Stream替代方法.A Stream很像a List,除了它只根据需要计算它的元素.这意味着map在必要时不会应用任何操作.要使用它,只需将最后一行替换为:

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

Stream超过a 的主要优点view是,一旦Stream计算出a中的值,它就会保持计算.这也是它的主要劣势view,具有讽刺意味的是.在这种特殊情况下,我认为view更快.

最后,关于先做一个max没有计算Set(结果keys)的.A 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.另外,请注意我们Ordering在每个嵌套时创建一个对象deMap.不错,但通过在别处定义它可以做得更好.

一旦你完成了所有这些,一个while循环仍然会更快,虽然我不知道多少.如果有足够的JVM优化,它们可能会非常接近.另一方面,如果你真的想要速度,你可以一直去装配代码.它归结为编写代码的简单和快速,维护代码的容易程度以及运行速度之间的平衡.