10
\$\begingroup\$

I am solving the "Sort" problem on Kattis.

Mirko is a great code breaker. He knows any cipher in the world can be broken by frequency analysis. He has completely the wrong idea what frequency analysis is, however.
He intercepted an enemy message. The message consists of N numbers, smaller than or equal to C.
Mirko belives freqency analysis consists of sorting this sequence so that more frequent numbers appear before less frequent ones.
Formally, the sequence must be sorted so that given any two numbers X and Y, X appears before Y if the number of times X appears in the original sequence is larger than the number of time Y does. If the number of appearances is equal, the number whose value appears sooner in the input should appear sooner in the sorted sequence.
Help Mirko by creating a “frequency sorter”.
Input
First line of input contains two integers, N (1≤N≤1000), the length of the message, and C (1≤C≤1000000000), the number from the task description above.
The next line contains N positive integers smaller than or equal to C, the message itself.

Basically, the problem is as follows. Let xs be a nonempty vector of positive integers. There are only few integers in this vector, but they have a big range. (The maximum value c is given in the problem, but my code does not use the information.) Sort the integers according to the following criteria.

  1. For any two elements x and y of xs, if x occurs more often than y, then x appears first; if y appears more often, y appears first.
  2. If x and y appear equally often, then x occurs first if the very first occurrence of x is earlier than that of y.

I use a comparison sort (provided by the C++ runtime) with a smart comparator. This comparator knows the frequency and the index of the first appearance of every element. This information is not inherent to the integers. Rather, it depends entirely on their location within the vector. This contextual information is generated when a comparator is created for a given vector. Upon application on elements x and y, it returns true if x must appear before y.

I have used custom comparators before, but never have I used anything that contains state. In the disassembly with -Os I see many copy and move constructors called under sort(vector<unsigned> &). The code passes all tests, and it's not slow.

But I wonder why the disassembly reveals so many copy and move calls, and whether this pattern of using heavy comparators is discouraged in C++. If this looks like a known pattern, I want to know its name. I appreciate general comments and insights.

#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iostream>

typedef std::vector<unsigned> vector;

/// Comparison based on knowledge of the entire vector
struct compare {
    std::multiset<unsigned> bag;
    std::map<unsigned, size_t> indices;

    /// Extract frequency and initial index of every element.
    explicit compare(vector const &xs) {
        for (size_t i = 0u; i < xs.size(); ++i) {
            unsigned const x = xs[i];
            bag.insert(x);
            if (!indices.count(x)) {
                indices[x] = i;
            }
        }
    }

    /// True if `x` must go before `y`.
    [[nodiscard]] bool operator()(unsigned x, unsigned y) const {
        return bag.count(x) > bag.count(y)
               || (bag.count(x) == bag.count(y) && indices.at(x) < indices.at(y));
    }
};

static void sort(vector &v) {
    compare c(v);
    std::sort(v.begin(), v.end(), c);
}

int main() {
    vector v;
    {
        // Get `n` unsigned integers from console.
        // Unused: `c` (upper bound for integers)
        unsigned n, c;
        std::cin >> n >> c;
        v.reserve(n);
        while (n--) {
            unsigned x;
            std::cin >> x;
            v.push_back(x);
        }
    }
    // Sort according to the problem description
    sort(v);
    // Print all
    for (unsigned const x : v) {
        std::cout << x << ' ';
    }
    return 0;
}

Update

Summary: Used shared pointers to enforce shared ownership w/o overhead

According to G. Sliepen, the internal implementation of std::sort by g++ makes many copy of the Compare object. So, I decided to keep a smart pointer inside the object that takes care of simultaneous uses by different instances of the internal function calls.

#include <memory>
===
struct compare {
private:
    struct vector_context {
        std::multiset<unsigned> bag;
        std::map<unsigned, size_t> indices;
    };

    std::shared_ptr<vector_context> context;

public:
    explicit compare(vector const &xs) : context(new vector_context) {
        for (size_t i = 0u; i < xs.size(); ++i) {
            unsigned const x = xs[i];
            context->bag.insert(x);
            if (!context->indices.count(x)) {
                context->indices[x] = i;
            }
        }
    }

    [[nodiscard]] bool operator()(unsigned x, unsigned y) const {
        return context->bag.count(x) > context->bag.count(y)
               || (context->bag.count(x) == context->bag.count(y)
                   && context->indices.at(x) < context->indices.at(y));
    }
};

The code change is minimal, and the runtime has improved four-fold.

\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to code review. The rules of the site are that questions that answer programming challenges include the text of the programming challenge and possibly link to it, include the text because links can get broken. In this case I have done it for you, but in the future please include the text in the question. \$\endgroup\$ – pacmaninbw Jun 27 at 11:42
5
\$\begingroup\$

The main issue is that the comparator object is passed by value. Not only from your application to std::sort(), but it's also passed by value internally in the implementation of std::sort(). This means that bag and indices get copied by value a lot. So you ideally want to generate those only once, and then have class compare store a pointer or reference to those. I think there are several possible approaches; you could keep the constructor mainly as it is, but instead of storing those vectors directly, use a std::shared_ptr to manage their storage. The default copy constructor will then just take care of updating the refcounts for you:

struct compare {
    std::shared_ptr<std::multiset<unsigned>> bag;
    std::shared_ptr<std::map<unsigned, size_t>> indices;

    /// Extract frequency and initial index of every element.
    explicit compare(vector const &xs):
        bag{new std::multiset<unsigned>},
        indices{new std::map<unsigned, size_t>},
    {
        for (size_t i = 0u; i < xs.size(); ++i) {
            unsigned const x = xs[i];
            bag->insert(x);
            if (!indices->count(x)) {
                (*indices)[x] = i;
            }
        }
    }

    /// True if `x` must go before `y`.
    [[nodiscard]] bool operator()(unsigned x, unsigned y) const {
        return bag->count(x) > bag_>count(y)
               || (bag->count(x) == bag->count(y) && indices->at(x) < indices->at(y));
    }
};

You can improve this further by combining bag and indices into on struct, so you only need one std::shared_ptr to hold them.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you. I appreciate this answer because I had no idea where smart pointers (in this case shared_ptr representing shared ownership) could be used. I had heard about the concept of ownership, but this answer pushed me to dig deeper. Thank you for introducing me to this concept. \$\endgroup\$ – YuJin Kim Jun 27 at 21:47
5
\$\begingroup\$

As explained in another answer, the implementation of the standard library that you use internally passes the comparator by value. It would not have to do that, but you still would have passed it by value to sort, and it is best to avoid that copying altogether. Now, you do not need to change the structure of your program to avoid this.

First, now that you are aware of the problem, I would advise you to make the comparator non-copyable just to ensure that you do not accidentally copy it.

struct compare {
    // There is no need to copy this.
    compare(const compare &) = delete;

...

With that change, your original program will not compile any more. Now next, we do not pass your heavy-weight comparator itself any more, but a light-weight wrapper that only holds a reference to it.

static void sort(vector &v) {
    const compare c(v);
    std::sort(v.begin(), v.end(),
              [&c](unsigned x, unsigned y) { return c(x, y); });
}

Now this does exactly what you intended in the first place. If you are worried that you might later change the type of the numbers from unsigned to something else and forget to also change it in the lambda, you can use const auto & there instead of unsigned.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you. I learned that std::copy(RandomIt, RandomIt, Compare) is allowed to internally pass around the Compare function by value. \$\endgroup\$ – YuJin Kim Jun 27 at 21:50

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.