我对使用 Scala 很感兴趣,因为它似乎是并行化操作的好方法。我需要设计一种利用向量乘法的机器学习算法(很多都是如此)。我知道如何做算法,但我想做的是来自 HashMaps 的稀疏向量实现。几乎所有向量都存储为 HashMaps[Int, Double],其中向量中给定 double 的索引是作为键的整数。
使用 Pythonish 伪代码,
==> {1:7, 2:6, 3:5, 4:4}
我想使用 fold、reduce、map ... 等定义点积函数,但我不想使用 foldLeft、reduceLeft ... 因为我希望它具有潜在的并行性,因为我的向量可以起来到 6000 多个维度,对于点积,顺序无关紧要。
我已经阅读了许多 foldLeft 和 reduceLeft 的例子,但我还没有找到如何使用 HashMap.fold 或 HashMap.reduce。
我对函数式编程有相当程度的了解,但我不了解 Scala 中的错误消息。这是我或多或少想要的模板。
object NGramAnalysis {
def main(args: Array[String]) {
val mapped = HashMap(1->1.2, 5->2.4)
println(mapped.fold( .... What goes here ... )
}
}
结论
我想要一个使用 HashMap.fold NOT foldLeft 和 HashMap.reduce 相同的实例
先感谢您。我已经挣扎了一段时间。
最佳答案
首先,fold
和 reduce
的区别在于 fold
需要一个额外的参数作为初始值,而 reduce
将集合中的第一个元素作为初始值,如果集合为空则抛出异常。因此, fold
比 reduce
更通用,所以从现在开始我将这两个函数都称为 fold
。
为了使 fold
正常工作,您集合中的元素必须形成半群,也就是说,应该有一个二元运算,它也必须是关联的,也就是说,应该保持以下身份: (a `op` b) `op` c == a `op` (b `op` c)
。需要关联性是因为 fold
没有指定操作应用顺序,这在并行上下文中尤为重要。此操作用于执行折叠:
a1 `op` a2 `op` a3 `op` ... `op` an
如果
reduce
并行运行,它可以拆分集合并在一个线程中减少前半部分,在另一个线程中减少后半部分;然后使用相同的操作将它们的结果连接起来。只有当操作是关联的时,这才能正常工作。正如我已经说过的,
fold
方法有两个参数:初始值和一个 [关联] 二元运算符。例如,要并行连接字符串列表,您可以这样做:val strings = Seq("a", "b", "c", "d", ...)
strings.par.fold("")(_ ++ _) // or strings.par.reduce(_ ++ _) if you know that strings is non-empty
因此,要实现点积,您需要考虑要折叠/归约的集合以及执行此归约的二元运算符。
这是两个集合的点积的简单实现:
(c1 zip c2).par.map {
case (e1, e2) => e1 * e2
}.reduce(_ + _)
也就是说,我们将这些集合压缩在一起,使用
*
运算符将它们的元素成对相乘,然后使用 +
运算符减少结果。当然,必须在 *
和 +
的元素上定义 c1
和 c2
。然而,
HashMap
是无序的,所以它的迭代顺序是不确定的。不能保证 zip
会连接具有相同键的元素,这使得上述点积的想法不正确。你需要做这样的事情:c1.par.map {
case (k, v) => v * c2(k)
}.reduce(_ + _)
在这里,我们没有压缩集合,而是使用第一个映射中的所有键在第二个映射中执行查找。
关于Scala - HashMap 上的折叠操作示例 ** 不是 foldLeft,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/25321691/