Skip to main content
Code Review

Return to Answer

added 1263 characters in body
Source Link
mdfst13
mdfst13
  • 22.4k
  • 6
  • 34
  • 70

using namespace std

std::vector vs. std::map

You want a type indexed by integers starting with 0 and increasing to an arbitrarily large amount in sequence, as that is what Fibonacci is is a sequence. So why use a std::map, which allows for sparse, out of sequence results? Just use

    std::vector<std::uint128_t>& m = __fib_result_vector;__fib_results;

Changing the name to __fib_results won't affect performance, but it saves having to rename the variable if you change types.

It will use less memory because a map has to leave room to add new elements between other elements in an arbitrary order. Which you don't need. And a map has to store the keys as well as the values. A vector uses position to do that, so the fourth is always index 3.

Headers

There's an argument that you should only do includes like this in header files if needed in the header file itself. That's not true in this case, as the header file only uses primitives. So you could include vector or map in fibonacci.cpp directly. The header file only needs to include the function prototype.

Working example

#include <vector>
#include <stdint.h>

std::vector<std::uint64_t> initializeFibonacci() {
    std::vector<std::uint64_t> m;

    m.push_back(0);
    m.push_back(1);

    return m;
}

std::vector<std::uint64_t> __fib_results = initializeFibonacci();

std::uint64_t fibonacci(int seq) {
    std::vector<std::uint64_t>& m = __fib_results;

    while (m.size() <= seq) {
        auto i = m.size();
        m.push_back(m[i-1] + m[i-2]);
    }

    return m[seq];
}

The compiler that I used for testing did not seem to have uint128_t, so I substituted uint64_t. I don't see any reason why uint128_t wouldn't work if available, but this is what I actually tested.

Instead of recursively working down to the last known value, this works up from it. This saves doing any recursive calls, so it doesn't have to worry about overloading the stack. Also, this makes it work more easily with push_back.

You want a type indexed by integers starting with 0 and increasing to an arbitrarily large amount in sequence, as that is what Fibonacci is is a sequence. So why use a std::map, which allows for sparse, out of sequence results? Just use

    std::vector<std::uint128_t>& m = __fib_result_vector;

It will use less memory because a map has to leave room to add new elements between other elements in an arbitrary order. Which you don't need. And a map has to store the keys as well as the values. A vector uses position to do that, so the fourth is always index 3.

There's an argument that you should only do includes like this in header files if needed in the header file itself. That's not true in this case, as the header file only uses primitives. So you could include vector or map in fibonacci.cpp directly. The header file only needs to include the function prototype.

using namespace std

std::vector vs. std::map

You want a type indexed by integers starting with 0 and increasing to an arbitrarily large amount in sequence, as what Fibonacci is is a sequence. So why use a std::map, which allows for sparse, out of sequence results? Just use

    std::vector<std::uint128_t>& m = __fib_results;

Changing the name to __fib_results won't affect performance, but it saves having to rename the variable if you change types.

It will use less memory because a map has to leave room to add new elements between other elements in an arbitrary order. Which you don't need. And a map has to store the keys as well as the values. A vector uses position to do that, so the fourth is always index 3.

Headers

There's an argument that you should only do includes like this in header files if needed in the header file itself. That's not true in this case, as the header file only uses primitives. So you could include vector or map in fibonacci.cpp directly. The header file only needs to include the function prototype.

Working example

#include <vector>
#include <stdint.h>

std::vector<std::uint64_t> initializeFibonacci() {
    std::vector<std::uint64_t> m;

    m.push_back(0);
    m.push_back(1);

    return m;
}

std::vector<std::uint64_t> __fib_results = initializeFibonacci();

std::uint64_t fibonacci(int seq) {
    std::vector<std::uint64_t>& m = __fib_results;

    while (m.size() <= seq) {
        auto i = m.size();
        m.push_back(m[i-1] + m[i-2]);
    }

    return m[seq];
}

The compiler that I used for testing did not seem to have uint128_t, so I substituted uint64_t. I don't see any reason why uint128_t wouldn't work if available, but this is what I actually tested.

Instead of recursively working down to the last known value, this works up from it. This saves doing any recursive calls, so it doesn't have to worry about overloading the stack. Also, this makes it work more easily with push_back.

Source Link
mdfst13
mdfst13
  • 22.4k
  • 6
  • 34
  • 70

    using namespace std;

Count the number of characters you use with this (twenty) and compare to the number of characters you save by having it (five). Wouldn't it be better to just say std::map instead?

Even in fib_cpp.cpp, you only save fifteen characters for a net increase of five.

    map<int, unsigned long long int>& m = __fib_result_map;

You want a type indexed by integers starting with 0 and increasing to an arbitrarily large amount in sequence, as that is what Fibonacci is is a sequence. So why use a std::map, which allows for sparse, out of sequence results? Just use

    std::vector<std::uint128_t>& m = __fib_result_vector;

It will use less memory because a map has to leave room to add new elements between other elements in an arbitrary order. Which you don't need. And a map has to store the keys as well as the values. A vector uses position to do that, so the fourth is always index 3.

It will be faster, because integer indexes are more efficient than hash indexes.

The only way that the map might be as fast as a vector is if optimization turns it into a vector.

    if(m[seq] == 0 && seq != 0) {

Then this becomes

    if (m.size() <= seq) {

You don't even need a hash calculation for this.

#include <iostream>

#include <map>
#include <vector>
#include <string>
#include <algorithm>

The only one of these that fibonacci.cpp actually uses that I can see is map (although I think that you should use vector instead). You use iostream in fib_cpp.cpp, but not in fibonacci.cpp.

There's an argument that you should only do includes like this in header files if needed in the header file itself. That's not true in this case, as the header file only uses primitives. So you could include vector or map in fibonacci.cpp directly. The header file only needs to include the function prototype.