检查超时的算法

我有一套有限的任务需要由客户完成。客户在连接时被分配任务，并在完成前一个任务后继续获取新任务。每个任务需要由3个独特的客户完成。这可以确保客户端不会给任务提供错误的结果。检查超时的算法

但是，我不希望客户花费超过3000毫秒。由于某些任务是相互依赖的，这可能会阻碍进展。

问题是我在检查任务超时时遇到问题 - 当没有可用的任务时应该完成这些任务。

这时每个任务有一个名为assignedClients属性，它看起来如下：

assignedClients: [ 
    { 
    client: Client, 
    start: Date, 
    completed: true 
    }, 
    { 
    client: Client, 
    start: Date, 
    completed: true 
    }, 
    { 
    client: Client, 
    start: Date, 
    completed: false 
    } 
]

所有任务（约1000）都存储在一个单一的阵列。基本上，当一个客户端需要一个新的任务时，伪代码是这样的：

function onTaskRequest: 
    for (task in tasks): 
    if (assignedClients < 3) 
     assignClientToTask(task, client) 
     return 

    // so no available tasks 
    for (task in tasks): 
     for (client in assignedClients): 
     if (client.completed === false && Time.now() - client.start > 3000): 
      removeOldClientFromAssignedClients() 
      assignClientToTask(task, client)

但是，这似乎效率很低。有没有更有效的算法？

来源

2017-10-16 Thomas W

你想要做的是将任务存储在优先级队列中（通常以堆的形式实现），方法是在最早的队列中存在任务。当客户需要一项新任务时，您只需查看队列的顶部。如果它可以安排在任何时间，它可以安排在该任务上。

当插入任务时，现在给出它的优先级。当您填写任务列表时，您需要在最早的客户端到期时才将它抓住。

如果您使用的是堆，那么所有的操作应该不会比O(log(n))差，与您目前的O(n)实施相比。

您的数据结构看起来像JSON，在这种情况下，https://github.com/adamhooper/js-priority-queue是我在Google查看时首先启动的优先级队列的JavaScript实现。您的伪代码看起来像Python，在这种情况下，https://docs.python.org/3/library/heapq.html位于标准库中。如果您找不到您的语言的实施，https://en.wikipedia.org/wiki/Heap_(data_structure)应该能够帮助您了解如何实施它。

来源

2017-10-17 00:45:12 btilly

检查超时的算法

回答

相关问题