5

タスク キューに基づいてアプリケーションを構築しています。これは、一連のタスクを、非同期的に接続された複数のクライアントに提供します。ひねりを加えたのは、タスクをランダムな順序で処理する必要があることです。

私の問題は、現在使用しているアルゴリズムが計算コストが高いことです。これは、多くの大きなクエリとデータベースからの転送に依存しているためです。同じ結果を達成するためのより安価な方法があるという強い予感がありますが、解決策がよくわかりません。この問題の巧妙な解決法を思いつくことができますか?

私が現在使用している（計算コストの高い）アルゴリズムは次のとおりです。

クライアントが新しいタスクを照会すると...

  1. 「未完了」のタスクについてデータベースにクエリを実行する
  2. すべてのタスクをリストに入れる
  3. リストをシャッフルします (random.shuffle を使用)
  4. 最初のタスクに「進行中」のフラグを立てる
  5. 完了のためにタスク パラメータをクライアントに送信する

クライアントがタスクを完了すると...

6a. 結果を記録し、タスクに「終了」のフラグを立てます。

クライアントが期限までにタスクを完了できなかった場合...

6b. タスクに「未完了」のフラグを付け直します。

ステップ 1、2、および 3 を疑似乱数シーケンスまたはハッシュ関数に置き換えることで、より良い結果が得られるようです。しかし、私は完全な解決策を理解することはできません。アイデア？

その他の考慮事項:

  • 重要な場合のために、私はこれらすべてに python と mongodb を使用しています。(Mongodb には、「find_one を使用してランダムに一致するエントリを効率的に返す」という巧妙な使い方がありませんよね?)
  • 「キュー」という用語は少し誤解を招きます。すべてのタスクは、mongodb 内の単一のコレクションのサブフィールドに格納されます。コレクション内の長さ (タスクの総数) は既知であり、最初に固定されています。
  • 必要に応じて、まれに同じタスクを複数回割り当てても問題ない場合があります。ただし、各タスクを完了するにはコストがかかるため、この種のインスタンスは非常にまれである必要があります。
  • 私は各クライアントの識別情報を持っているので、各タスク リクエストの発信者を正確に把握できます。
4

2 に答える 2

1

MongoDB からランダムなドキュメントを取得する簡単な方法があります。

MongoDB からのランダム レコードを参照してください

タスクを 2 回選択したくない場合は、タスクをアクティブとしてマークし、選択しないようにすることができます。

于 2012-07-26T14:34:02.703 に答える
0

ああ、私が見逃したコメントに基づいて、あなたはこれらの線に沿って何かをすることができます：

import random
available = range(lengthofdatabase)
inprogress = []
while len(available) > 0:
    taskindex = available.pop(random.randrange(0, len(available)))
    # I'm not sure of your implementation, but you said something 
    # along these lines was possible
    task = GetTask(taskindex)
    inprogress.append(taskindex)

使用している関数がわからない-これは単なるアルゴリズムです。

ハッピーコーディング！

于 2012-07-26T14:47:36.507 に答える