使用动态编程对列表进行分区

Question

我在这里发布了一些与我一直在尝试工作的项目相关的内容，并且我一直在打击设计问题，并且必须从头开始设计。所以我想知道我是否可以发布我想要做的事情，并且有人可以帮助我理解我如何获得我想要的结果。

背景：

我新的编程和努力学习。因此，我参与了一个对我感兴趣的项目，其中涉及基本上使用列表并仅使用列表中的数字来分解每个数字。我知道我可以很容易地蛮力（这是我做的），但我也想学习Hbase，Hadoop和并行处理，所以我希望能够通过各种机器打破这个过程。我认为这样做的方式是使用动态编程和递归来创建可能进一步细分的可能性表。

例子：

如果我提交名单：[1,2, 4]我应该得到{1: [[1]], 2: [[1, 1]], 4: [[2, 2]]}。它的基本意思是2 + 2 = 4，1 + 1 = 2，1 = 1 ..因此，我试图查看所有的方法来创建4，我可以查找这个列表（它将在数据库中）和看2 + 2 = 4，然后分解2 ..等等..我有查找工作工作，但我有问题的故障。使用蛮力不会让我使用大数字（比如说百万，列表中有一千个数字），这样我就可以使用hadoop或其他工具来扩展它。以下是可能的结果更多的例子：

[1,2, 3, 4] = {1: [[1]], 2: [[1, 1]], 3: [[1, 2]], 4: [[1, 3], [2, 2]]} 
[1,2, 3, 4, 6, 10] = {1: [[1]], 2: [[1, 1]], 3: [[1, 2]], 4: [[1, 3], [2, 2]], 6: [[2, 4], [3, 3]], 10: [[4, 6], [2, 2, 2, 2, 2]]} 
[10, 30, 50] = 50: [[10, 10, 30]], 30: [[10, 10, 10]]} 

这种方法的逻辑是，它不会花时间在列表中COMPUT下一个可能的数据，所以如果我发送列表一百万的数字它可以快速做到甚至扩展到hadoop集群。

我创建的代码是here，但问题在于如何纠正设计问题。我得到了这样的建议：这是一个分区问题，并且环视四周，发现了我想要做的更简单的版本（activestate），但它并不完全是我想要做的，因为它分解了一个数字，并没有使用特定的数据集来做到这一点。

问：

所以希望我清楚地描述了我想要做的事。我需要阅读/学习/学习如何使用动态编程在python中创建列表的分区表，以便扩展？它只是一种业余爱好，而不是时间敏感，但我觉得我已经在这方面工作了3个多月，每次遇到设计问题时都必须从头开始。我如何正确构建这个（看我的不正确的方式看到我的链接上面）？我已经搜索并找到了背包问题和分区问题的解决方案，但它们似乎更适合于学校工作，并且不是真正用大数据集来扩展。

希望有人能给我洞察力，但不管感谢您阅读本文。

Answer 1

您必须知道，DP问题本身并不是最佳的独立和分布式计算。

当你考虑DP算法的经典形式时，你有一个矩阵/表/数组，并且你以一定顺序连续计算新值。每个值的计算都需要先前创建的其他值。因此，您将失去数据独立性，并且可以同时最大限度地计算一定数量的数组字段，具体取决于特定的DP算法。例如，许多DP算法可以并行处理整个表格列，因为每个字段都依赖于前一列的字段。但这已经是由于该列之后的所有剩余字段的数据依赖性所引起的限制。

这就是说，计算列表中可用的各种数字的总和可能性不是DP问题。您根本没有解决任何子问题，只是简单地收集所有可能的金额（如果它们碰巧与您的某个列表条目匹配）。

因此，我建议以下悦目不同的方法：

• 计算所有可能的总和一个新的列表。这是数据独立的并且可以并行化，但是您需要一些上限来终止。例如：[1,2,4]变成[ [1],[2],[4],[1,1],[1,2],[1,4],...]。您不必明确地构造这个列表，而只需将每个这样的组合传递给下一步。
• 评估每个计算，即创建总和并检查它是否与原始列表中的值匹配。同样，您独立于数据，可以独立执行所有这些计算。
• 将正面结果结合到最终的数据结构中。

所以总结起来，并回答您的问题：

• 反思，你是否希望把这个问题作为DP的。
• 您可能想要了解数据并行性。这在解决GPU的这些问题时特别重要，所以关于CUDA/OpenCL的相关文献也可能有用。