Google App Engineで実行するメモリと計算集約型のプログラムの設計方法

Question

Googleのアプリケーションエンジンで動作するコードに問題があります。 GAEに合わせてコードを修正する方法はわかりません。以下は、私の問題

for j in range(n): 
for d in range(j): 
    for d1 in range(d): 
    for d2 in range(d1): 
    # block which runs in O(n^2) 

を効率的に全体のコードブロックは、O（N^6）であり、それはNに依存以上10分間実行されています。したがって私はタスクキューを使用しています。また、nxnxnxnのリスト（例えば、A [j] [d] [d1] [d2]）として格納されている4次元配列が必要になるでしょう。

制限put（）は10 MBですが、配列全体を格納することはできません。だから私は小さな塊にチョッピングし、それを保存し、それらを組み合わせて取得するときに試みました。私はこれにjson関数を使用しましたが、大きなn（> 40）のサポートはありません。

次に、データストア、すなわち各A [j] [d] [d1]エンティティのリストの個々のエンティティとして行列全体を格納しました。したがって、ローカル変数はありません。私のコードでA [j] [d] [d1] [d2]にアクセスすると、自分自身の関数getitemとputitemを呼び出してデータストアからデータを取得し、キャッシングを使用します。その結果、私のコードは計算に時間がかかります。いくつかの反復の後、私はGAEによって生成されたエラー203を取得し、タスクはコード500で失敗します。

私のコードはGAEには最適ではないかもしれません。しかし、それをGAEに実装する最良の方法は何ですか？

Answer 1

さらに効率的にデータを格納し、それを反復する方法があります。

質問：あなたは、list of list ... of intを何のデータ型を

• を格納していますか？
• 最も内側のループO（n^2）部分は通常どのような範囲でネストされますか？
• putitemを実行すると、1つのputまたはgetでいくつの値を取得していますか？

アイデア：

• あなたは（カット・アンド・ペースト用とBASE64）あなたのJSONを圧縮してみてください。 'myjson'.encode('zlib').encode('base64')
• @Robertのように分割と征服（map reduce）を使用することをお勧めします。あなたは、キーのためのタプルを持つ辞書を使用することができるかもしれませんが、これはあなたの内側のループのA[j][d][d1][d2]ルックアップが少ないかもしれません。それはまたあなたの構造をまばらに埋め込むことができます。別の方法で読み込んだデータの範囲を追跡して知る必要があります。 A[j][d][d1][d2] becomes D[(j,d,d1,d2)] or D[j,d,d1,d2]

Answer 2

あなたの質問から予想されるサイズnのような重要な詳細は省略しました。また、 "# block which runs in O(n^2)"はマトリックス全体にアクセスする必要がありますか、単にインデックス値に基づいて行列を設定していますか？

これは一般的な答えです。これを小さなチャンクに分割する方法を見つける必要があります。たぶん、いくつかのタイプのdivide and conquer戦略を使用して、並列処理にタスクを使用することができます。あなたの行列をどのように保存するかは、問題をどのように分割するかによって異なります。インデックス値をキー名として使用してサブ行列、またはサブベクトルを格納することができます。これは、あなたの問題と使用する戦略によって異なります。

何らかの理由でアルゴリズムを並列化する方法がわからない場合は、何らかのタイプの継続戦略を使用することです。他の研究では、時間制限（安全マージンを残す）の中で典型的に何回行うことができるかを把握し、その限界に達するとデータを保存し、処理を続ける新しいタスクを挿入します。出発地点を通過してそこから走行を再開するだけです。最も外側の範囲に開始パラメータを与えることでこれを簡単に行うことができるかもしれませんが、もう一度問題の詳細に依存します。

Answer 3

サム、ちょうどあなたにアイデアとポインタをどこから始めるかを教えてください。

行列全体を格納してから数値を1つずつ格納するのに必要なものがあれば、pickleを使用してリストをシリアライズし、データストアに保存して後で取得することができます。 listはpythonオブジェクトであり、それをシリアル化できるはずです。トピックオフ

http://appengine-cookbook.appspot.com/recipe/how-to-put-any-python-object-in-a-datastore