我有一个Map [Int,Int]列表,它们都有相同的键(从1到20),我想将它们的内容合并到一个Map [Int,Int]中。
我已经阅读了关于堆栈溢出的another post关于合并使用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的建议,我最终得到以下代码(对我的原始版本有一个明显的改进,我不必将地图更改为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)
}
}
正如您的标签所示,您可能对scalaz解决方案感兴趣。开始:
> console
[info] Starting scala interpreter...
[info]
Welcome to Scala version 2.10.0 (OpenJDK 64-Bit Server VM, Java 1.7.0_15).
Type in expressions to have them evaluated.
Type :help for more information.
scala> import scalaz._, Scalaz._, Tags._
import scalaz._
import Scalaz._
import Tags._
在最大操作下存在Int的Semigroup实例:
scala> Semigroup[Int @@ MaxVal]
res0: scalaz.Semigroup[scalaz.@@[Int,scalaz.Tags.MaxVal]] = scalaz.Semigroup$$anon$9@15a9a9c6
我们只是用它:
scala> val m1 = Map(1 -> 2, 2 -> 3) mapValues MaxVal
m1: scala.collection.immutable.Map[Int,scalaz.@@[Int,scalaz.Tags.MaxVal]] = Map(1 -> 2, 2 -> 3)
scala> val m2 = Map(1 -> 3, 4 -> 5) mapValues MaxVal
m2: scala.collection.immutable.Map[Int,scalaz.@@[Int,scalaz.Tags.MaxVal]] = Map(1 -> 3, 4 -> 5)
scala> m1 |+| m2
res1: scala.collection.immutable.Map[Int,scalaz.@@[Int,scalaz.Tags.MaxVal]] = Map(1 -> 3, 4 -> 5, 2 -> 3)
如果你对这个“标记”(@@
的东西)如何工作感兴趣,这里有一个很好的解释:http://etorreborre.blogspot.de/2011/11/practical-uses-for-unboxed-tagged-types.html
此解决方案不适用于一般Map
s,但如果您使用immutable.HashMap
s,您可以考虑merged
method:
def merged[B1 >: B](that: HashMap[A, B1])(mergef: ((A, B1), (A, B1)) ⇒ (A, B1)): HashMap[A, B1]
创建一个新映射,它是this和参数哈希映射的合并。
如果两个键相同,则使用指定的冲突解决功能。冲突解决函数将始终从此哈希映射中获取第一个参数,并从中获取第二个参数。
合并的方法平均比执行遍历和从头开始重构新的不可变哈希映射(或++)更高效。
使用案例:
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)))
}
启动Scala 2.13
,另一种仅基于标准库的解决方案包括在应用Map
之前将groupMapReduces合并为序列,其中(顾名思义)是groupBy
的等价物,后跟映射和值的减少步骤:
// val map1 = Map(1 -> 2, 2 -> 3)
// val map2 = Map(1 -> 3, 4 -> 5)
(map1.toSeq ++ map2).groupMapReduce(_._1)(_._2)(_ max _)
// Map[Int,Int] = Map(2 -> 3, 4 -> 5, 1 -> 3)
这个:
List((1,2), (2,3), (1,3), (4,5))
)。为了简明起见,map2
被隐式转换为Seq
以采用map1.toSeq
的类型 - 但你可以选择通过使用map2.toSeq
使其明确。group
s元素基于它们的第一个元组部分(groupMapReduce的组部分)map
s将值分组到它们的第二个元组部分(mapMapReduce的map部分)reduce
s通过取max(减少groupMapReduce的一部分)映射值(_ max _
)