檢查超時的算法

我有一套有限的任務需要由客戶完成。客戶在連接時被分配任務，並在完成前一個任務後繼續獲取新任務。每個任務需要由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

檢查超時的算法

回答

相關問題