使用Map Reduce确定输入数据中的模式

Question

我有一组按一定顺序排列的数字。秩序很重要，需要维护。我需要找到符合条件的连续数字的最大数目。

示例

:

条件:素数

输入数据:1、3、2、4、7、5、3、11、2,4,6, 3、7、3、5、1、3、7、5 ,

4

Answer : 8

Answer 1

这个解决方案要求您知道输入的每个元素的位置i。这并不一定容易，但现在假设它。

首先，想象将每个值映射到列表中的索引i，然后只保留原始值n满足条件的值。然后只需在输入中找到最长的连续序列。

首先，对于输入中的每个值，在位置i，取i的前几位，可能是前8位，作为输出键。这将导致附近的值在256中转到相同的减速器。如果原始值满足条件，则输出this作为键，i作为值。

在每个reducer中，只需遍历索引并记录您看到的最长连续序列。发出它为(start,end)。

最后，您将从约简器中读取所有这些值，并处理来自两个不同约简器的两个序列实际上一起运行的情况(一个结束于n，下一个开始于n+1)。折叠它们，然后只报告最长的那个的长度。

Answer 2

因为顺序很重要，所以您应该集中精力寻找满足条件的长且连续的范围。

这样写怎么样:

你可以并行化你的输入数据，包括5个字段到序列中的每个元素:

• 第一个和第二个附加字段描述一个范围的开始和结束，以保持局域性，
• 将在reduce阶段填充的第三个额外字段，如果满足条件，该字段将保留
• 第4个额外的字段，如果邻居在左边已经减少
• 第5个保留右侧邻居的额外字段已经减少

:

地图

输入数据:

1,3,2,4,7,5,3,11,2,4,6,3,7,3,5,1,3,7,5,4

会变成这样:

输入数据:(1,1,1,,true,false),(3,2,2,,false,false),(2,3,3,,false,false),(4,4,4,,false,false),(7,5,5,,false,false),(5,6,6,,false,false),(3,7,7,,false,false),(11,8,8,,false,false),(2,9,9,,false,false),(4,10,10,,false,false),(6,11,11,,false,false),(3,12,12,,false,false),(7,13,13,,false,false),(3,14,14,,false,false),(5,15,15,,false,false),(1,16,16,,false,false),(3,17,17,,false,false),(7,18,18,,false,false),(5,19,19,,false,false),(4,20,20,,false,true)

因此，通过这种方式，您将能够并行地保持引用的顺序并具有明确的停止条件。

对于约简阶段，您必须验证两个条件，并且只约那些满足两个条件的元素元组，否则，不约简，但可能会更新第4，第5，第6个额外字段，然后继续迭代，直到满足停止条件。

1)要还原的元素是连续的(相邻)2)元素满足特定条件，对于您的情况:两个元素都是素数

如果做:你减少其他情况:继续进行reduce阶段，直到数据中没有连续的元组仍然被求值，换句话说，而任何一个元素在其第4或第5个字段中保持值为false。

reduce中的case:

a)你收到元素(3,12,12,,false,false)和(7,13,13,,false,false)被还原:

• 是连续的(邻居)?是的
• 是素数吗?是的

则返回:("3,17",12,13,true,false,false)

b)你收到元素(6,11,11,,false,false)和("3,17",12,13,true,false,false)被简化:

• 连续吗?是的
• 都是素数吗?没有

那么，您将返回:("3,17",12,13,true,true,false)和(6,11,11,false,false,true)

c)你收到元素(1,1,1,,true,false)和(3,2,2,,false,false)被简化:

• 连续吗?是的
• 都是素数吗?没有

则返回(1,1,1,false,true,*true*)和(3,2,2,false,*true*,false)

d)你收到元素(5,15,15,,false,false)和(3,17,17,,false,false)要减少:

• 连续吗?没有
• 都是素数吗?是的

则返回(5,15,15,*true*,false,false)和(3,17,17,*true*,false,false)

e)你收到元素(5,15,15,true,false,false)和(1,16,16,,false,false)要减少:

• 连续吗?是的
• 都是素数吗?是的

则返回("5,1",15,16,true,false,false)

输出

最后你会得到8个元素:

• ("1,2,3",1,3,true,true,true)

  • for: (1,1,1,,true,false),(3,2,2,,false,false),(2,3,3,,false,false)

• (4,4,4,false,true,true)

  • for: (4,4,4,,false,false)

• ("7,5,3,11",5,8,true,true,true)

  • for (7,5,5,,false,false),(5,6,6,,false,false),(3,7,7,,false,false),(11,8,8,,false,false)

• (2,9,9,true,true,true)

  • for: (2,9,9,,false,false)

• (4,10,10,false,true,true)

  • for: (4,10,10,,false,false)

• (6,11,11,false,true,true)

  • for: (6,11,11,,false,false)

• ("3,7,3,5,1,3,7,5",12,19,true,true,true)

  • for: (3,12,12,,false,false),(7,13,13,,false,false),(3,14,14,,false,false), (5,15,15,,false,false),(1,16,16,,false,false),(3,17,17,,false,false),(7,18,18,,false,false),(5,19,19,,false,false)

• (4,20,20,false,true,true)

  • for: (4,20,20,,false,true)