Улучшения для функции слияния карт

Question

Я пишу функцию для объединения двух карт.Это то, что я до сих пор:

def merge[K, V1, V2, V3](left: Map[K, V1], right: Map[K, V2])
    (fn: (Option[V1], Option[V2]) => V3): Map[K, V3] = {
  val r = (left.keySet ++ right.keySet) map {
    key =>
      (key -> fn(left.get(key), right.get(key)))
  }
  r.toMap
}

Сама функция работает.Вы используете функцию следующим образом:

val m1 = Map(1 -> "one", 3 -> "three", 5 -> "five")
val m2 = Map(1 -> "I", 5 -> "V", 10 -> "X")
merge(m1, m2) { (_, _) } 
// returns: 
// Map(1 -> (Some(one),Some(I)), 
//     3 -> (Some(three),None), 
//     5 -> (Some(five),Some(V)), 
//     10 -> (None,Some(X)))

У меня есть два вопроса:

1. Я беспокоюсь о производительности вычислительной сложности .getи .toMap звонки.Кто-нибудь может улучшить реализацию?
2. Я бы хотел, чтобы функция по умолчанию составляла пару значений ({ (_, _) }).Я не могу понять синтаксис, чтобы сделать это правильно.

Редактировать: Хотя я изначально говорил о производительности, я имел в виду вычислительную сложность. Я предполагаю, что эта функция выполняется за O (n • ln (n)). Похоже, моя функция работает примерно за O (n).Можно ли это сделать в O (ln (n))?

Answer 1

Для литерала функции по умолчанию:

(fn: (Option[V1], Option[V2]) => V3 = 
  (x: Option[V1], y: Option[V2]) => Tuple2(x,y))

Вам нужно использовать слияние следующим образом: merge(m1,m2)()

Я бы сказал, не беспокойтесь о производительности, пока вы не выполните некоторые измерения на реальных данных.

Редактировать: о производительности, предоставляя представление вместо построения карты, вы можете быстро получить «конструкцию» за счет поиска - при условии, что мы имеем дело с неизменяемыми картами. Таким образом, в зависимости от фактических данных и варианта использования, вы можете получить лучшую производительность для определенных операций, но у этого есть компромисс.

class MergedView[K, V1, V2, V3](
    left: Map[K, V1], right: Map[K, V2]
  )(fn: (Option[V1], Option[V2]) => V3 = (x: Option[V1], y: Option[V2]) => Tuple2(x,y)
  ) extends collection.DefaultMap[K, V3] {
  def get(key: K): Option[V3] = (left.get(key), right.get(key)) match {
    case (None, None) => None
    case t => Some(fn(t._1, t._2))
  }
  lazy val tuples = (left.keys ++ right.keys).map(key => key -> get(key).get)
  def iterator: Iterator[(K, V3)] = tuples.iterator
} 

val r1 = new MergedView(m1, m2)() // use parens here for second param list.

Answer 2

Вам не стоит беспокоиться о get - да, это создаст объект-обертку, но делать что-либо еще будет достаточно неловко, и вам не следует пытаться, если профилировщик не покажет, что это проблема.

Что касается toMap, да, это вполне может замедлить вас.Вы можете попробовать использовать breakOut .

Что касается сложности get и toMap, поиск и добавление - это действительное постоянное время для неизменяемого HashMap, которое по умолчанию Map.См. Характеристики производительности коллекций Scala .