Это бессмысленно:
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, они могут быть довольно близки. С другой стороны, если вам действительно нужна скорость, вы можете пройти весь путь до ассемблерного кода. Это сводится к балансу между тем, насколько легко и быстро написать код, насколько легко его поддерживать и как быстро он выполняется.