summaryrefslogtreecommitdiff
path: root/Sources
diff options
context:
space:
mode:
authorHaidong Ji2019-02-24 15:33:28 -0600
committerHaidong Ji2019-02-24 15:33:28 -0600
commitcf6f4a6dcb62c21b5f498396d01e5323d42852a7 (patch)
treeabd3083982ee336cb01d868aeacdc2634f849082 /Sources
parent8047395062ce2234a94e35dadf11d8f29ecfb2ac (diff)
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 :)
Diffstat (limited to 'Sources')
-rw-r--r--Sources/DataStructure.cpp165
1 files changed, 82 insertions, 83 deletions
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 <iostream>
#include <vector>
#include <algorithm>
+#include <queue>
//#include <gtest/gtest.h>
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<int> data_;
-// vector<pair<int, int> > 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<int> assigned_workers_;
+ vector<long long> start_times_;
-public:
- vector<pair<int, int>> 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<int> &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<int> &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<long long> 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<int> jobs;
void Solve() {
ReadData();
-// GenerateSwaps();
- UpdateSwaps(data_);
+ AssignJobsImproved();
WriteResponse();
}
+ const vector<int>& assigned_workers() const {
+ return assigned_workers_;
+ }
+ const vector<long long>& start_times() const {
+ return start_times_;
+ }
+
+ void AssignJobsImproved() {
+ std::priority_queue<pair<long, int>> 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<long, int> 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<int> 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<int> 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<int> jobs = { 1, 2, 3, 4, 5 };
+// vector<int> expected_assigned_workers = { 0, 1, 0, 1, 0 };
+// vector<long long> 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<int> data = {1, 2, 3, 4, 5};
-// HeapBuilder heap_builder;
-// heap_builder.UpdateSwaps(data);
-// ASSERT_EQ(0, heap_builder.swaps.size());
+//TEST(ParralelProcessing, t1) {
+// vector<int> jobs = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+// 1, 1 };
+// vector<int> expected_assigned_workers = { 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2,
+// 3, 0, 1, 2, 3, 0, 1, 2, 3 };
+// vector<long long> 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());
//}
-//