Scala:将 map 列表与每个键的最大值合并的惯用方法？

Question

我有一个 Map[Int, Int] 列表，它们都有相同的键(从 1 到 20)，我想将它们的内容合并到一个 Map[Int, Int] 中。

我已阅读 another post关于合并使用 |+| 的 map 的堆栈溢出来自 Scalaz 图书馆。

我想出了以下解决方案，但对我来说似乎很笨拙。

val defaultMap = (2 to ceiling).map((_,0)).toMap
val factors: Map[Int, Int] = (2 to ceiling). map(primeFactors(_)).
        foldRight(defaultMap)(mergeMaps(_, _))

def mergeMaps(xm: Map[Int, Int], ym: Map[Int, Int]): Map[Int,Int] = {
    def iter(acc: Map[Int,Int], other: Map[Int,Int], i: Int): Map[Int,Int] = {
      if (other.isEmpty) acc
      else iter(acc - i + (i -> math.max(acc(i), other(i))), other - i, i + 1)
    }
    iter(xm, ym, 2)
  }

def primeFactors(number: Int): Map[Int, Int] = {
  def iter(factors: Map[Int,Int], rem: Int, i: Int): Map[Int,Int] = {
    if (i > number) factors
    else if (rem % i == 0) iter(factors - i + (i -> (factors(i)+1)), rem / i, i)
    else iter(factors, rem, i + 1)
  }
  iter((2 to ceiling).map((_,0)).toMap, number, 2)
}

说明:val factors创建一个映射列表，每个映射代表 2-20 中数字的质因数；然后将这 18 个映射折叠成一个映射，其中包含每个键的最大值。

更新

使用@folone 的建议，我最终得到了以下代码(对我的原始版本有了明显的改进，而且我不必将 Maps 更改为 HashMaps):

import scalaz._
import Scalaz._
import Tags._

/**
 * Smallest Multiple
 *
 * 2520 is the smallest number that can be divided by each of the numbers 
 * from 1 to 10 without any remainder. What is the smallest positive number 
 * that is evenly divisible by all of the numbers from 1 to 20?
 *
 * User: Alexandros Bantis
 * Date: 1/29/13
 * Time: 8:07 PM
 */
object Problem005 {

  def findSmallestMultiple(ceiling: Int): Int = {
    val factors = (2 to ceiling).map(primeFactors(_).mapValues(MaxVal)).reduce(_ |+| _)
    (1 /: factors.map(m => intPow(m._1, m._2)))(_ * _)
  }

  private def primeFactors(number: Int): Map[Int, Int] = {
    def iter(factors: Map[Int,Int], rem: Int, i: Int): Map[Int,Int] = {
      if (i > number) factors.filter(_._2 > 0).mapValues(MaxVal)
      else if (rem % i == 0) iter(factors - i + (i -> (factors(i)+1)), rem / i, i)
      else iter(factors, rem, i + 1)
    }
    iter((2 to number).map((_,0)).toMap, number, 2)
  }

  private def intPow(x: Int, y: Int): Int = {
    def iter(acc: Int, rem: Int): Int = {
      if (rem == 0) acc
      else iter(acc * x, rem -1)
    }
    if (y == 0) 1 else iter(1, y)
  }
}

Answer 1

此解决方案不适用于一般 Map s，但如果您使用的是 immutable.HashMap你可以考虑 merged method :

def merged[B1 >: B](that: HashMap[A, B1])(mergef: ((A, B1), (A, B1)) ⇒ (A, B1)): HashMap[A, B1]

Creates a new map which is the merge of this and the argument hash map.

Uses the specified collision resolution function if two keys are the same. The collision resolution function will always take the first argument from this hash map and the second from that.

The merged method is on average more performant than doing a traversal and reconstructing a new immutable hash map from scratch, or ++.

用例:

val m1 = immutable.HashMap[Int, Int](1 -> 2, 2 -> 3)
val m2 = immutable.HashMap[Int, Int](1 -> 3, 4 -> 5)
m1.merged(m2) {
  case ((k1, v1), (k2, v2)) => ((k1, math.max(v1, v2)))
}