私はここで作業しようとしていたプロジェクトに関連してここに少し載せました。私は設計上の問題にぶつかり、ゼロから設計しなければなりません。だから、私がやろうとしていることを投稿できるかどうかと、誰かが私が望む結果を得る方法を理解するのを助けることができるのだろうかと思っています。ダイナミックプログラミングを使用したリストのパーティション
背景:
私はプログラミングに新しいし、学ぶことをしようとしています。だから私は基本的にリストを取ってリストから数字だけを使って各数字を分解することに関心のあるプロジェクトに取り掛かった。私はこれを(私がやった)簡単に無理やりにすることができると知っていますが、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や他のツールを使って拡大縮小することができるような方法で、大きな数字(リストには1000個の数字がついています)を使用することはできません。ここでは可能な結果のいくつかのより多くの例を示します。
[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ヶ月以上にわたって作業していて、デザインの問題にぶつかり、最初から始めなければならないと感じています。これを正しく構築するにはどうしたらいいですか?私はグーグルで見つけて、ナップザックの問題とパーティションの問題の解決策を見つけましたが、彼らは学校の仕事のためであり、大規模なデータセットではスケールアップできていないようです。
誰かが私に洞察力を与えることができたらうれしいですが、これを読んでくれてどうもありがとうございます。
この質問に答える時間をとってくれてありがとう、フランク。私はダイナミックプログラミングが基本的に事前計算テーブルの生成に役立ったと思っていましたが、私はそれについて考えて、ダイナミック関数をリスト全体に与える必要はないかもしれないという考えを持っていました。やや独立しています。たとえば、4は[2,2]に、2は[1,1]に分けることができますが、独立しているように見えるので、同じCPUでこれを行う必要はありません。また、CPU時間を節約するために、私はリスト全体を計算しませんでしたが、私は次の変数だけを考えました。 – Lostsoul
私はあなたの解決策を完全に理解していません。私は他の人たち(DPと言いました)が私にシンプルなテーブルを見せているのを見ましたが、[1,4]はどういう意味ですか? 1は4?もしそうなら、それは[1,2,4]のリストを使って5の数をどのように解決するでしょう。正解は[4 + 1]でなければなりませんが、その結果を得るためにリストを生成する方法はわかりません。 – Lostsoul
このアプローチでは、[1,4]は、1 + 4が5を構成するように読み込まれるという点で、あなたの解の一部です。最初のステップは異なる可能な合計を作成するだけですが、この合計の値。 – Frank