Convertir récursivement la carte [Int, Map [Int, X]] en Array [Array [X]]

Question

J'essaye d'écrire une fonction qui convertit entre Maps avec des touches entières pour les tableaux correspondants. J'ai fait le cas de base, mais j'essaye d'écrire le cas récursif (c'est-à-dire des tableaux multidimensionnels: convertir la carte [Int, carte [Int, X]] en tableau [tableau [X]]). Cette tâche est née de la nécessité de construire un tableau à partir d'un flux sans connaître la taille du tableau à l'avance, permettant la possibilité que les éléments sortent du flux dans un ordre aléatoire et la possibilité d'éléments dupliqués à venir. hors du courant.

J'ai une fonction qui le fait:

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 
    } 
} 

Remarque, je suis conscient du fait que le code échoue si la carte contient la clé k mais ne contient pas la clé i où 0 < = i < k. C'est correct pour mes fins.

Maintenant, je cherche à faire la même chose pour les tableaux multi-dimensionnels arbitrairement profonds. Par exemple, convertir une carte entre [Int, Carte [Int, X]] en Array [Array [X]]. Malheureusement, je suis dérangé par les types. En utilisant ce qui précède comme un cas de base, voici ce que j'ai jusqu'à présent:

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) 
     } 
    } 
} 

C'est l'erreur que je reçois:

« => » attendu mais « forsome » trouvé.

Comme il s'agit d'une activité éducative, tout commentaire est grandement apprécié. Spécifiquement, j'apprécierais n'importe quelles critiques de code de mon code java-regardant terriblement, des fonctions existantes de scala qui font la même chose, ou des suggestions pour une manière alternative de construire ces tableaux.

Answer 1

Ce n'a pas de sens:

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

en raison de l'effacement, tout ce que vous pouvez vérifier est la suivante:

case t: Map[_, _] 

qui, en fait, est la seule façon que vous n'obtiendrez des avertissements sur effacement. En outre, un type existentiel est presque toujours inutile, et, personnellement, je trouve toujours sa syntaxe un peu difficile à obtenir. Encore, c'est le seul cas où l'utilisation _ pour signifier le type existentiel est adéquate. Notez, cependant, que dans mon propre code (la première version) je ne peux pas l'utiliser, parce que les types ne correspondront pas si je le fais.

Ensuite,

arbitrairement profondes multidimensionnels tableaux

Ce n'est pas une bonne idée particulière. Vous devez savoir quel type vous reviendrez pour le déclarer - si la profondeur est "arbitraire", alors le type l'est aussi. Vous pouvez vous en sortir avec un Array[AnyRef], mais il sera difficile à utiliser.

Encore, voici une façon. J'ai supprimé toutes les boucles, en les remplaçant par la carte. Notez où je profite du fait qu'un Map est également un Function1, en appelant map m.Notez également que j'utilise simplement map sur un tableau (créé avec toArray) pour éviter d'avoir à gérer la création de carte.

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 
} 

Il y a deux problèmes. Pour commencer, si les touches ne sont pas contiguës (Map(0 -> "a", 2 -> "b"), par exemple), les éléments seront hors position. Voici une façon de le contourner, en remplaçant le côté de la dernière ligne de code avec:

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

Ici, j'utilisé une chaîne vide pour se présenter à un trou dans les tableaux. L'autre problème est que toutes les cartes seront de type Map[Int, AnyRef]. Pour résoudre ce problème, l'aurait peut être réécrite comme ceci:

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 
} 

Ici, j'ignorer toutes les paires dont les clés ne sont pas Int et les valeurs ne sont pas AnyRef. On pourrait encore sûr vérifier le code pour tester si quelque chose manque et de faire rapport et l'erreur dans ce cas:

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 
} 

Enfin, sur la performance. L'utilisation de map comme je l'ai fait signifie qu'un nouveau tableau sera alloué pour chaque map. Certaines personnes prennent cela pour dire que je dois répéter trois fois au lieu d'une, mais puisque chaque fois que je fais une tâche différente, cela ne fait pas vraiment beaucoup plus de travail. Cependant, le fait que j'attribue un nouveau tableau à chaque fois a certainement un impact sur les performances - à la fois en raison de la pénalité d'allocation (Java pré-initialise tous les tableaux), et à cause des problèmes de localisation du cache.

Une façon d'éviter cela est l'utilisation d'un view. Lorsque vous faites map, flatMap et filter sur un view, vous obtenez une nouvelle vue en arrière, avec cette opération stocké pour une utilisation future (d'autres méthodes pourraient fonctionner de cette façon aussi - vérifier la documentation, ou tester en cas de doute). Lorsque vous effectuez enfin un apply sur l'objet view, il applique toutes les opérations nécessaires pour obtenir l'élément spécifique que vous avez demandé. Il le fera à chaque fois que vous aurez aussi cet élément, donc la performance peut être à la fois meilleure ou pire.

Ici, je vais commencer avec une vue Range, pour éviter l'allocation de tableau, puis convertir la vue en Array à la fin. Encore, keys va créer un ensemble, imposant une surcharge. Après cela, je vais vous expliquer comment éviter cela.

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 
} 

Vous devez laisser view à des optimisations nécessaires, mais, au lieu de pro-activement leur utilisation. Ce n'est pas nécessairement plus rapide que les collections normales, et sa non-rigueur peut être difficile. Une autre alternative à l'utilisation view utilise à la place un Stream. Un Stream ressemble beaucoup à un List, sauf qu'il ne calcule que ses éléments à la demande. Cela signifie qu'aucune des opérations map ne sera appliquée jusqu'à ce que nécessaire. Pour l'utiliser, il suffit de remplacer la dernière ligne suivante à ceci:

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

L'avantage principal d'un Stream sur une view est qu'une fois une valeur dans un Stream a été calculé, il reste calculé. C'est aussi son principal inconvénient sur un view, assez ironiquement. Dans ce cas particulier, je pense que view est plus rapide.

Enfin, à propos de faire un max sans calculer un Set (le résultat de keys) en premier. Un Map est également un Iterable, et tous les Iterable ont une méthode max, donc vous pouvez simplement faire m.max. Cela, cependant, va calculer le maximum de Tuple2[Int, AnyRef], un type pour lequel il n'y a pas Ordering. Cependant, max reçoit un paramètre implicite lui indiquant ce Ordering à utiliser, qui peut être ainsi fourni:

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

C'est un peu d'une bouchée, afin que nous puissions définir l'implicite dont nous avons besoin et de l'utiliser, err, implicitement . :-)

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 
} 

Notez que max retourne un tuple, key et value, donc nous avons besoin pour obtenir le _1key. Notez également que nous créons un objet Ordering à chaque imbrication de deMap. Pas mal, mais il pourrait être amélioré en le définissant ailleurs.

Une fois que vous avez fait tout cela, une boucle while sera encore plus rapide, mais je n'ai aucune idée de combien. Si les optimisations JVM sont suffisantes, elles pourraient être assez proches. D'autre part, si vous voulez vraiment la vitesse, vous pouvez aller jusqu'au code assembleur. Il s'agit d'un équilibre entre la facilité et la rapidité d'écriture du code, sa facilité de maintenance et sa rapidité d'exécution.