Return to Revisions

On my machine (i7 6700HQ running gcc 7.1.1 and compiled with -O3) your code runs in the following time:

./main  0.57s user 0.18s system 89% cpu 0.834 total

That's pretty good. No matter what I tried, I always got a value around 0.5s, so I can't provide anything that can speed up your code, sorry.

1. Compile with every warning turned on. In my case, g++ reports 2 things:

    main.cpp: In function 'void select_coordinates_highest_occurrence(std::vector<Coordinate>&)':
    main.cpp:48:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < node_degree_vect.size() / 2; i++) {
                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    main.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < high_occurrences.size(); i++) {
                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~
   

Please fix them.

2. I don't know if this goes against your requirement, but typedefing structs is only a thing in C. In C++, there is no difference, so just leave it out.

3. Mark structs that shouldn't be used as base classes final, to prevent any potential bugs about a non-virtual destructor.

4. My opinion: Using integers as booleans is confusing. So, I would change

    if (!node_degree.count(node))
   

to

    if (node_degree.count(node) == 0)

5. If you read std::unordered_map::operator[], you'll see that it inserts a default constructed element if it doesn't exist. So, add_node_to_node_degree_map can be simplified to:

    ++node_degree[node];
   

Which also means that you don't need a function for it.

6. Every binary arithmetic operator (let's call one %%) can be rewritten if it has the form

    num = num %% a; // 'a' is another number
   

Using %%=:

    num %%= a;

Example, node_degree[node] = node_degree[node] + 1; can become node_degree[node] += 1;, or in this case, even ++node_degree[node]; because you're only adding one.

7. Mark functions that do not throw as noexcept to help the compiler optimize (if you compile without exceptions, ignore this.)

8. Your naming is a bit too specific, and as a result, they are long, especially function names. Try to find shorter names, but not too short :)

9. I can only see one printf, so I'm not sure on this one:

• If you always use printf, even if you are outputting an integer, then don't, because you are using the C function, which is not guaranteed to be included. In this case, #include <cstdio> and change it to std::printf.

• If you removed it because you know that ADL will find printf anyways in std in this case, good job :) Still, you need to #include <cstdio>.

10. Use more range-based for loops:

    for (const auto &node : node_degree)
        node_degree_vect.push_back(std::make_pair(node.first, node.second));
    

11. You are inconsistent with braces, but only in one case. The one replaced above is the only one with opening braces being on a separate line.

12. int is not guaranteed to cover the whole range of std::size_t, which is returned by most .size() calls. So, you'll need to use std::size_t instead of int in loops:

    for (std::size_t i = 0; i < node_degree_vect.size() / 2; ++i) {
        high_occurrences.push_back(node_degree_vect[i].first);
    }
    

13. Prefer pre-increment to post-increment. Even though for ints this is negligible and the compiler will optimize the temporary away, this might not be the case for other heavier types (like iterators.)

14. Use auto.

    [](const std::pair<int, int> &left, const std::pair<int, int> &right) {
        return left.second > right.second;
    }
    

can become

    [](const auto &left, const auto &right) {
        return left.second > right.second;
    }

15. I think you didn't write this, but if you did: std::ifstream's destructor closes the file, so you don't need to at the end.

16. A function returning void and taking a reference to a type is not very nice. Consider returning the variable instead of taking it by reference. In this case, you can initialize coordinates in 1 line instead of 2.

17. Print a trailing new line please.

18. select_coordinates_highest_occurrence doesn't modify coordinates. So please mark it const to prevent any accidental modifications.

19. You don't need return 0; for main, you can safely remove it.