并行作业任务中的优先队列

Question

我尝试了 PS 提到的问题 here。

任务。

您有一个并行化的程序并使用 n 个独立线程来处理给定的 m 列表职位。线程按照它们在输入中给出的顺序接受作业。如果有空闲线程，它立即从列表中获取下一个作业。

如果一个线程已经开始处理一个作业，它不会中断或停止直到它处理完作业。

如果多个线程同时尝试从列表中获取作业，则索引较小的线程接管了这项工作。对于每项工作，您确切知道任何线程需要多长时间处理这个作业，这个时间对所有线程都是一样的。

您需要为每个作业确定哪个线程会处理它，什么时候开始处理。

输入格式。

输入的第一行包含整数 n 和 m。第二行包含 m 个整数 t_i — 任何线程处理第 i 个作业所花费的时间（以秒为单位）。时间的顺序与它们在线程从中获取作业的列表中的顺序相同。线程从 0 开始索引。

约束。

1≤n≤10^5； 1 ≤ m ≤ 10^5 ； 0 ≤ t i ≤ 10^9 .

输出格式。

正好输出m行。第 i 行（使用基于 0 的索引）应包含两个 space- 分隔的整数 — 将处理第 i 个作业的线程的从 0 开始的索引和时间几秒钟后开始处理该作业。

我的实现对于基本测试用例运行良好。但是，这在某些测试中会失败。我这里没看到是什么错误

Sample Input

2 5

1 2 3 4 5

Output

0 0

1 0

0 1

1 2

0 4

这是我的代码。

#include <iostream>
#include <queue>

using std::cin;
using std::cout;
using std::endl;
using std::ios_base;
using std::pair;
using std::priority_queue;
using std::queue;
using std::vector;

#define For(i,a,n) for (int i = a; i < n; i++)
typedef pair<int,int> PII;

int main() {

    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int n,m,t,val;
    PII p;
    priority_queue<PII> pq;
    queue<int> q;

    // inputs >> number of treads, jobs
    cin >> n >> m;
    // time to process each job
    For(i,0,m){
        cin >> t;
        q.push(t);
    }
    // priority_queue
    // contains pair {-time, -tread} 
    For(i,0,n) pq.push({0, -i});

    // untill finish all jobs
    while(!q.empty()){
        // get the smallest time tread
        p = pq.top();
        pq.pop();
        // print the output << tread no , start time
        cout << -p.second << " " << -p.first << endl;
        // get the next value in the queue
        val = q.front();
        q.pop();
        // push the given tread with new end time
        pq.push({ -val + p.first, p.second });
        
    }

    return 0;
}

下面的 python3 代码可以很好地解决这个问题。但是，我在这两者中都找不到任何功能差异。 c++实现有什么问题。

import sys
import heapq

def read(): 
    return [int(i) for i in sys.stdin.readline().strip().split()]

n, m = read()
arr = read()

q = []

for i in range(n):
    heapq.heappush(q, (0, i))

for i in range(m):
    x, y = heapq.heappop(q)
    print(y, x)
    heapq.heappush(q, (x+arr[i], y))

感谢您的每一个回答。

Answer 1

If several threads try to take jobs from the list simultaneously, the thread with smaller index takes the job.

如果两个（或更多）线程同时完成它们的工作，则不能保证您首先弹出的线程在其中具有最小索引。修复很简单：pop all 那个时候终止的线程，并按索引对它们进行排序。

Answer 2

我得到了答案。那是因为 C++ 中的整数范围。将 'int' 更改为 'long long' 解决了这个问题。谢谢。

并行作业任务中的优先队列

Priority Queue in Parallel Jobs task

performance

priority-queue

python-3.x

c++17