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 中的随机记录

如果您不希望任务被选中两次，您可以将任务标记为活动而不选择它。

于 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 回答