ダイナミックプログラミングを使用したリストのパーティション

Question

私はここで作業しようとしていたプロジェクトに関連してここに少し載せました。私は設計上の問題にぶつかり、ゼロから設計しなければなりません。だから、私がやろうとしていることを投稿できるかどうかと、誰かが私が望む結果を得る方法を理解するのを助けることができるのだろうかと思っています。

背景：

私はプログラミングに新しいし、学ぶことをしようとしています。だから私は基本的にリストを取ってリストから数字だけを使って各数字を分解することに関心のあるプロジェクトに取り掛かった。私はこれを（私がやった）簡単に無理やりにすることができると知っていますが、Hbase、Hadoop、および並列処理も学びたいので、さまざまなマシン間でプロセスを壊すことができるようにしていきたいと思います。私はこれを行う方法は、動的なプログラミングと再帰を使用して、さらに細分化できる可能性のテーブルを作成することだと思いました。

例：私はリスト提出する場合

：[1,2, 4]を私は{1: [[1]], 2: [[1, 1]], 4: [[2, 2]]}を取得する必要があります。基本的には2 + 2 = 4,1 + 1 = 2、1 = 1.soなので、4を作るためのすべての方法を見てみると、このリスト（データベース内にある）と2 + 2 = 4を参照してから、2..などを分解してください。私は検索作業をしていますが、問題が発生しています。ブルートフォースを使用しても、私がhadoopや他のツールを使って拡大縮小することができるような方法で、大きな数字（リストには10​​00個の数字がついています）を使用することはできません。ここでは可能な結果のいくつかのより多くの例を示します。

[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に時間がかかることはありませんということですそれをすばやく行い、ハーフカットクラスターにスケールアップすることもできます。

これを動作させるために作成したコードは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の関連資料も役立ちます。