C ++ 11: массив времени компиляции с логарифмической оценкой

17

Один из способов реализации массива C ++ 11, который имеет свои элементы, инициализированные функцией их индекса, рассчитанные компилятором, и результаты, хранящиеся в разделе данных (.rodata) изображения приложения, - это использование шаблонов, частичная специализация и constexpr следующим образом:

#include <iostream>
#include <array>
using namespace std;

constexpr int N = 1000000;
constexpr int f(int x) { return x*2; }

typedef array<int, N> A;

template<int... i> constexpr A fs() { return A{{ f(i)... }}; }

template<int...> struct S;

template<int... i> struct S<0,i...>
{ static constexpr A gs() { return fs<0,i...>(); } };

template<int i, int... j> struct S<i,j...>
{ static constexpr A gs() { return S<i-1,i,j...>::gs(); } };

constexpr auto X = S<N-1>::gs();

int main()
{
        cout << X[3] << endl;
}

Это не работает при больших значениях N:

error: constexpr evaluation depth exceeds maximum of 512 

Это из-за стиля хвостового рекурсивного шаблона, который имеет линейную глубину в терминах N.

Есть ли способ сделать это так, чтобы глубина оценки была логарифмической с точки зрения N, а не линейной? (и, следовательно, позволит избежать предела глубины по умолчанию)

    
задан Andrew Tomazos 25.10.2012 в 17:46
источник
  • Связанный: stackoverflow.com/questions/12108390/... –  Andrew Tomazos 25.10.2012 в 17:47
  • Связанный: stackoverflow.com/questions/13102996/... –  Andrew Tomazos 27.10.2012 в 20:37

3 ответа

22

Если то, что вы используете в коде, является странной формой трюка индексов, вот реализация, которая имеет O(log N) экземпляров:

// using aliases for cleaner syntax
template<class T> using Invoke = typename T::type;

template<unsigned...> struct seq{ using type = seq; };

template<class S1, class S2> struct concat;

template<unsigned... I1, unsigned... I2>
struct concat<seq<I1...>, seq<I2...>>
  : seq<I1..., (sizeof...(I1)+I2)...>{};

template<class S1, class S2>
using Concat = Invoke<concat<S1, S2>>;

template<unsigned N> struct gen_seq;
template<unsigned N> using GenSeq = Invoke<gen_seq<N>>;

template<unsigned N>
struct gen_seq : Concat<GenSeq<N/2>, GenSeq<N - N/2>>{};

template<> struct gen_seq<0> : seq<>{};
template<> struct gen_seq<1> : seq<0>{};

// example

template<unsigned... Is>
void f(seq<Is...>);

int main(){
  f(gen_seq<6>());
}

Пример в реальном времени.

    
ответ дан Xeo 25.10.2012 в 18:27
источник
  • Чтобы дать перспективу, с моим конкретным компилятором и машиной я могу скомпилировать программу OP до N = 510, прежде чем нажимать ограничение на создание шаблона. С помощью этой техники я могу увеличить N до 12000, а ограничивающий фактор становится памятью - я видел, что машина способна обрабатывать N около 25000. Очевидно, что это далеко от 1000000, но чистое улучшение на несколько порядков , –  Luc Danton 26.10.2012 в 22:26
  • @LucDanton: FYI получается, что GCC имеет проблему с большим N, однако у меня есть отчет о том, что clang / llvm не имеет с ним никаких проблем (например, clang может обрабатывать N = 10 ^ 6). Не знаю о msvc. –  Andrew Tomazos 29.12.2012 в 06:24
  • Использование g ++ - 4.8 с 18 ГБ или ОЗУ Я получил от N до 75000 до исчерпания памяти –  SirGuy 25.09.2013 в 20:36
  • Использование clang 3.3 У меня N до 1'000'000 gcc имеет некоторые проблемы с производительностью sizeof ... (I). поэтому, если вы будете использовать gcc, замените sizeof ... (I) на конкретный номер. –  Khurshid 14.11.2013 в 09:49
4

В c ++ 14 с общей функцией constexpression не требуется никакая последовательность, make_sequence

static constexpr int f(int i) noexcept { return i * 2; }

template< int N, typename F >
static constexpr std::array<int,N> generate_array( F fo ) noexcept
{
     std::array< int, N > result{}; // init with zero
     int i = 0; 
     for( auto& x : result) x = fo(++i);

     return result;
}

// test
constexpr auto arr = generate_array<10>( f );

Только одна проблема, нет компилятора, который может скомпилировать его:)

    
ответ дан Khurshid 18.11.2013 в 09:01
источник
  • Фактически clang trunk в режиме C ++ 1y - это функция, полная против последнего черновика. –  Andrew Tomazos 19.11.2013 в 09:53
1

Единственным хвостовым рекурсивным шаблоном, вызывающим глубину создания линейного шаблона, является построение списка целых чисел в списке параметров шаблона S .

Это можно сделать с помощью логарифмической глубины инкрементации, как вы предлагаете:

template <int ... Ints> struct seq;

template <int Start, int End> 
struct range
{
  typedef concat_seq<range<Start, Start+(End-Start)/2>::type, range<Start+(End-Start)/2, End>::type>::type type;
};

template<int Singleton>
struct range<Singleton, Singleton+1>
{
  typedef seq<Singleton> type;
};

template <int NoSingleton>
struct range<NoSinleton, NoSingleton>
{
  typedef seq<> type;
};

Добавьте кучу typename s, где это необходимо, реализуйте concat_seq (легко), извлеките список аргументов для fs из range<0, N>::type и там вы идете.

    
ответ дан jpalecek 25.10.2012 в 18:21
источник