7
\$\begingroup\$

I have been solving the following problem:

Given n numbers find out the least k numbers from them. For example, if there are 8 numbers like 5,6,3,4,7,8,9,-1. For k = 3 the result will be -1,3,4.

I implemented it in the following way:

  1. make heap with first k numbers
  2. traverse the rest k-n numbers
    1. if heapMax > any of the k numbers then
    2. swap
  3. return heap containing k numbers

Can you please review my code and provide me with feedback?

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

std::vector<int> getKLeastNumbers(std::vector<int> &nums, int k)
{
    std::vector<int> tmpNums;

    if(k<=0 || k > nums.size())
    {
        return tmpNums;
    }

    for(int i=0; i<k; i++)
    {
        tmpNums.push_back(nums.at(i));
    }
    std::make_heap(tmpNums.begin(), tmpNums.end());

    for(int i=k; i<nums.size(); i++)
    {
        if (tmpNums.front() > nums.at(i))
        {
            int tmp = nums.at(i);

            nums.at(i) = tmpNums.front();

            std::pop_heap(tmpNums.begin(),tmpNums.end());
            tmpNums.pop_back();

            tmpNums.push_back(tmp);
            std::push_heap(tmpNums.begin(), tmpNums.end());
        }
    }

    return tmpNums;
}

int main()
{
    // test codes
    std::vector<int>nums;
    nums.push_back(56);
    nums.push_back(5);
    nums.push_back(6);
    nums.push_back(60);
    nums.push_back(-6);
    nums.push_back(3);
    nums.push_back(600);

    nums = getKLeastNumbers(nums,1);

    for(int i=0; i<nums.size(); i++)
    {
        std::cout<<nums.at(i)<<std::endl;
    }

    std::vector<int>nums2;
    nums2.push_back(56);

    nums2 = getKLeastNumbers(nums2,-1);

    std::cout<<std::endl<<"Test set 2 "<<std::endl;
    for(int i=0; i<nums2.size(); i++)
    {
        std::cout<<nums2.at(i)<<std::endl;
    }
}
\$\endgroup\$
8
\$\begingroup\$

I assume you can use C++11.

  • Use initializer lists:

    std::vector<int>nums;
    nums.push_back(56);
    nums.push_back(5);
    nums.push_back(6);
    nums.push_back(60);
    nums.push_back(-6);
    nums.push_back(3);
    nums.push_back(600);
    

    becomes

    std::vector<int> nums = {56, 5, 6, 60, -6, 3, 600};
    
  • Use range based for:

    nums = getKLeastNumbers(nums, 1);
    
    for(int i=0; i<nums.size(); i++)
    {
        std::cout<<nums.at(i)<<std::endl;
    }
    

    becomes

    for (auto &i : getKLeastNumbers(nums, 1))
        std::cout << i << '\n';
    
  • Do not hide bugs. If you detect that someone used your function wrong tell them instead of letting them wonder why the return value doesn't make sense.

    if(k<=0 || k > nums.size())
    {
        return tmpNums;
    }
    

    becomes

    assert(k <= 0 && k > nums.size());
    

    or

    if (k <=0 || k > nums.size())
        throw std::range_error("k must be bigger than 0 and less than num's size");
    
  • You seem to be using the heap functions correctly, however, there are functions more suitable for that. I would pick std::partial_sort.

    std::vector<int> getKLeastNumbers(std::vector<int> &nums, int k)
    {
        std::partial_sort(std::begin(nums), std::begin(nums) + k, std::end(nums));
        return { std::begin(nums), std::begin(nums) + k };
    }
    
  • The declaration for getKLeastNumbers is a bit strange. nums is not const and gets modified which feels unexpected. Why can I not use getKLeastNumbers on a const std::vector?. I would prefer a const & to preserve the original value, allow const vector and to be able to initialize nums with an initializer list directly.

\$\endgroup\$
  • 1
    \$\begingroup\$ I'd also suggest that the second argument to getKLeastNumbers() should be unsigned rather than int. A whole class of possible errors is rendered impossible by that small change. \$\endgroup\$ – Edward Nov 16 '14 at 22:39
  • 1
    \$\begingroup\$ @Edward I am not convinced that this is good advice. First you can still pass negative numbers which become huge positive numbers which does not help reducing error potential. Secondly I tend to calculate differences of sizes which would make me clutter the code with casts. I would even prefer sizeof to return a signed number to prevent if (sizeof(int) - 4 < 0) to do something unexpected. \$\endgroup\$ – nwp Nov 16 '14 at 23:37
  • 1
    \$\begingroup\$ @Edward: I disagree that it removes the error. But rather it hides errors (if you are not validating already) because of auto conversion. if the interface is only takes unsigned int and I call it getKLeastNumbers(data, -1); it still compiles just fine. It will run just fine and the -1 silently becomes some big number. There is no magic bullet you have to validate your input. \$\endgroup\$ – Martin York Nov 17 '14 at 6:53
  • 2
    \$\begingroup\$ There was a great talk by Bjarne Stroustrup at going native last year. Is it worth using unsigned number for anything. Do they really buy you anything. Answer no. An extra bit. Now worth it. The consensus is that you should use signed for everything unless you are using the int for bit flags then use unsigned otherwise signed. They also admitted that the choice of the standard library using unsigned in most places was a mistake. \$\endgroup\$ – Martin York Nov 17 '14 at 15:01
  • 1
    \$\begingroup\$ at 44 minutes 30 second mark Herb Sutter says Quote: "Unfortunately is a mistake in the STL and standard that we use use unsigned integers". \$\endgroup\$ – Martin York Nov 17 '14 at 18:00
7
\$\begingroup\$

There are several things that you could improve, especially with regards to containers usage:

  • If you can use C++11 or a more recent version of the C++ standard, then you can use an initializer list to push elements into your std::vector when your construct it:

    std::vector<int> nums = { 56, 5, 6, 60, -6, 3, 600 };
    
  • If you don't explicitly need indices, then use iterators to iterate over containers. It helps to write more generic code. Here is one of your loops converted to iterators. I also used the C++11 range-based for loop to make it even clearer:

    for (int& elem: nums)
    {
        if (tmpNums.front() > elem)
        {
            int tmp = elem;
            elem = tmpNums.front();
    
            std::pop_heap(tmpNums.begin(),tmpNums.end());
            tmpNums.pop_back();
    
            tmpNums.push_back(tmp);
            std::push_heap(tmpNums.begin(), tmpNums.end());
        }
    }
    
  • By the way, in this loop, instead of popping the last element and pushing back a new one, you could simply assign the new value to the last element of the container:

    std::pop_heap(tmpNums.begin(),tmpNums.end());
    tmpNums.back() = tmp;
    std::push_heap(tmpNums.begin(), tmpNums.end());
    
  • Instead of using a loop to initialize tmpNums with the \$k\$ first elements of nums, you can use the std::vector constructor which takes two iterators:

    std::vector<int> tmpNums(nums.begin(), nums.begin()+k);
    

    This will create tmpNums and initialize it by copying the elements in the range [vec[0], vec[k]), which is exactly what you want.

  • I don't especially like this condition to return early:

    if(k<=0 || k > nums.size())
    {
        return tmpNums;
    }
    

    In my opinion, calling the function and asking to treat a negative number of elements or a number of elements greater than the one available is a logic error and should fail instead of returning an empty std::vector which doesn't really help the user. I would probably replace the condition by hard assertions:

    assert(k > 0);
    assert(k <= nums.size());
    

    It is important for the user to know why that fails. Therefore, I would also document these as preconditions in the function documentation.

\$\endgroup\$
  • \$\begingroup\$ Asserts are for things that will never happen in production. I.E. you validate your pre-conditions are holding in your test environment (in production asserts do nothing). For things that can happen but should not something else is more appropriate (potentially exception). \$\endgroup\$ – Martin York Nov 17 '14 at 7:08
  • \$\begingroup\$ @LokiAstari Frankly, in our case, if you use the function correctly, there should not be errors here. Passing a negative k clearly shows that you did something wrong, that won't appear at random and you should be able to catch the problem during the test phase. \$\endgroup\$ – Morwenn Nov 17 '14 at 9:54
  • \$\begingroup\$ Assuming at some point this will be user input you really need to validate and use another method other than assert (probably outside the function were the user inputs the data). My point is that assert is not the same as validation. assert is used to validate correctness of the calling function while testing the code. \$\endgroup\$ – Martin York Nov 17 '14 at 14:42
6
\$\begingroup\$

Since there are already a couple of reviews, I won't repeat that advice, but can add a few other things.

Include relevant #include files

The code uses std::push_heap which is defined in <algorithm> but the code doesn't include that file. It should.

Use appropriate types

Because you're looking for the least \$k\$ numbers from a collection, it doesn't make much sense to ask for a negative number of them. For that reason, I'd recommend making k an unsigned parameter.

Simplify the code by using standard operations

A simpler way to write this function would be this:

template <typename T>
T getKLeast(T collection, unsigned k)
{
    std::sort(collection.begin(), collection.end());
    if (k > collection.size())
        return collection;
    return T{collection.begin(), collection.begin()+k};
}

This makes a copy of the passed type, sorts it, and then returns only the first \$k\$ items. Also, I've used a template so that it works just as well with a std::list or std::vector<float> or even std::vector<std::string>.

Don't use std::endl if '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl.

Simplify the test code by overloading operator<<

If we define this function:

std::ostream &operator<<(std::ostream &out, const std::vector<int>&collection)
{
    for (const auto &item : collection)
        std::cout << item << ", ";
    return out;
}

The main code can get really simple now:

int main()
{
    using namespace std;

    vector<int>nums{56, 5, 6, 60, -6, 3, 600};

    cout << getKLeast(nums, 3) << '\n'
         << getKLeast(nums, 2) << '\n'
         << getKLeast(nums, 0) << '\n'
         << getKLeast(nums, 100) << '\n';
}

sample output

On my machine, here's what that program prints:

-6, 3, 5, 
-6, 3, 

-6, 3, 5, 6, 56, 60, 600, 
\$\endgroup\$
  • 1
    \$\begingroup\$ Regarding std::endl take a look at what Scott Meyers has to say about it. Also my partial_sort beats your sort ;D \$\endgroup\$ – nwp Nov 16 '14 at 23:35
  • 1
    \$\begingroup\$ @nwp: regarding partial_sort vs. sort. If you're thinking that partial_sort is faster, you should test that assumption. Testing here and by others shows sort is typically much faster. \$\endgroup\$ – Edward Nov 17 '14 at 2:32
  • \$\begingroup\$ Don't like the idea of defining a serializer for such a generic container. You may accidentally hide errors. I would create a specific printer wrapper that the user must explicitly use to prevent accidental printing. std::cout << VectorPrinter(getKLeast(nums, 3)) << "\n"; \$\endgroup\$ – Martin York Nov 17 '14 at 7:12
  • \$\begingroup\$ @Edward I did a benchmark of my own based on the one you linked. partial_sort is faster if the percentage of the data you sort is small whereas sort is faster if the percentage is high. Turns out the break even point is around 23%. The test you linked always uses 50% which makes partial_sort look bad. I felt like k would be small compared to n for this problem, but a better solution would be to check if k < n * .23 and pick the sorting function accordingly. I suppose the break even percentage depends on the system and data types. \$\endgroup\$ – nwp Nov 23 '14 at 16:09
5
\$\begingroup\$

A more concise way of displaying the vectors, without the use of any loops, is to use std::copy() with std::ostream_iterator:

std::copy(nums.begin(), nums.end(), std::ostream_iterator<int>(std::cout, "\n");

std::copy(nums2.begin(), nums2.end(), std::ostream_iterator<int>(std::cout, "\n");

This doesn't require any C++11, in case you don't have access to it.

\$\endgroup\$
  • \$\begingroup\$ Would you recommend to always do this? If so, why? I can't seem to find a liking to use copy for printing. \$\endgroup\$ – nwp Nov 16 '14 at 22:09
  • \$\begingroup\$ @nwp: That may depend on readability and what is available to you. There are other ways of printing storage containers, and I'm not suggesting that this is the best way. I'm not too keen to always using a loop just for displaying something. \$\endgroup\$ – Jamal Nov 16 '14 at 22:13

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.