Spark: производить RDD [(X, X)] всех возможных комбинаций из RDD [X]
Возможно ли в Spark реализовать функцию '.combinations' из коллекций scala?
/** Iterates over combinations.
*
* @return An Iterator which traverses the possible n-element combinations of this $coll.
* @example `"abbbc".combinations(2) = Iterator(ab, ac, bb, bc)`
*/
Например, как я могу получить из RDD [X] в RDD [List [X]] или RDD [(X, X)] для комбинаций размера = 2. И позволяет предположить, что все значения в RDD уникальны.
Ответы
Ответ 1
Декартово произведение и комбинации - две разные вещи: декартово произведение создаст RDD размера rdd.size() ^ 2, а комбинации создадут RDD размера rdd.size() choose 2
val rdd = sc.parallelize(1 to 5)
val combinations = rdd.cartesian(rdd).filter{ case (a,b) => a < b }`.
combinations.collect()
Обратите внимание, что это будет работать, только если для элементов списка указано упорядочение, так как мы используем <. Это работает только для выбора двух, но их можно легко расширить, убедившись, что отношение a < b для всех a и b в последовательности
Ответ 2
Как обсуждалось, cartesian даст вам n ^ 2 элемента декартова произведения RDD с самим собой.
Этот алгоритм вычисляет комбинации (n, 2) RDD без необходимости сначала вычислять n ^ 2 элементов: (используемый тип String как тип, обобщающий на тип T, берет некоторую сантехнику с классовыми предметами, которые скрывали бы здесь цель)
Это, вероятно, меньше времени, чем декартовая + фильтрация из-за итеративных действий count и take, которые заставляют вычислять RDD, но более эффективное пространство, поскольку оно вычисляет только элементы C(n,2) = n!/(2*(n-2))! = (n*(n-1)/2) вместо n^2 декартового произведения.
import org.apache.spark.rdd._
def combs(rdd:RDD[String]):RDD[(String,String)] = {
val count = rdd.count
if (rdd.count < 2) {
sc.makeRDD[(String,String)](Seq.empty)
} else if (rdd.count == 2) {
val values = rdd.collect
sc.makeRDD[(String,String)](Seq((values(0), values(1))))
} else {
val elem = rdd.take(1)
val elemRdd = sc.makeRDD(elem)
val subtracted = rdd.subtract(elemRdd)
val comb = subtracted.map(e => (elem(0),e))
comb.union(combs(subtracted))
}
}
Ответ 3
Это поддерживается с помощью Spark RDD с преобразованием cartesian.
например:.
val rdd = sc.parallelize(1 to 5)
val cartesian = rdd.cartesian(rdd)
cartesian.collect
Array[(Int, Int)] = Array((1,1), (1,2), (1,3), (1,4), (1,5),
(2,1), (2,2), (2,3), (2,4), (2,5),
(3,1), (3,2), (3,3), (3,4), (3,5),
(4,1), (4,2), (4,3), (4,4), (4,5),
(5,1), (5,2), (5,3), (5,4), (5,5))
Ответ 4
Это создает все комбинации (n, 2) и работает для любого RDD без необходимости упорядочивания элементов RDD.
val rddWithIndex = rdd.zipWithIndex
rddWithIndex.cartesian(rddWithIndex).filter{case(a, b) => a._2 < b._2}.map{case(a, b) => (a._1, b._1)}
a._2 и b._2 - индексы, а a__1 и b._1 - элементы исходного RDD.
Пример:
Обратите внимание, что на картах не определено упорядочение.
val m1 = Map('a' -> 1, 'b' -> 2)
val m2 = Map('c' -> 3, 'a' -> 4)
val m3 = Map('e' -> 5, 'c' -> 6, 'b' -> 7)
val rdd = sc.makeRDD(Array(m1, m2, m3))
val rddWithIndex = rdd.zipWithIndex
rddWithIndex.cartesian(rddWithIndex).filter{case(a, b) => a._2 < b._2}.map{case(a, b) => (a._1, b._1)}.collect
Вывод:
Array((Map(a -> 1, b -> 2),Map(c -> 3, a -> 4)), (Map(a -> 1, b -> 2),Map(e -> 5, c -> 6, b -> 7)), (Map(c -> 3, a -> 4),Map(e -> 5, c -> 6, b -> 7)))
