使用标准库在 Scala 中计算两个稀疏向量的点积(并生成它们)
Calculating the Dot Product of two Sparse Vectors (and generating them) in Scala using the standard library
我正在尝试计算 Scala 中两个稀疏向量的点积(标量积)。我编写的代码正在执行我想要的所有操作,除了将两个向量的相似元素相乘时,它不考虑 0 值。
我希望得到 72 作为我的答案,因为 3 和 18 是唯一两个非零的键,它们的计算结果为:(3 -> 21) + (18 -> 51) = 72
我使用了 withDefaultValue(0) 希望它会 "fill in" 未提及的 key/value 对,但我认为情况并非如此,我相信这就是我的问题所在,在一开始。我想我的问题也可以是 "How to generate a Sparse Vector in Scala using the Standard Library".
如果我输入相应的 0,并且两个地图(矢量)具有相同数量的 key/value 对,我的代码可以正常工作。
```
val Sparse1 = Map(0 -> 4, 3 -> 7, 6 -> 11, 18 -> 17).withDefaultValue(0)
val Sparse2 = Map(1 -> 3, 3 -> 3, 11 -> 2,18 -> 3, 20 -> 6).withDefaultValue(0)
//println(Sparse2.toSeq)//to see what it is....0's missing
val SparseSum = (Sparse1.toSeq ++ Sparse2.toSeq).groupBy(_._1).mapValues(_.map(_._2).sum)
//println(SparseSum)
val productOfValues = ((Sparse1.toSeq ++ Sparse2.toSeq).groupBy(_._1).mapValues(_.map(_._2).reduce(_*_)))
//println(productOfValues)
var dotProduct = 0
for ((h,i) <- productOfValues) {
dotProduct += i
}
//println(dotProduct)
//If I specify some zero values, lets see what happens:
val Sparse3 = Map(0 -> 4, 1 -> 0, 3 -> 7, 6 -> 11, 11 -> 0, 18 -> 17, 20 -> 0).withDefaultValue(0)
val Sparse4 = Map(0 -> 0, 1 -> 3, 3 -> 3, 6 -> 0, 11 -> 2,18 -> 3, 20 -> 6).withDefaultValue(0)
val productOfValues2 = ((Sparse3.toSeq ++ Sparse4.toSeq).groupBy(_._1).mapValues(_.map(_._2).reduce(_*_)))
var dotProduct2 = 0
for ((l, m) <- productOfValues2) {
dotProduct2 += m
}
println(productOfValues2)
println(dotProduct2)//I get 72
```
我可以这样创建一个稀疏向量,然后更新值
import scala.collection.mutable.Map
val Sparse1 = Map[Int, Int]()
for (k <- 0 to 20) {
Sparse1 getOrElseUpdate (k, 0)
}
val Sparse2 = Map[Int, Int]()
for (k <- 0 to 20) {
Sparse2 getOrElseUpdate (k, 0)
}
但我想知道是否有 "better" 方法。更多的是我使用 "withDefaultValue(0)"
尝试过但失败的事情
由于您使用的是稀疏向量,因此您可以忽略不在两个向量上的所有键。
因此,我将计算两个键集之间的 intersection
,然后执行简单的 map-reduce 来计算点积。
type SparseVector[T] = Map[Int, T]
/** Generic function for any type T that can be multiplied & summed. */
def sparseDotProduct[T: Numeric](v1: SparseVector[T], v2: SparseVector[T]): T = {
import Numeric.Implicits._
val commonIndexes = v1.keySet & v2.keySet
commonIndexes
.map(i => v1(i) * v2(i))
.foldLeft(implicitly[Numeric[T]].zero)(_ + _)
}
那么,你可以这样使用它:
// The withDefault(0) is optional now.
val sparse1 = Map(0 -> 4, 3 -> 7, 6 -> 11, 18 -> 17).withDefaultValue(0)
val sparse2 = Map(1 -> 3, 3 -> 3, 11 -> 2, 18 -> 3, 20 -> 6).withDefaultValue(0)
sparseDotProduct(sparse1, sparse2)
// res: Int = 72
编辑 - 相同的方法,但没有上下文界限和隐式语法。
type SparseVector[T] = Map[Int, T]
/** Generic function for any type T that can be multiplied & summed. */
def sparseDotProduct[T](v1: SparseVector[T], v2: SparseVector[T])(implicit N: Numeric[T]): T = {
val commonIndexes = v1.keySet & v2.keySet
commonIndexes
.map(i => N.times(v1(i), v2(i)))
.foldLeft(N.zero)((acc, element) => N.plus(acc, element))
}
奖金 - non-spare 向量的一般方法。
可以修改上述方法以适用于任何类型的向量,而不仅仅是备用向量。
在这种情况下,我们需要密钥的 union
,并考虑一个密钥在另一个密钥上不存在的情况。
type MyVector[T] = Map[Int, T]
/** Generic function for any type T that can be multiplied & summed. */
def dotProduct[T: Numeric](v1: MyVector[T], v2: MyVector[T]): T = {
import Numeric.Implicits._
val zero = implicitly[Numeric[T]].zero
val allIndexes = v1.keySet | v2.keySet
allIndexes.map { i =>
v1.getOrElse(
key = i,
default = zero
) * v2.getOrElse(
key = i,
default = zero
)
}.foldLeft(zero)(_ + _)
}
我正在尝试计算 Scala 中两个稀疏向量的点积(标量积)。我编写的代码正在执行我想要的所有操作,除了将两个向量的相似元素相乘时,它不考虑 0 值。
我希望得到 72 作为我的答案,因为 3 和 18 是唯一两个非零的键,它们的计算结果为:(3 -> 21) + (18 -> 51) = 72
我使用了 withDefaultValue(0) 希望它会 "fill in" 未提及的 key/value 对,但我认为情况并非如此,我相信这就是我的问题所在,在一开始。我想我的问题也可以是 "How to generate a Sparse Vector in Scala using the Standard Library".
如果我输入相应的 0,并且两个地图(矢量)具有相同数量的 key/value 对,我的代码可以正常工作。
```
val Sparse1 = Map(0 -> 4, 3 -> 7, 6 -> 11, 18 -> 17).withDefaultValue(0)
val Sparse2 = Map(1 -> 3, 3 -> 3, 11 -> 2,18 -> 3, 20 -> 6).withDefaultValue(0)
//println(Sparse2.toSeq)//to see what it is....0's missing
val SparseSum = (Sparse1.toSeq ++ Sparse2.toSeq).groupBy(_._1).mapValues(_.map(_._2).sum)
//println(SparseSum)
val productOfValues = ((Sparse1.toSeq ++ Sparse2.toSeq).groupBy(_._1).mapValues(_.map(_._2).reduce(_*_)))
//println(productOfValues)
var dotProduct = 0
for ((h,i) <- productOfValues) {
dotProduct += i
}
//println(dotProduct)
//If I specify some zero values, lets see what happens:
val Sparse3 = Map(0 -> 4, 1 -> 0, 3 -> 7, 6 -> 11, 11 -> 0, 18 -> 17, 20 -> 0).withDefaultValue(0)
val Sparse4 = Map(0 -> 0, 1 -> 3, 3 -> 3, 6 -> 0, 11 -> 2,18 -> 3, 20 -> 6).withDefaultValue(0)
val productOfValues2 = ((Sparse3.toSeq ++ Sparse4.toSeq).groupBy(_._1).mapValues(_.map(_._2).reduce(_*_)))
var dotProduct2 = 0
for ((l, m) <- productOfValues2) {
dotProduct2 += m
}
println(productOfValues2)
println(dotProduct2)//I get 72
```
我可以这样创建一个稀疏向量,然后更新值
import scala.collection.mutable.Map
val Sparse1 = Map[Int, Int]()
for (k <- 0 to 20) {
Sparse1 getOrElseUpdate (k, 0)
}
val Sparse2 = Map[Int, Int]()
for (k <- 0 to 20) {
Sparse2 getOrElseUpdate (k, 0)
}
但我想知道是否有 "better" 方法。更多的是我使用 "withDefaultValue(0)"
尝试过但失败的事情由于您使用的是稀疏向量,因此您可以忽略不在两个向量上的所有键。
因此,我将计算两个键集之间的 intersection
,然后执行简单的 map-reduce 来计算点积。
type SparseVector[T] = Map[Int, T]
/** Generic function for any type T that can be multiplied & summed. */
def sparseDotProduct[T: Numeric](v1: SparseVector[T], v2: SparseVector[T]): T = {
import Numeric.Implicits._
val commonIndexes = v1.keySet & v2.keySet
commonIndexes
.map(i => v1(i) * v2(i))
.foldLeft(implicitly[Numeric[T]].zero)(_ + _)
}
那么,你可以这样使用它:
// The withDefault(0) is optional now.
val sparse1 = Map(0 -> 4, 3 -> 7, 6 -> 11, 18 -> 17).withDefaultValue(0)
val sparse2 = Map(1 -> 3, 3 -> 3, 11 -> 2, 18 -> 3, 20 -> 6).withDefaultValue(0)
sparseDotProduct(sparse1, sparse2)
// res: Int = 72
编辑 - 相同的方法,但没有上下文界限和隐式语法。
type SparseVector[T] = Map[Int, T]
/** Generic function for any type T that can be multiplied & summed. */
def sparseDotProduct[T](v1: SparseVector[T], v2: SparseVector[T])(implicit N: Numeric[T]): T = {
val commonIndexes = v1.keySet & v2.keySet
commonIndexes
.map(i => N.times(v1(i), v2(i)))
.foldLeft(N.zero)((acc, element) => N.plus(acc, element))
}
奖金 - non-spare 向量的一般方法。
可以修改上述方法以适用于任何类型的向量,而不仅仅是备用向量。
在这种情况下,我们需要密钥的 union
,并考虑一个密钥在另一个密钥上不存在的情况。
type MyVector[T] = Map[Int, T]
/** Generic function for any type T that can be multiplied & summed. */
def dotProduct[T: Numeric](v1: MyVector[T], v2: MyVector[T]): T = {
import Numeric.Implicits._
val zero = implicitly[Numeric[T]].zero
val allIndexes = v1.keySet | v2.keySet
allIndexes.map { i =>
v1.getOrElse(
key = i,
default = zero
) * v2.getOrElse(
key = i,
default = zero
)
}.foldLeft(zero)(_ + _)
}