Parallel processing simulator

#1

Xin chào mọi người, em đang làm bài parallel processing simulator. Đây là đề bài:

image
image1366×768 145 KB

Em ví dụ:
Input:
2 5
1 2 3 4 5
Output:
0 0
1 0
0 1
1 2
0 4
Còn đây là cách em hiểu bài toán:
image
image1366×768 24.2 KB

Jobs sẽ lần lượt vào Counter 0,1; sau đó nó sẽ lưu vào timeline của mỗi cái counter. Code của em có dùng priority queue để lưu counter lại. (vì em lười tạo min priority queue nên dùng max priority queue). Jobs[i] lưu lại thời gian thực thi của i. Assigned_workers_[i] để lưu lại counter mà i đã đến. Start_times_[i] là thời điểm bắt đầu công việc của i. Next_free_time để lưu lại timeline làm việc của 2 counter. Code của em vẫn còn sai gì đó mà em không nghĩ ra, mọi người xem và gợi ý giúp em với. Em xin cảm ơn ạ :3

// Assignment2Problem2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include "pch.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
class JobQueue {
private:
	int num_workers_;
	vector<int> jobs_;
	vector<int> assigned_workers_;
	vector<long long> start_times_;

	void WriteResponse() const {
		for (int i = 0; i < jobs_.size(); ++i) {
			cout << assigned_workers_[i] << " " << start_times_[i] << "\n";
		}
	}
	void ReadData() {
		int m;
		cin >> num_workers_ >> m;
		jobs_.resize(m);
		for (int i = 0; i < m; ++i)
			cin >> jobs_[i];
	}

	void AssignJobs() {

		// TODO: replace this code with a faster algorithm.
		/*
		assigned_workers_.resize(jobs_.size());
		start_times_.resize(jobs_.size());
		vector<long long> next_free_time(num_workers_, 0);
		for (int i = 0; i < jobs_.size(); ++i) {
			int duration = jobs_[i];
			int next_worker = 0;
			for (int j = 0; j < num_workers_; ++j) {
				if (next_free_time[j] < next_free_time[next_worker])
					next_worker = j;
			}
			assigned_workers_[i] = next_worker;
			start_times_[i] = next_free_time[next_worker];
			next_free_time[next_worker] += duration;
		}
		*/
		priority_queue<int> counter;
		vector <long long> next_free_time(num_workers_);
		assigned_workers_.resize(jobs_.size());
		start_times_.resize(jobs_.size());
		int temp_customer = 0;
		while (temp_customer < jobs_.size())
		{
			for (int i = 0; i < num_workers_; i++)
			{
				counter.push(i);
			}

			while (counter.empty() == 0)
			{
				int free_counter = num_workers_ - counter.top() - 1;
				counter.pop();
				assigned_workers_[temp_customer] = free_counter;
				start_times_[temp_customer] = next_free_time[free_counter];
				next_free_time[free_counter] += jobs_[temp_customer];
				temp_customer++;
				if (temp_customer >= jobs_.size()) return;
			}
		}
	}

public:
	void Solve() {
		ReadData();
		AssignJobs();
		WriteResponse();
	}
};

int main() {

	ios_base::sync_with_stdio(false);
	JobQueue job_queue;
	job_queue.Solve();
	return 0;
	
}
1 Like
#2

Cái code trên sai ở chỗ nếu counter 1 làm 6 s, counter 2 làm 3 s, job tiếp theo 2 s thì nó sẽ đi vào counter 1 nên sai.
Em sửa sai bằng cách tạo cái minHeapBuilder và lưu luôn timeline của các counter vào, chưa biết nó chạy nhanh hay chậm, nhưng mà nó vẫn còn sai ạ :(((( huhu:

// Assignment2Problem2.cpp : This file contains the 'main' function. Program execution begins and ends there.
#include "pch.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
class minHeapBuilder {
private:
	vector<int> data_;

	int parent(int i)
	{
		return (i - 1) / 2;
	}
	int leftChild(int i)
	{
		return 2 * i + 1;
	}
	int rightChild(int i)
	{
		return 2 * i + 2;
	}
	void siftDown(int i)
	{
		int minIndex = i;
		int l = leftChild(i);
		if (l <= data_.size() - 1 && data_[l] < data_[minIndex])
			minIndex = l;
		int r = rightChild(i);
		if (r <= data_.size() - 1 && data_[r] < data_[minIndex])
			minIndex = r;
		if (i != minIndex)
		{
			swap(data_[i], data_[minIndex]);
			siftDown(minIndex);
		}
	}
	void siftUp(int i)
	{
		while (i > 0 && data_[parent(i)] > data_[i])
		{
			swap(data_[i], data_[parent(i)]);
			i = parent(i);
		}
	}
public:
	void push(int i)
	{
		data_.push_back(i);
		siftUp(data_.size() - 1);
	}
	int extractMin()
	{
		int result = data_[0];
		swap(data_[0], data_[data_.size() - 1]);
		data_.pop_back();
		siftDown(0);
		return result;
	}
	bool empty()
	{
		if (data_.size() == 0)
			return 1;
		return 0;
	}
};
class JobQueue {
private:
	int num_workers_;
	vector<int> jobs_;
	vector<int> assigned_workers_;
	vector<long long> start_times_;
	void WriteResponse() const {
		for (int i = 0; i < jobs_.size(); ++i) {
			cout << assigned_workers_[i] << " " << start_times_[i] << "\n";
		}
	}
	void ReadData() {
		int m;
		cin >> num_workers_ >> m;
		jobs_.resize(m);
		for (int i = 0; i < m; ++i)
			cin >> jobs_[i];
	}
	void AssignJobs() {
		// TODO: replace this code with a faster algorithm.
		
		minHeapBuilder counter;
		vector <long long> next_free_time(num_workers_);
		assigned_workers_.resize(jobs_.size());
		start_times_.resize(jobs_.size());
		for (int i = 0; i < num_workers_; i++)
		{
			counter.push(next_free_time[i]);
		}
		for (int i = 0; i < jobs_.size(); i++)
		{
			int freeCounter;
			int minTimeline = counter.extractMin();
			for (int j = 0; j < num_workers_; j++)
			{
				if (next_free_time[j] == minTimeline)
				{
					freeCounter = j;
					break;
				}
			}
			assigned_workers_[i] = freeCounter;
			start_times_[i] = next_free_time[freeCounter];
			next_free_time[freeCounter] += jobs_[i];
			counter.push(next_free_time[freeCounter]);
		}
	}
public:
	void Solve() {
		ReadData();
		AssignJobs();
		WriteResponse();
	}
};
int main() {
	ios_base::sync_with_stdio(false);
	JobQueue job_queue;
	job_queue.Solve();
	return 0;
}
1 Like
#3

Test case:
10 100
124860658 388437511 753484620 349021732 311346104 235543106 665655446 28787989 706718118 409836312 217716719 757274700 609723717 880970735 972393187 246159983 318988174 209495228 854708169 945600937 773832664 587887000 531713892 734781348 603087775 148283412 195634719 968633747 697254794 304163856 554172907 197744495 261204530 641309055 773073192 463418708 59676768 16042361 210106931 901997880 220470855 647104348 163515452 27308711 836338869 505101921 397086591 126041010 704685424 48832532 944295743 840261083 407178084 723373230 242749954 62738878 445028313 734727516 370425459 607137327 541789278 281002380 548695538 651178045 638430458 981678371 648753077 417312222 446493640 201544143 293197772 298610124 31821879 46071794 509690783 183827382 867731980 524516363 376504571 748818121 36366377 404131214 128632009 535716196 470711551 19833703 516847878 422344417 453049973 58419678 175133498 967886806 49897195 188342011 272087192 798530288 210486166 836411405 909200386 561566778

#4

em xài priority_queue :V Đẩy vào pq này cặp (thread_id, complete_timestamp) rồi so sánh by complete_timestamp then by thread_id là được :V

6 Likes
#5

Em chưa hiểu lắm, làm sao để truyền 2 tham số vào priority queue được.

#6

https://en.cppreference.com/w/cpp/container/priority_queue/priority_queue xem ví dụ bên dưới “Example With Custom Comparator”

6 Likes
#7

à em làm tiếp từ cái heap bài kia à =] làm xong priority_queue rồi tìm cách đổi thành cái heap kia lại coi bất tiện chỗ nào =]

4 Likes
#8

Hã, ý anh là cái minHeapBuilder đó hả, rồi đổi nó lại thành cái gì á :v

#9

đổi từ std::priority_queue<...> thành minHeapBuilder :V

5 Likes
#10

Em hiểu rồi nè. Nhưng mà đổi xong rồi makepair lại xong rồi so sánh với complete_timestamp hả anh, em chưa biết cái complete_timestamp.

#11

ban đầu em đẩy vào (0,0) và (1,0), pq.top() là (0,0).

  • pop ra (0,0) ra rồi push vào lại (0,0+1) vì task tiếp theo tốn thời gian là 1. Giá trị đầu tiên là thread_id, giá trị thứ hai là là thời điểm hoàn thành task hiện tại. Lúc này pq = (1,0), (0,1).
  • pop ra (1,0), push vào lại (1,0+2). pq = (0,1), (1,2).
  • pop ra (0,1), push vào lại (0,1+3). pq = (1,2), (0,4).
  • pop ra (1,2), push vào lại (1,2+4). pq = (0,4), (1,6).
  • pop ra (0,4), push vào lại (0,4+5). pq = (1,6), (0,9).
    tới đây là xong :V Mỗi lần pop em in ra cặp tương ứng thì output là
    0 0
    1 0
    0 1
    1 2
    0 4
    đúng như yêu cầu :V
7 Likes
#12

Haha, đỉnh của tỉnh, hồi chiều em còn suy nghĩ cách tạo cái heap bằng double linked list 2 data để lưu cái threadid với time. :)))) cảm ơn anh nhiều lém.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?