From cf6f4a6dcb62c21b5f498396d01e5323d42852a7 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Sun, 24 Feb 2019 15:33:28 -0600 Subject: Parallel processing job queue done! I used C++'s priority_queue (queue.h) and C++'s own pair data structure. Unlike Python and Java's similar data structure, C++'s priority_queue pops in reverse order, so I had to negate the value, and negate back when adding them to vectors. Cool use of pair. Fun stuff :)--- Sources/DataStructure.cpp | 165 +++++++++++++++++++++++----------------------- 1 file changed, 82 insertions(+), 83 deletions(-) (limited to 'Sources') diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp index f3d46be..6085971 100644 --- a/Sources/DataStructure.cpp +++ b/Sources/DataStructure.cpp @@ -1,118 +1,117 @@ #include #include #include +#include //#include using std::vector; using std::cin; using std::cout; -using std::swap; using std::pair; using std::make_pair; -class HeapBuilder { +class JobQueue { private: - vector data_; -// vector > swaps_; -// void GenerateSwaps() { -// swaps_.clear(); -// // The following naive implementation just sorts -// // the given sequence using selection sort algorithm -// // and saves the resulting sequence of swaps. -// // This turns the given array into a heap, -// // but in the worst case gives a quadratic number of swaps. -// // -// for (size_t i = 0; i < data_.size(); ++i) -// for (size_t j = i + 1; j < data_.size(); ++j) { -// if (data_[i] > data_[j]) { -// swap(data_[i], data_[j]); -// swaps_.push_back(make_pair(i, j)); -// } -// } -// } + vector assigned_workers_; + vector start_times_; -public: - vector> swaps; void WriteResponse() const { - cout << swaps.size() << "\n"; - for (size_t i = 0; i < swaps.size(); ++i) { - cout << swaps[i].first << " " << swaps[i].second << "\n"; + for (size_t i = 0; i < jobs.size(); ++i) { + cout << assigned_workers_[i] << " " << start_times_[i] << "\n"; } } void ReadData() { - int n; - cin >> n; - data_.resize(n); - for (int i = 0; i < n; ++i) - cin >> data_[i]; + int m; + cin >> num_workers >> m; + jobs.resize(m); + for (int i = 0; i < m; ++i) + cin >> jobs[i]; } - // Please note the for loop below. Initially I copied the for loop from my - // Java code, but it doesn't work in C++. Changing it to while loop worked! - // It was better with the while loop anyway, much clearer to me. - void UpdateSwaps(vector &data) { - int j = (data.size() - 1) / 2; - while (j >= 0) { - siftDown(j, data); - j = j - 1; - } -// for (size_t i = j; i >= 0; i--) { -// siftDown(i, data); -// } - } - void siftDown(int i, vector &data) { - int maxIndex = i; - size_t l = 2 * i + 1; - if (l < data.size() && data[l] < data[maxIndex]) - maxIndex = l; - size_t r = 2 * i + 2; - if (r < data.size() && data[r] < data[maxIndex]) - maxIndex = r; - if (i != maxIndex) { - swap(data[i], data[maxIndex]); - swaps.push_back(make_pair(i, maxIndex)); - siftDown(maxIndex, data); + void AssignJobs() { + // Naive algorithm + assigned_workers_.resize(jobs.size()); + start_times_.resize(jobs.size()); + vector next_free_time(num_workers, 0); + for (size_t 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; } } + +public: + int num_workers; + vector jobs; void Solve() { ReadData(); -// GenerateSwaps(); - UpdateSwaps(data_); + AssignJobsImproved(); WriteResponse(); } + const vector& assigned_workers() const { + return assigned_workers_; + } + const vector& start_times() const { + return start_times_; + } + + void AssignJobsImproved() { + std::priority_queue> pq; + assigned_workers_.resize(jobs.size()); + start_times_.resize(jobs.size()); + + for (size_t i = 0; i < num_workers; ++i) { + pq.push(make_pair(0, -i)); + } + + for (size_t i = 0; i < jobs.size(); ++i) { + pair l = pq.top(); + pq.pop(); + start_times_[i] = -l.first; + assigned_workers_[i] = -l.second; + pq.push(make_pair(l.first - jobs[i], l.second)); + } + } }; int main() { -// vector data = { 5, 4, 3, 2, 1 }; -// HeapBuilder heap_builder; -// heap_builder.UpdateSwaps(data); -// heap_builder.WriteResponse(); - - std::ios_base::sync_with_stdio(false); - HeapBuilder heap_builder; - heap_builder.Solve(); - return 0; + std::ios_base::sync_with_stdio(false); + JobQueue job_queue; + job_queue.Solve(); + return 0; } -//TEST(BuildHeap, t) { -// vector data = {5, 4, 3, 2, 1}; -// HeapBuilder heap_builder; -// heap_builder.UpdateSwaps(data); -// ASSERT_EQ(3, heap_builder.swaps.size()); -// ASSERT_EQ(1, heap_builder.swaps[0].first); -// ASSERT_EQ(4, heap_builder.swaps[0].second); -// ASSERT_EQ(0, heap_builder.swaps[1].first); -// ASSERT_EQ(1, heap_builder.swaps[1].second); -// ASSERT_EQ(1, heap_builder.swaps[2].first); -// ASSERT_EQ(3, heap_builder.swaps[2].second); +//TEST(ParralelProcessing, t) { +// vector jobs = { 1, 2, 3, 4, 5 }; +// vector expected_assigned_workers = { 0, 1, 0, 1, 0 }; +// vector expected_start_times = { 0, 0, 1, 2, 4 }; +// JobQueue jq; +// jq.num_workers = 2; +// jq.jobs = jobs; +// jq.AssignJobsImproved(); +// ASSERT_EQ(expected_assigned_workers, jq.assigned_workers()); +// ASSERT_EQ(expected_start_times, jq.start_times()); //} // -//TEST(BuildHeap, t1) { -// vector data = {1, 2, 3, 4, 5}; -// HeapBuilder heap_builder; -// heap_builder.UpdateSwaps(data); -// ASSERT_EQ(0, heap_builder.swaps.size()); +//TEST(ParralelProcessing, t1) { +// vector jobs = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, +// 1, 1 }; +// vector expected_assigned_workers = { 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, +// 3, 0, 1, 2, 3, 0, 1, 2, 3 }; +// vector expected_start_times = { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, +// 2, 3, 3, 3, 3, 4, 4, 4, 4 }; +// JobQueue jq; +// jq.num_workers = 4; +// jq.jobs = jobs; +// jq.AssignJobsImproved(); +// ASSERT_EQ(expected_assigned_workers, jq.assigned_workers()); +// ASSERT_EQ(expected_start_times, jq.start_times()); //} -// -- cgit v1.2.3