1
\$\begingroup\$

I'm learning priority scheduling algorithm and trying to implement it using std::vector. But the current performance of my code that's partially implemented is not that good since I'm performing sort operation every time I add a new process to std::vector list. Can somebody suggest ways I can improve my current partially implemented algorithm. This is my code:

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

void print_list(const std::vector<std::pair<int, int>>& pair_list) {
    for (const auto& pa : pair_list)
        std::cout << "process_ID: " << pa.first << ", " << "priority: " << pa.second << "\n";
    std::cout << std::endl;
}

void add_pro(int pro_ID, int pro_pri, std::vector<std::pair<int, int>>& pair_list) {
    pair_list.emplace_back(pro_ID, pro_pri);

    std::sort(pair_list.begin(), pair_list.end(), [=](std::pair<int, int>& a, std::pair<int, int>& b) {
        return a.second < b.second;
    });
}

bool check_pro_is_present(int pro_ID, const std::vector<std::pair<int, int>>& pair_list) {
    for (const auto& pa : pair_list) {
        if (pa.first == pro_ID)
            return true;
    }

    return false;
}

bool is_higher_pri_pro_present(int pro_ID, const std::vector<std::pair<int, int>>& pair_list) {
    if (pair_list.front().first == pro_ID)
        return false;

    return true;
}

int main() {
    std::vector<int> process_ID_list { 1345, 45, 5646, 52525, 55757, 23424, 68696, 55878, 667, 252 };
    std::vector<int> process_pri_list { 41, 334, 747, 41, 47, 7, 75, 544, 42, 6 };
    
    std::vector<std::pair<int, int>> pair_list;
    for (int i = 0; i < process_ID_list.size(); ++i) {
        int new_pro_ID = process_ID_list.at(i);
        int new_pro_pri = process_pri_list.at(i);

        if (!check_pro_is_present(new_pro_ID, pair_list))
            add_pro(new_pro_ID, new_pro_pri, pair_list);
        else
            std::cout << "process is already in list" << std::endl;

        print_list(pair_list);
    }

    int query_pro_ID = 1345;
    std::cout << std::boolalpha << is_higher_pri_pro_present(query_pro_ID, pair_list) << std::endl;

    return (EXIT_SUCCESS);
}
\$\endgroup\$
6
  • \$\begingroup\$ One sound choice here is a priority queue, such as std::priority_queue. \$\endgroup\$ Jan 17 at 7:09
  • 1
    \$\begingroup\$ @JerryCoffin Actually I thought of using it, but the problem is I can't iterate through the list(without popping or copying) if I want to say print current list data and to remove any process from the list based on process identifier due to some reasons, if I implement using std::priority_queue. \$\endgroup\$
    – Harry
    Jan 17 at 7:13
  • \$\begingroup\$ In that case, perhaps a vector with make_heap, pop_heap (etc.) will be more amenable to your needs. \$\endgroup\$ Jan 17 at 7:16
  • \$\begingroup\$ @JerryCoffin what about std::set?. Do you think it has better performance over std::vector in this case scenario? \$\endgroup\$
    – Harry
    Jan 17 at 7:18
  • \$\begingroup\$ Harder to guess about set. With set, each node is dynamically allocated, so a lot here depends on how fast the allocator is (but it's probably at least worth a try). \$\endgroup\$ Jan 17 at 7:24
1
\$\begingroup\$

While comments have suggested more suitable types than std::vector, I'm going to assume that the use of this underlying type is a given, and suggest straightforward improvements without changing that.

The main performance concern is here:

void add_pro(int pro_ID, int pro_pri, std::vector<std::pair<int, int>>& pair_list) {
    pair_list.emplace_back(pro_ID, pro_pri);

    std::sort(pair_list.begin(), pair_list.end(), [=](std::pair<int, int>& a, std::pair<int, int>& b) {
        return a.second < b.second;
    });
}

It's wasteful to sort the vector every time we add an element, when we know it was sorted before we called this function. Instead, we need to insert the new element in the correct position.

void add_pro(int pro_ID, int pro_pri, std::vector<std::pair<int, int>>& pair_list)
{
    auto position = std::upper_bound(pair_list.begin(), pair_list.end(), pro_pri,
                                     [](auto pri, auto const& ele) { return pri < ele.second; });
    pair_list.emplace(position, pro_ID, pro_pri);
}

We use the type std::vector<std::pair<int, int>> a lot. It's worth giving it a name:

using priority_queue = std::vector<std::pair<int, int>>;

That makes changing the code easier, e.g. if we decide that process ids actually need to be unsigned long or something.

However, I observe that every function takes one of these as an argument. That suggests that we want a class with this vector as member, then convert those free functions to be members of that class.


Thank you for including the test program - that's always helpful in a review. There's a couple of small points:

for (int i = 0; i < process_ID_list.size(); ++i) {

We're mixing signed and unsigned types in this comparison (int and std::size_t). Obviously we should change int i to std::size_t i - and enable more compiler warnings.

       std::cout << "process is already in list" << std::endl;

Prefer to use std::cerr for error messages.


The pattern if (condition) return true; else return false; can simply be replaced with return condition. So:

bool is_higher_pri_pro_present(int pro_ID, const std::vector<std::pair<int, int>>& pair_list)
{
    return pair_list.front().first != pro_ID;
}

The loop in check_pro_is_present can be replaced with std::any_of:

bool check_pro_is_present(int pro_ID, const std::vector<std::pair<int, int>>& pair_list)
{
    return std::any_of(pair_list.begin(), pair_list.end(),
                       [pro_ID](auto const& e){ return e.first == pro_ID; });
}

Modified code

This is just a beginning - we'll probably want an initialiser-list constructor, and replace print() with operator<<(), but it's a start.

#include <algorithm>
#include <iostream>
#include <utility>
#include <utility>
#include <vector>

template<typename T, typename Priority = int>
class priority_queue
{
    std::vector<std::pair<T, Priority>> values = {};

public:
    void print(std::ostream &os) const {
        for (const auto& pa : values) {
            os << "process_ID: " << pa.first << ", "
               << "priority: " << pa.second << '\n';
        }
        std::cout << '\n';
    }

    void add(T t, Priority pri) {
        auto const position
            = std::upper_bound(values.begin(), values.end(),
                               pri,
                               [](auto const& pri, auto const& ele) { return pri < ele.second; });
        values.emplace(position, std::move(t), std::move(pri));
    }

    bool contains(int pro_ID) const
    {
        return std::any_of(values.begin(), values.end(),
                           [pro_ID](auto const& e){ return e.first == pro_ID; });
    }

    bool has_higher(int pro_ID) const
    {
        return values.front().first != pro_ID;
    }
};

int main()
{
    const std::pair<int,int> processes[]
        = { { 1345, 41 }, { 45, 334 }, { 5646, 747 },
            { 52525, 41 }, { 55757, 47 },
            { 23424, 7 }, { 68696, 75 }, { 55878, 544 },
            { 667, 42 }, { 252, 6 } };

    priority_queue<int, int> queue;
    for (auto const& p: processes) {
        if (queue.contains(p.first)) {
            std::cerr << p.first << " is already in list\n";
        } else {
            queue.add(p.first, p.second);
        }
        queue.print(std::cout);
    }

    int query_pro_ID = 1345;
    std::cout << std::boolalpha << queue.has_higher(query_pro_ID) << '\n';
}
\$\endgroup\$
3
  • \$\begingroup\$ Thanks for the suggestions. Well if you think that this can be better implemented other than using std::vector, please let me know. \$\endgroup\$
    – Harry
    Jan 17 at 10:27
  • \$\begingroup\$ I might write a separate answer for that, if I get time. Or perhaps somebody else will? \$\endgroup\$ Jan 17 at 10:34
  • 1
    \$\begingroup\$ @TobySpeight, I can do that next week, although it might take time until Friday or so. I will ping you here if you’re interested in the results. \$\endgroup\$ Jan 17 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.