백준 풀다가 갑자기 만든 피보나치 클래스

#include <iostream>
#include <ostream>
#include <array>

template < std::size_t length = 45 >
class Fibonacci 
{
private:
	using ulong = unsigned long;

	std::array< ulong, length > series { 0, 1, 1, };

public:
	Fibonacci() = default;

	ulong get(const std::size_t& ind)
	{
		if ( ind == 0 || series[ind] ) return series[ind];
		
		return series[ind] = get( ind - 1 ) + get( ind - 2 );
	}

	constexpr std::size_t size() const
	{
		return length;
	}

	friend std::ostream& operator<<(std::ostream& lhs, Fibonacci rhs)
  	{
		rhs.get( rhs.size() );
		
		lhs << "< ";

		for ( const auto& i : rhs.series ) lhs << i << " ";

		lhs << ">";

		return lhs;
 	}
};

int main()
{
	Fibonacci< 20 > fibo;
	
	std::cout << "length : " << fibo.size() << "\n";
	std::cout << fibo;

	return 0;
}

그냥 만들고 싶었어요 :sweat_smile:

5 Likes

근데 왜 하이라이팅 제대로 적용되지 않은거 같죠?? ㅠㅠ

간단히 리뷰하자면,

  1. 무슨 목적을 가진 코드인지 알기 힘듭니다. 템플릿 인자로 크기를 받는다면 컴파일 타임에 수열을 모두 계산할 수 있을텐데 그것도 아니고, 어차피 런타임에 계산할 거라면 std::vector 등의 동적 배열을 사용해 더 유연하게 사용할 수도 있었을텐데 그것도 아닙니다.

  2. 구현이 비효율적입니다. get 함수는 반복문을 사용해 작성하는 것이 나아 보이고, 출력 함수도 레퍼런스를 사용해 더 효율적으로 작동하게 고칠 수 있습니다.

  3. get의 인자로 왜 레퍼런스만 받게 했는지 모르겠습니다.

  4. 기본 생성자만 default로 해놓을 이유가 없습니다.

  5. using ulong = ...보다는, 값의 타입을 템플릿 인자로 받는게 좋아 보입니다.

  6. 해도 되고 안해도 되는 사항이지만, 분할정복을 사용해 O(log N)의 시간복잡도에 피보나치 수열의 N번째 항을 계산할 수 있습니다. 만들어 보시는걸 추천합니다. 참고:

4 Likes

constexpr 예제는 피보나치보다 힙하게 애커만으로 합시다

#include <iostream>
#include <chrono>

namespace crn = std::chrono;

size_t ackermann_brutal(size_t m, size_t n) {
    if (m == 0) return n + 1;
    if (n == 0) return ackermann_brutal(m - 1, 1);
    return ackermann_brutal(m - 1, ackermann_brutal(m, n - 1));
}

constexpr size_t ackermann_smart(size_t m, size_t n) {
    return !m ? n + 1
    : !n ? ackermann_smart(m - 1, 1)
    : ackermann_smart(m - 1, ackermann_smart(m, n - 1));
}

int main() {
    auto begin_time = crn::steady_clock::now();
    std::cout << ackermann_brutal(3, 10) << '\n';
    auto end_time = crn::steady_clock::now();
    std::cout << "Brutal: " << (crn::duration_cast<crn::milliseconds>(end_time - begin_time)).count() << "ms\n";
    begin_time = crn::steady_clock::now();
    std::cout << ackermann_smart(3, 10) << '\n';
    end_time = crn::steady_clock::now();
    std::cout << "Smart: " << (crn::duration_cast<crn::milliseconds>(end_time - begin_time)).count() << "ms\n";
    return 0;
}
8189
Brutal: 56ms
8189
Smart: 0ms
4 Likes

우와 constexpr 멋져요 ㅎㅎㅎ

1 Like

http://stackoverflow.com/questions/908256 TMP는 요런거부터 시작하믄 될 것 같다는 생각이 드네용

1 Like

C++14부터는 ?: 아니어도 constexpr 할 수 있읍니다.

constexpr size_t ackermann_smart(size_t m, size_t n) {
    if (m == 0) return n + 1;
    if (n == 0) return ackermann_smart(m - 1, 1);
    return ackermann_smart(m - 1, ackermann_smart(m, n - 1));
}

Compiler Explorer 요기서 확인해보세용

2 Likes

https://en.cppreference.com/w/cpp/language/constexpr

2 Likes

오 예술이네유 ㅎㅎㅎㅎ