我们如何利用 mapreduce 或 spark 将二和算法作为大数据问题来解决?
How can we solve a two-sum algorithm as a big data problem leveraging mapreduce or spark?
假设 list/array 个数字存在于一个非常庞大的数据文件中,我们需要找到匹配特定数字 'k' 的一对总和。我知道通常如何使用数据结构来解决它,但我想不出一种方法来特别利用 Hadoop MR 或 spark 来解决它。
假设一个文件有 1,2,3,6,7,7,8,9
我的思考过程:
- 将数据考虑到一个数据框中,然后再向其中添加一列来标识差异 i.e.if i<=k/2 然后 k-i else i。然后现在我的上述数据的数据框是这样的:
number
number_2
1
9
2
8
3
7
7
7
7
7
8
8
9
9
创建 df 后,我计划根据 number_2 使用键聚合数据。但我无法假设聚合逻辑。
任何帮助将不胜感激。
假设您有一个名为 numbers.txt
的文件,如下所示:
10
5
8
7
3
6
9
11
3
1
你可以这样实现你的目标:
int desiredSum = 15;
SparkSession spark = SparkSession
.builder()
.appName("My App")
.master("local[*]")
.getOrCreate();
Dataset<Row> rdd = spark
.read()
.text("numbers")
.withColumnRenamed("value", "number")
.withColumn("number", col("number").cast(DataTypes.LongType));
rdd.createOrReplaceTempView("myTable");
spark.sql("select first.number, second.number as number_2 from myTable first inner join myTable second on first.number + second.number =" + desiredSum + " where first.number <= second.number").show();
+------+--------+
|number|number_2|
+------+--------+
| 5| 10|
| 7| 8|
| 6| 9|
+------+--------+
或者,如果数据很小,您可以像这样在 Spark 中使用笛卡尔积来实现您的目标:
int desiredSum = 15;
SparkSession spark = SparkSession
.builder()
.appName("My App")
.master("local[*]")
.getOrCreate();
Dataset<Row> rdd = spark
.read()
.text("numbers.txt")
.withColumnRenamed("value", "number")
.withColumn("number", col("number").cast(DataTypes.LongType));
Dataset<Row> joinedRdd = rdd.crossJoin(rdd.withColumnRenamed("number", "number_2")).filter("number <= number_2");
UserDefinedFunction mode = udf((UDF2<Long, Long, Object>) Long::sum, DataTypes.LongType);
joinedRdd = joinedRdd.withColumn("sum", mode.apply(col("number"), col( "number_2"))).filter("sum = " + desiredSum);
joinedRdd.show();
结果为:
+------+--------+---+
|number|number_2|sum|
+------+--------+---+
| 5| 10| 15|
| 7| 8| 15|
| 6| 9| 15|
+------+--------+---+
**take into account the Order of time and space complexity when you use Cross join**
假设 list/array 个数字存在于一个非常庞大的数据文件中,我们需要找到匹配特定数字 'k' 的一对总和。我知道通常如何使用数据结构来解决它,但我想不出一种方法来特别利用 Hadoop MR 或 spark 来解决它。
假设一个文件有 1,2,3,6,7,7,8,9 我的思考过程: - 将数据考虑到一个数据框中,然后再向其中添加一列来标识差异 i.e.if i<=k/2 然后 k-i else i。然后现在我的上述数据的数据框是这样的:
number | number_2 |
---|---|
1 | 9 |
2 | 8 |
3 | 7 |
7 | 7 |
7 | 7 |
8 | 8 |
9 | 9 |
创建 df 后,我计划根据 number_2 使用键聚合数据。但我无法假设聚合逻辑。 任何帮助将不胜感激。
假设您有一个名为 numbers.txt
的文件,如下所示:
10
5
8
7
3
6
9
11
3
1
你可以这样实现你的目标:
int desiredSum = 15;
SparkSession spark = SparkSession
.builder()
.appName("My App")
.master("local[*]")
.getOrCreate();
Dataset<Row> rdd = spark
.read()
.text("numbers")
.withColumnRenamed("value", "number")
.withColumn("number", col("number").cast(DataTypes.LongType));
rdd.createOrReplaceTempView("myTable");
spark.sql("select first.number, second.number as number_2 from myTable first inner join myTable second on first.number + second.number =" + desiredSum + " where first.number <= second.number").show();
+------+--------+
|number|number_2|
+------+--------+
| 5| 10|
| 7| 8|
| 6| 9|
+------+--------+
或者,如果数据很小,您可以像这样在 Spark 中使用笛卡尔积来实现您的目标:
int desiredSum = 15;
SparkSession spark = SparkSession
.builder()
.appName("My App")
.master("local[*]")
.getOrCreate();
Dataset<Row> rdd = spark
.read()
.text("numbers.txt")
.withColumnRenamed("value", "number")
.withColumn("number", col("number").cast(DataTypes.LongType));
Dataset<Row> joinedRdd = rdd.crossJoin(rdd.withColumnRenamed("number", "number_2")).filter("number <= number_2");
UserDefinedFunction mode = udf((UDF2<Long, Long, Object>) Long::sum, DataTypes.LongType);
joinedRdd = joinedRdd.withColumn("sum", mode.apply(col("number"), col( "number_2"))).filter("sum = " + desiredSum);
joinedRdd.show();
结果为:
+------+--------+---+
|number|number_2|sum|
+------+--------+---+
| 5| 10| 15|
| 7| 8| 15|
| 6| 9| 15|
+------+--------+---+
**take into account the Order of time and space complexity when you use Cross join**