рекурсивно преобразовать Map[Int, Map[Int, X]] в Array[Array[X]]

Это бессмысленно:

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

из-за стирания все, что вы можете проверить, это:

case t: Map[_, _]

что, по сути, является единственным способом избежать предупреждений о стирании. Кроме того, экзистенциальный тип почти всегда не нужен, и лично я всегда нахожу его синтаксис немного сложным для правильного понимания. Тем не менее, это единственный случай, когда использование _ для обозначения экзистенциального типа является адекватным. Обратите внимание, однако, что в моем собственном коде (первая версия) я не могу использовать его, потому что типы не будут совпадать, если я это сделаю.

Следующий,

произвольно глубокие многомерные массивы

Это не очень хорошая идея. Вы должны знать, какой тип вы вернете, чтобы объявить его — если глубина «произвольна», то и тип будет таким же. Вы можете обойтись без Array[AnyRef], но пользоваться им будет больно.

Тем не менее, вот один из способов. Я избавился от всех петель, заменив их картой. Обратите внимание, где я использую тот факт, что 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. Когда вы выполняете 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. Stream очень похож на List, за исключением того, что он вычисляет свои элементы только по запросу. Это означает, что ни одна из map операций не будет применяться до тех пор, пока в этом нет необходимости. Чтобы использовать его, просто замените предпоследнюю строку на эту:

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

Основное преимущество Stream перед view заключается в том, что после того, как значение в Stream было вычислено, оно остается вычисленным. Это также его главный недостаток по сравнению с view, как это ни парадоксально. В данном конкретном случае я думаю, что view быстрее.

Наконец, о выполнении max без предварительного вычисления Set (результата keys). 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, они могут подойти довольно близко. С другой стороны, если вам действительно нужна скорость, вы можете полностью перейти на ассемблерный код. Все сводится к балансу между тем, насколько легко и быстро писать код, насколько легко его поддерживать и насколько быстро он работает.