5
\$\begingroup\$

I want to solve the following task --- I am given a vector of integers. I want to 'compress' this list, where the elements will be replaced with numbers 0 through n - 1, where n is the number of unique elements in the vector, such that the relative ordering among the elements is preserved, i.e., if previously vector[index1] < vector[index2], then that is still true after the compression. In other words, each element is replaced with its ranking among the source vector.

For example, given the vector {1, 3, 10, 6, 3, 12}, the elements will be replaced with 0 through 4 since there are 5 unique value. To preserve ordering, it will be transformed into {0, 1, 3, 2, 1, 4}.

Right now, to complete this, I use the following algorithm:

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

using namespace std;

int compress_vector(vector<int>& vec) {
  // function compresses the vector passed in by reference
  // and returns the total number of unique elements
  map<int, int> m;
  set<int>      s;
  for (auto i : vec) s.insert(i);
  int counter = 0;
  for (auto i : s) {
    m[i] = counter;
    counter++;
  }
  for (auto& i : vec) i = m[i];
  return s.size();
}

int main() {
  vector<int> vec = { 1, 3, 10, 6, 3, 12 };  //

  int size = compress_vector(vec);

  // Should output "0 1 3 2 1 4", then a newline, then a "5"
  for (auto i : vec) cout << i << " ";
  cout << endl;
  cout << size;

  return 0;
}

However, I feel this function is quite messy --- it uses maps, sets, and counters. While this is functional, is there a faster or cleaner way to do this?

Thanks

\$\endgroup\$
5
  • \$\begingroup\$ Your example (and expected output) is confusing and difficult to understand. \$\endgroup\$
    – Casey
    Mar 28 at 2:47
  • \$\begingroup\$ @Casey I guess what is meant here is to apply a bijection from the data to [0, n - 1] that preserves order, or, in other words, replace each value with its rank among the source array. \$\endgroup\$
    – L. F.
    Mar 28 at 4:05
  • \$\begingroup\$ @L.F.: yes, I think this is what I mean. I have been taught that this is called "list compression," but if you have another term/description that would better explain it, please edit it in. \$\endgroup\$
    – Mike Smith
    Mar 28 at 6:22
  • \$\begingroup\$ @MikeSmith I think your description is mostly fine. I've edited the question hopefully clarify it; please take a look and refine it as appropriate. \$\endgroup\$
    – L. F.
    Mar 28 at 6:28
  • \$\begingroup\$ It's great! Now I just need my original question answered ;) \$\endgroup\$
    – Mike Smith
    Mar 28 at 6:29
4
\$\begingroup\$

Algorithm improvements

I really don’t understand what this algorithm is supposed to be doing. Your description of it is incomplete and vague (for example, you say vector[index1] < vector[index2]… but what is index1 and index2?), and the single example is not illuminating. It looks like you’re just trying to get the sorted position of each element in the vector. So it’s very possible that there is a much better algorithm that can solve this; there’s no way for me to know when what you’re trying to do makes no sense to me.

However, I can look at what your existing implementation is doing and at least improve on that a bit.

You use a set to get all the unique elements in the vector, and then you use a map to get… I dunno, something something count (the sorted index?). I can’t help you with the second part. But I can help you with the first part, because you don’t need the set. You can use the map to get the unique values, like so:

auto compress_vector(std::vector<int>& vec)
{
    auto m = std::map<int, int>{};

    // You don't need the set. You can use the map's keys to get the unique
    // values.
    for (auto i : vec)
        m[i] = 0;

    // And then you can recover the "set" of unique values by just iterating
    // on the map's keys.
    auto counter = 0;
    for (auto [i, _] : m)
        m[i] = counter++;

    // The above loop may be optimized by avoiding the duplicate lookup:
    //  for (auto& p : m)
    //      p->second = counter++;

    for (auto& i : vec)
        i = m[i];

    return m.size();
}

You could also go the other way, and keep the set but ditch the map:

auto compress_vector(std::vector<int>& vec)
{
    auto s = std::set<int>{};

    for (auto i : vec)
        s.insert(i);

    // The values of the map are just the indices of the set.
    for (auto& i : vec)
        i = std::distance(s.begin(), s.find(i));

    return s.size();
}

Depending on a lot of factors, it might be more efficient to ditch the set and use a sorted vector instead:

auto compress_vector(std::vector<int>& vec) {
    // Take care of the degenerate case of an empty input vector first.
    //
    // Not strictly necessary, but will save a lot of work.
    if (vec.empty())
        return 0;

    // You could also do this:
    //  if (vec.size() == 1)
    //  {
    //      vec[0] = 0;
    //      return 1;
    //  }

    // A second container, either a map, set, or second vector, is probably
    // unavoidable, because we need to keep track of the original values while
    // also changing the vector's contents, in order to know the sorted
    // indices.
    //
    // Note that this is the lazy way of building the sorted vector. If there
    // are a lot of duplicate values, it *might* be faster to:
    //  1)  reserve vec.size()
    //  2)  for each element in vec, do a lower_bound() search, to find if
    //      it's already in sorted, and if not, then you have the insert
    //      position
    auto sorted = vec;
    std::sort(sorted.begin(), sorted.end());
    sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());

    // Transform each element in the input vector into the index of the
    // element in the sorted vector.
    std::transform(vec.begin(), vec.end(), vec.begin(),
        [&sorted](auto i)
        {
            // Instead of std::find(), you could also use a binary search,
            // like std::lower_bound().
            return static_cast<int>(
                std::distance(
                    sorted.begin(),
                    std::find(sorted.begin(), sorted.end(), i)
                )
            );
        }
    );

    return sorted.size();
}

Code review

using namespace std;

This is always a bad idea. You can probably get away with it in simple, toy programs, but you should never do it in real code.

int compress_vector(vector<int>& vec)

“Out” parameters (function parameters taken by non-const reference, and then modified with the “return” value) are generally not a great idea. They usually make functions harder to use, because they put the onus on the user to set up space for the return. What if I want the original vector and the “compressed” vector? Now I have to deal with the pain of setting up the result manually, rather than just writing auto result = compress_vector(input);. And if the vector I want to “compress” is already const (which is often the case), it’s on me to make a copy again.

I know there is an argument that out parameters can be more efficient, but that doesn’t really apply here, because you’re creating whole maps, sets, and/or copies of the vector in the function anyway.

An even better design would be to take an output iterator argument.

for (auto i : vec) s.insert(i);

Don’t do this. Saving a single line in the function just isn’t worth the risk of missing the hard-to-spot loop body and introducing bugs. If your function is so long that you actually need to save a line or two in order to fit it on screen, your function is too long in any case, and should be broken up.

for (auto i : vec) s.insert(i);
int counter = 0;
for (auto i : s) {
  m[i] = counter;
  counter++;
}
for (auto& i : vec) i = m[i];

Space out the code. There are THREE loops here, jammed all together. That is three entirely separate logical sections of the function. Each section should be separated from the others by a blank line, to make it clear where the function’s “paragraphs” are. (And, of course, both the first and last loops should not be single lines.)

You should also consider using algorithms instead of naked loops, for two reasons. First, they make your code clearer: a naked loop could be doing ANYTHING… but an algorithm spells out exactly what is happening. Also, algorithms are much easier to optimize.

So the big glob of code above could be:

std::for_each(vec.begin(), vec.end(), [&s](auto i) { s.insert(i); });

auto counter = 0;
std::for_each(s.begin(), s.end(), [&m, &counter](auto i) { m[i] = counter++; });

std::for_each(vec.begin(), vec.end(), [&m](auto& i) { i = m[i]; });

Of course, all three algorithms are for_each() here, because I don’t really understand what the loops are supposed to be doing. for_each() is what you use when nothing else makes more sense. You’ll note that in the modified algorithm I wrote above, I used more specific algorithms, like transform(), unique(), and find() because I understood what was going on.

return s.size();

You have a bug here. s.size() gives an unsigned type, which is problematic enough, but the real issue is that the type may be (and often is) larger than an int. But you are forcing it to be crammed into an int, which may cause truncation, or other weirdness. If you’re absolutely sure you want compress_vector() to return int, then you should at least assert that the size of the vector is smaller than the maximum value of int. Or, on the other hand, maybe you don’t really want compress_vector() to return int? I don’t understand what you want from this function, so I can’t guess which is the right answer.

In main():

for (auto i : vec) cout << i << " ";

Once again, this should not be on a single line. Also, you probably don’t want a whole string constant for just a space; you probably mean ' ', not " ".

cout << endl;

std::endl really makes no sense here. If you want a newline, use a newline: std::cout << '\n';.

return 0;

You don’t need this in main().

Summary

Because your description of the problem is so vague and incomplete, and your examples of the intended usage are so limited and unrevealing, it’s impossible to give good recommendations. There is just so much about this function that is unexplained, and so many unanswered questions: Does it really need to modify the input vector; could it not simply return a new vector instead? Why does it return the number of unique elements; is that really important information? Why does it return that value as an int, rather than std::size_t or std::vector::size_type? And so on and so forth.

The best I can do is offer base-level suggestions going by the literal operations in the given code; in other words, I can only give suggestions for tuning the existing algorithm… I can’t suggest better algorithms, if there are any.

That said, there are certainly some corners you could cut, and some inefficiencies you could remove. You don’t need a set and a map… that’s just overkill in just about any situation. You might even get away with a sorted vector, which should be way more efficient than either a map or a set… especially if you do a binary search.

\$\endgroup\$
5
  • \$\begingroup\$ Sorry, I do not have much experience in all of this --- I just made this function on the fly, and the number of unique elements was important to me at the time I made this function. Yes, you could also return a new vector, and from what I have been told, I think that is the better idea. At this point, I am still trying to learn programming paradigms and the "best" way to do things. If you want to suggest new code to do it, I am completely fine with that. I believe some of the comments may have cleared up a bit of confusion. \$\endgroup\$
    – Mike Smith
    Mar 28 at 6:35
  • 1
    \$\begingroup\$ Oh, there’s nothing to apologize for: there’s nothing wrong with what you wrote. It’s a fine effort. It’s just that to review code properly, just having the code itself isn’t enough; you need information about the context: how that code is going to be used. Programming is engineering; there is no “right” answer, only “this is best for this situation”… so the more one knows about the situation, the more useful one’s review comments can be. \$\endgroup\$
    – indi
    Mar 28 at 13:30
  • \$\begingroup\$ For example, I think it’s possible to do this “compression” with no extra map, set, or even extra vector—to do it all in place with no extra allocation. But that is going to be a really complicated and possibly inefficient algorithm for large data sets. So if it is really important to use an “out” parameter… and your data sets won’t be huge… and you really want to avoid the cost of extra allocations… then maybe that would be the way to go. It all depends on the context. \$\endgroup\$
    – indi
    Mar 28 at 13:30
  • \$\begingroup\$ Oh, ok! I get it now. I failed to provide the context. I will do so next time. \$\endgroup\$
    – Mike Smith
    Mar 28 at 17:54
  • \$\begingroup\$ I don't know. Creating maps and sets is unpleasantly slow due to lots of allocations but the algo you propose is O(n^2) instead of O(n log n) which is rather bad. And I don't see how for_each is better than a naked range-based for loop. The latter is much more preferred as it is less verbose and thus more clear. \$\endgroup\$
    – ALX23z
    Mar 30 at 12:27
0
\$\begingroup\$

It feels to me that it is a bit too much to create both std::map and std::set for such a simple purpose. You just need to generate sorted order of vec and then to adjust it a little bit so elements with same value are mapped to the same index.

size_t compress_vector(vector<int>& vec)
{
   if(vec.empty())
   {
       return 0;
   }
   // plan is to make vector ord of indices so that vec[ord[i]] is sorted
   vector<size_t> ord;
   size_t siz = vec.size();
   ord.reserve(siz);

   for(size_t i = 0; i<siz; i++)
   {
        ord.push_back(i);
   }

   std::sort(ord.begin(), ord.end(), [&vec](size_t l, size_t r){return vec[l] < vec[r];});

   // now with sorted indices one can simply iteratively figure out which mapped value do you have
   // you iterate over elements of ord and keep track of the previous element's value to see if a change in values occurred.
   int prevValue = vec.front();
   size_t count = 0;
   for(size_t i : ord)
   {
       if(prevValue != vec[i])
       {
             prevValue = vec[i];
             count++;
       }
       vec[i] = (int)count;
    }

    return count+1;
  }
\$\endgroup\$
2
  • \$\begingroup\$ I think there might be a solution by using a std::vector<std::pair<int, int>> and sorting it. \$\endgroup\$
    – Mike Smith
    Mar 30 at 17:57
  • \$\begingroup\$ @MikeSmith yeah instead of sorting ord according to some lambda you can create pair where first element is value while second is original index. Then continue with equivalent logical procedure. \$\endgroup\$
    – ALX23z
    Mar 30 at 18:03

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.