3

整数キーのマップ間で対応する配列に変換する関数を作成しようとしています。基本ケースは完了しましたが、再帰ケースを書き込もうとしています（つまり、多次元配列：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'が見つかりました。

これは教育的な目的であるため、フィードバックをいただければ幸いです。具体的には、私のひどくJavaに見えるコードのコード批評、同じことを行う既存のscala関数、またはこれらの配列を構築するための代替方法の提案をいただければ幸いです。

4

1 に答える 1

11

これは無意味です：

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

消去のため、確認できるのはこれだけです。

case t: Map[_, _]

実際、これが消去に関する警告を受け取らない唯一の方法です。また、実存型はほとんどの場合不要であり、個人的には、その構文を正しく理解するのは常に少し難しいと思います。それでも、これは_実存型を示すために使用することが適切である1つのケースです。ただし、私自身のコード（最初のバージョン）では、タイプが一致しないため、使用できないことに注意してください。

次、

任意に深い多次元配列

それは特に良い考えではありません。宣言するために返すタイプを知っている必要があります。深さが「任意」の場合、タイプも同様です。で逃げることはできますがArray[AnyRef]、使うのは大変です。

それでも、ここに1つの方法があります。私はすべてのループを廃止し、それらをマップに置き換えました。を呼び出すことにより、 aMapも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
}

2つの問題があります。まず、キーが連続していない場合（Map(0 -> "a", 2 -> "b")たとえば）、要素の位置がずれます。これを回避する方法は、コードの最後から2番目の行を次のように置き換えることです。

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

ここでは、空の文字列を使用して、配列の穴を表しています。

もう1つの問題は、すべてのマップがタイプであると想定していることです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。これは、1回ではなく3回繰り返す必要があると考える人もいますが、毎回異なるタスクを実行するため、実際にはそれほど多くの作業を行っていません。ただし、毎回新しい配列を割り当てるという事実は、割り当てのペナルティ（Javaがすべての配列を事前に初期化する）とキャッシュの局所性の懸念の両方のために、パフォーマンスに確実に影響を与えます。

これを回避する1つの方法は、を使用することviewです。を実行するとmap、flatMap新しいビューが返され、その操作は将来の使用のために保存されます（他の方法もそのように機能する可能性があります。ドキュメントを確認するか、疑わしい場合はテストしてください）。最終的にオブジェクトに対してを実行すると、要求した特定の要素を取得するために必要なすべての操作が適用されます。その要素についても毎回そうするので、パフォーマンスは良くも悪くもなります。filterviewapplyviewapply

ここでは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よく似ています。Listつまり、map必要になるまで操作は適用されません。これを使用するには、最後から2番目の行を次のように置き換えます。

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

Streamaに対するoverの主な利点は、viewaの値Streamが計算されると、計算されたままになることです。viewそれはまた、皮肉なことに、それに対する主な欠点でもあります。この特定のケースでは、私viewはより速いと思います。

最後に、最初に（の結果）maxを計算せずにを実行することについて。Aもであり、すべてにメソッドがあるので、簡単に行うことができます。ただし、これは、の最大値を計算します。これには、が存在しないタイプです。ただし、何を使用するかを指示する暗黙のパラメーターを受け取ります。これにより、次のように提供できます。SetkeysMapIterableIterablemaxm.maxTuple2[Int, AnyRef]OrderingmaxOrdering

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返すことに注意してください。したがって、を取得する必要があります。また、のネストごとにオブジェクトを作成することに注意してください。悪くはありませんが、他の場所で定義することで改善できます。keyvalue_1keyOrderingdeMap

それをすべて行った後でも、whileループはさらに高速になりますが、どれだけかはわかりません。十分なJVM最適化があれば、それらはかなり近くなる可能性があります。一方、本当に速度が必要な場合は、アセンブラコードまでたどり着くことができます。それは、コードを書くのがどれほど簡単で速いか、それを維持するのがどれほど簡単か、そしてそれがどれだけ速く実行されるかの間のバランスに帰着します。

于 2010-12-05T02:41:09.560 に答える