3. campers TMP-Aufgabe(n): 7

campers TMP-Aufgabe(n): 7

  • S

    camper schrieb:

    Mit clang wird das auch nichts werden. Das durch eine Packexpansion erzeugte Komma ist niemals ein Kommaoperator.

    Verdammt...!

    0
  • C
    Mod

    Kleiner Tip: Templateargumentlisten sind nicht die einzigen Stellen, wo Packexpansionen auftreten können (14.5.3/4)

    0
  • S

    Spielst du auf sowas an?

    #include <type_traits>

template<typename base, int val>
struct AccTag
{
    static int constexpr value = val * std::is_base_of<AccTag<base, val>, base>::value + AccTag<base, val-1>::value;
};

template<typename base>
struct AccTag<base, 0> : std::integral_constant<int, 0> {};

template<int ... args>
struct accumulate : AccTag<accumulate<args...>, args>... 
// Trick: Da AccTag von einem Template-Parameter abhängt, wird seine Definition erst wenn sie gebraucht wird angesehen - wenn accumulate schon *vollständig definiert* ist.
{
    static int constexpr value = AccTag<accumulate<args...>, 10>::value; // Hmm. Das muss schöner gehen, ich mach mich ran.
};

    Was an dieser Lösung schön ist: Hier wird nix aufgeteilt, wie du wolltest. 🙂
    Das Blöde: Die Instantiierungstiefe überschreitet ggf. ihr Maximum. Doof. 😞

    P.S.: Empfehle mir mal das beste Linux-Derivat für GCC. Einfach fürs programmieren mit GCC. Gentoo? (Edit: Naja, Gentoo wäre mir vielleicht zuviel. Das ist schon extrem)

    0
  • E

    Irgendeine Distro die Bleeding Edge Pakete anbietet wenn es dir speziell um die neuesten Versionen geht. Fedora ist einsteigerfreundlicch und du kannst meisten relativ neuen Kram haben. Obwohl ich mit Fedora 17 immer noch den 4.7.2 habe, gab wohl keinen Grund umzustellen...

    0
  • S

    Ok, das ist Blödsinn. Da wäre

    template<int ... args>
struct index_list
{
    static constexpr int arr[]{args...};
};

template<typename base, int index>
struct AccTag
{
    static int constexpr value = base::arr[index] + AccTag<base, index-1>::value;
};

template<typename base>
struct AccTag<base, -1> : std::integral_constant<int, 0> {};

template<int ... args>
struct accumulate : std::integral_constant<int, AccTag<index_list<args...>, sizeof...(args)-1>::value> {};

    Schon direkter.

    0
  • C
    Mod

    Sone schrieb:

    Ok, das ist Blödsinn. Da wäre

    template<int ... args>
struct index_list
{
    static constexpr int arr[]{args...};
};

template<typename base, int index>
struct AccTag
{
    static int constexpr value = base::arr[index] + AccTag<base, index-1>::value;
};

template<typename base>
struct AccTag<base, -1> : std::integral_constant<int, 0> {};

template<int ... args>
struct accumulate : std::integral_constant<int, AccTag<index_list<args...>, sizeof...(args)-1>::value> {};

    Schon direkter.

    Das ist aber auch nur normale Rekursion etwas umständlicher geschrieben. Es wird immer noch die Liste bei jedem Schritt mitgechleppt.

    #include <type_traits>

template<int ... args>
struct index_list
{
    static constexpr int arr[]{args...};
    using type = index_list;
};

template<typename base, int index>
struct AccTag
{
    static int constexpr value = base::arr[index] + AccTag<base, index-1>::value;
};

template<typename base>
struct AccTag<base, -1> : std::integral_constant<int, 0> {};

template<int ... args>
struct accumulate : std::integral_constant<int, AccTag<index_list<args...>, 
sizeof...(args)-1>::value> {};

template <typename T, typename U> struct concat_list;
template <int... i, int... j>
struct concat_list<index_list<i...>,index_list<j...>>
: index_list<i..., (sizeof...(i)+i)..., (2*sizeof...(i)+j)...> {};

template <int N> struct make_index_list
: concat_list<typename make_index_list<N/2>::type, typename make_index_list<N%2>::type> {};
template <> struct make_index_list<1> : index_list<0> {};
template <> struct make_index_list<0> : index_list<> {};

template <typename T> struct acc;
template <int... i> struct acc<index_list<i...>> : accumulate<i...> {};

#include <iostream>

int main()
{
    using list = typename make_index_list<LENGTH>::type;
    std::cout << sizeof(list) << '\t';
    using result = acc<list>;
    std::cout << result::value << '\t';
}

    Mal schnell getestet mit

    for ((x=100;x<20000;x+=x/2)) do y=`/usr/bin/time -f "utime=%U res=%M" 2>&1 g++-4.8.1 -std=c++0x test.cpp -DLENGTH=$x -ftemplate-depth=20000`; echo X=$x $y ; done

    ergibt ohne die letzten beiden Zeilen in main (res in kB, auf i7 2640m)

    X=100 utime=0.18 res=136304
X=150 utime=0.18 res=137136
X=225 utime=0.19 res=137408
X=337 utime=0.19 res=139360
X=505 utime=0.19 res=141200
X=757 utime=0.21 res=147248
X=1135 utime=0.21 res=166256
X=1702 utime=0.25 res=179472
X=2553 utime=0.34 res=235424
X=3829 utime=0.52 res=314400
X=5743 utime=0.92 res=534800
X=8614 utime=1.73 res=1034864
X=12921 utime=3.60 res=2025968
X=19381 utime=7.49 res=4211920

    und mit accumulate

    X=100 utime=0.19 res=140400
X=150 utime=0.20 res=144560
X=225 utime=0.21 res=149936
X=337 utime=0.23 res=163872
X=505 utime=0.29 res=186240
X=757 utime=0.41 res=251088
X=1135 utime=0.68 res=358032
X=1702 utime=1.30 res=576096
X=2553 utime=2.61 res=1117840
X=3829 utime=6.07 res=2158192
X=5743 utime=12.86 res=4598640
X=8614 utime=29.15 res=9429120
X=12921 utime=71.27 res=22378096

    Das ist klar exponentielles Wachstum, was ich nicht haben möchte.
    Mit clang

    X=100 utime=0.21 res=103904
X=150 utime=0.22 res=106256
X=225 utime=0.21 res=109744
X=337 utime=0.23 res=115088
X=505 utime=0.23 res=122848
X=757 utime=0.25 res=134752

    clang steigt bei einer Tiefe über 1000 mit einem Segfault aus, aus den ermittelten Zahlen ist leider keine Tendenz klar erkennbar.

    Ich bin kein Linux-Experte, habe ausser Gentoo nur vor Jahren mal wenige andere angetestet.

    0
  • S

    Ich sehe. Wie ist übrigens

    template<int ... args>
struct accumulate : std::integral_constant<int, boost::mpl::plus<boost::mpl::int_<args>...>::value> {};

    ?

    Btw: schöne make_indices -Implementation.

    0
  • C
    Mod

    Sone schrieb:

    Ich sehe. Wie ist übrigens

    template<int ... args>
struct accumulate : std::integral_constant<int, boost::mpl::plus<boost::mpl::int_<args>...>::value> {};

    ?

    100x schlechter. mpl verwendet ja keine varidic Templates.

    #define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS 1
#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY LENGTH

#include <type_traits>
#include <boost/mpl/plus.hpp>
#include <boost/mpl/int.hpp>

template<int ... args>
struct index_list
{
    static constexpr int arr[]{args...};
    using type = index_list;
};

template<int ... args>
struct accumulate : std::integral_constant<int, boost::mpl::plus<boost::mpl::int_<args>...>::value> {};	

template <typename T, typename U> struct concat_list;
template <int... i, int... j>
struct concat_list<index_list<i...>,index_list<j...>>
: index_list<i..., (sizeof...(i)+i)..., (2*sizeof...(i)+j)...> {};

template <int N> struct make_index_list
: concat_list<typename make_index_list<N/2>::type, typename make_index_list<N%2>::type> {};
template <> struct make_index_list<1> : index_list<0> {};
template <> struct make_index_list<0> : index_list<> {};

template <typename T> struct acc;
template <int... i> struct acc<index_list<i...>> : accumulate<i...> {};

#include <iostream>

int main()
{
    using list = typename make_index_list<LENGTH>::type;
    std::cout << sizeof(list) << '\t';
    using result = acc<list>;
    std::cout << result::value << '\t';
}

    ergibt bei mir mit gcc 4.8.1

    X=10 utime=0.36 res=234272
X=15 utime=0.46 res=321376
X=22 utime=0.63 res=388784
X=33 utime=1.02 res=535216
X=49 utime=1.88 res=1112064
X=73 utime=3.79 res=2911728
X=109 utime=8.07 res=4516576
X=163 utime=18.18 res=13134112
X=244 utime=44.89 res=22324720
    0
  • S

    Ich verstehe immer noch nicht. Du willst also, dass ich eine Schleife auf eine pack-expansion "reduziere"?

    0
  • S

    camper schrieb:

    Es wird immer noch die Liste bei jedem Schritt mitgechleppt.

    Das ist nicht das Problem.

    template<int ... args>
struct accumulate
{
    static constexpr int arr[]{args...};

    static constexpr int compute_acc( int start_index )
    {
        return (start_index == -1 ? 0 : compute_acc(start_index-1) + arr[start_index] );
    }

    static constexpr auto value = compute_acc(sizeof...(args)-1);
};

    Überhaupt, irgendwo muss es ja die Rekursion geben - das meintest du selbst. Und da ist die Rekursion.

    0
  • C
    Mod

    Sone schrieb:

    Überhaupt, irgendwo muss es ja die Rekursion geben - das meintest du selbst. Und da ist die Rekursion.

    Um die Indexliste zu erzeugen.

    template<int ... args>
struct index_list
{
    static constexpr int arr[]{args...};
    static constexpr int size = sizeof...(args);
    using type = index_list;
};

template <typename T, typename U> struct concat_list;
template <int... i, int... j>
struct concat_list<index_list<i...>,index_list<j...>>
: index_list<i..., (sizeof...(i)+i)..., (2*sizeof...(i)+j)...> {};

template <int N> struct make_index_list
: concat_list<typename make_index_list<N/2>::type, typename make_index_list<N%2>::type> {};
template <> struct make_index_list<1> : index_list<0> {};
template <> struct make_index_list<0> : index_list<> {};

template <int i> struct rack { int v; };

template <typename T, typename = typename make_index_list<T::size>::type> struct acc;

template <int... i, int... j> struct acc<index_list<i...>, index_list<j...>>
: rack<-1>, rack<j>...
{
    constexpr acc() : rack<-1>{0}, rack<j>{rack<j-1>::v+i}... {}
    static const int value;
};

template <int... i, int... j>
const int acc<index_list<i...>, index_list<j...>>::value = acc().rack<sizeof...(j)-1>::v;
    0
  • S
     

    rack<-1>{0}, rack<j>{rack<j-1>::v+i}...

    Natürlich...
    Ja, das ist schön. Damit kann man alles schöner schreiben, auch partial_sum und wahrscheinlich auch multiply...

    Und welche ist jetzt schneller?

    Edit: Das hätte ich doch sehen müssen...:

    template <typename V> struct fib; 
template <typename T, T... i> struct fib<value_list<T, i...>> 
    : tagged_value<0,T>, tagged_value<1,T>, tagged_value<j+2, T>... 
{ 
    constexpr partial_sum() : tagged_value<0,T>(0), tagged_value<1,T>(1), tagged_value<j+2, T>( tagged_value<j,T>::v + tagged_value<j+1,T>::v )... {} 
};

    Mit dem Trick lässt sich alles schöner schreiben.

    0
  • C
    Mod

    Sone schrieb:

    Und welche ist jetzt schneller?

    clang steigt bei großer constexpr-Rekursionstiefe aus
    Mit g++ 4.8.1 erhalte cih für die constexpr-Variante (jweils wieder mit und ohne Instantiierung von accumulate, die Differenz der Werte ist von Interesse).

    X=100 utime=0.19 res=137856 utime=0.18 res=136272
X=150 utime=0.18 res=140576 utime=0.18 res=136800
X=225 utime=0.19 res=142240 utime=0.18 res=137136
X=337 utime=0.19 res=152496 utime=0.17 res=139168
X=505 utime=0.20 res=160896 utime=0.18 res=141216
X=757 utime=0.21 res=188928 utime=0.19 res=147392
X=1135 utime=0.25 res=265072 utime=0.21 res=166000
X=1702 utime=0.31 res=381856 utime=0.25 res=179472
X=2553 utime=0.42 res=661360 utime=0.33 res=235328
X=3829 utime=0.71 res=1253536 utime=0.49 res=314448
X=5743 utime=1.28 res=2683328 utime=0.87 res=534880
X=8614 utime=2.57 res=5789856 utime=1.67 res=1034896
X=12921 utime=5.42 res=12672320 utime=3.46 res=2026080

    Mein Code:

    X=100 utime=0.19 res=146224 utime=0.19 res=136416
X=150 utime=0.21 res=151648 utime=0.18 res=137024
X=225 utime=0.23 res=158432 utime=0.19 res=137440
X=337 utime=0.26 res=170960 utime=0.19 res=139360
X=505 utime=0.30 res=186384 utime=0.19 res=141632
X=757 utime=0.39 res=217072 utime=0.20 res=147888
X=1135 utime=0.59 res=269824 utime=0.22 res=166928
X=1702 utime=1.02 res=331872 utime=0.25 res=180640
X=2553 utime=1.85 res=464032 utime=0.33 res=236896
X=3829 utime=3.73 res=654192 utime=0.49 res=316448
X=5743 utime=7.71 res=1068160 utime=0.86 res=538016
X=8614 utime=16.63 res=1723568 utime=1.67 res=1038784
X=12921 utime=36.29 res=3103984 utime=3.45 res=2031216

    Schön linearer Speicherbedarf, dafür unterirdische Geschwindgikeit.

    Mal noch zum Vergleich

    template <typename T,
          typename = typename make_index_list<T::size/2>::type,
          typename = typename make_index_list<T::size%2>::type> struct acc;

template <typename T, int... j, int... k>
struct acc<T, index_list<j...>,index_list<k...>>
: std::integral_constant<int, acc<index_list<T::arr[j]...>>::value+
                              acc<index_list<T::arr[sizeof...(j)+j]...>>::value+
                              acc<index_list<T::arr[2*sizeof...(j)+k]...>>::value>
{};

template <>
struct acc<index_list<>,index_list<>,index_list<>> : std::integral_constant<int,0> {};
template <int i>
struct acc<index_list<i>,index_list<>,index_list<0>> : std::integral_constant<int,i> {};

    mit gcc 4.8.1

    X=100 utime=0.22 res=158560 utime=0.19 res=136432
X=150 utime=0.24 res=181152 utime=0.18 res=137120
X=225 utime=0.27 res=199040 utime=0.18 res=137584
X=337 utime=0.33 res=275280 utime=0.19 res=139648
X=505 utime=0.40 res=340256 utime=0.19 res=141584
X=757 utime=0.60 res=577792 utime=0.21 res=147968
X=1135 utime=1.01 res=1143088 utime=0.22 res=166976
X=1702 utime=1.49 res=1855312 utime=0.26 res=180672
X=2553 utime=2.76 res=3846768 utime=0.33 res=236960
X=3829 utime=4.84 res=7397792 utime=0.56 res=316496
X=5743 utime=9.71 res=16665488 utime=0.88 res=538240

    also schlechter als die anderen Varianten, wobei sich das sicher etwas verbessern ließe, wenn ein größerer Faktor als 2 verwendet wird.

    Mein Code+clang

    X=100 utime=0.21 res=102400 utime=0.21 res=99744
X=150 utime=0.22 res=103904 utime=0.21 res=100000
X=225 utime=0.23 res=106128 utime=0.21 res=100256
X=337 utime=0.25 res=109456 utime=0.20 res=100800
X=505 utime=0.30 res=114416 utime=0.20 res=101488
X=757 utime=0.37 res=122064 utime=0.21 res=102560
X=1135 utime=0.60 res=133344 utime=0.22 res=104256
X=1702 utime=1.11 res=150368 utime=0.22 res=106480
X=2553 utime=2.12 res=175776 utime=0.22 res=110112
X=3829 utime=5.27 res=214336 utime=0.23 res=115200
X=5743 utime=13.16 res=272384 utime=0.25 res=123888
X=8614 utime=35.95 res=360032 utime=0.27 res=135584
X=12921 utime=87.30 res=491056 utime=0.29 res=155376
X=19381 utime=193.86 res=685744 utime=0.33 res=184624
X=29071 utime=456.63 res=982000 utime=0.40 res=220384
X=43606 utime=1012.73 res=1421840 utime=0.47 res=290624
X=65409 utime=2432.28 res=2085632 utime=0.64 res=384944
X=98113 utime=5285.76 res=3058112 utime=0.82 res=520656

    Die letzte Variante mit clang

    X=100 utime=0.24 res=107776 utime=0.21 res=99792
X=150 utime=0.26 res=113488 utime=0.20 res=100032
X=225 utime=0.28 res=118176 utime=0.20 res=100336
X=337 utime=0.34 res=130624 utime=0.20 res=100816
X=505 utime=0.37 res=141056 utime=0.21 res=101488
X=757 utime=0.50 res=168128 utime=0.21 res=102592
X=1135 utime=0.71 res=216352 utime=0.21 res=104272
X=1702 utime=0.91 res=255440 utime=0.22 res=106528
X=2553 utime=1.45 res=357184 utime=0.22 res=110176
X=3829 utime=2.10 res=448848 utime=0.22 res=115200
X=5743 utime=3.75 res=675040 utime=0.24 res=124176
X=8614 utime=7.12 res=1074704 utime=0.26 res=136624
X=12921 utime=12.10 res=1403328 utime=0.29 res=155696
X=19381 utime=24.27 res=2250448 utime=0.32 res=184448
X=29071 utime=47.27 res=3022464 utime=0.39 res=221776
X=43606 utime=103.71 res=4885888 utime=0.48 res=291088
X=65409 utime=225.23 res=6634432 utime=0.65 res=386064
X=98113 segfault
    0
  • S

    Ja, diese Aufteil-Variante hätte ich auch noch vorgeschlagen.

    Schön linearer Speicherbedarf, dafür unterirdische Geschwindgikeit.

    Ja, aber wo denkst du überschneiden sich die Geschwindigkeiten?

    Im Übrigen stelle ich in Frage, ob diese - obgleich schöne Variante - überhaupt richtig ist. value ist nämlich nicht constexpr .
    Ich habe dieselbe Form von Lösung schon gefunden, sie aber abgetan, weil sie ja nicht constexpr ist...

    template<int ... args>
struct index_list
{
    static constexpr int size = sizeof...(args);
    using type = index_list;
};

template <typename T, typename U> struct concat_list;
template <int... i, int... j>
struct concat_list<index_list<i...>,index_list<j...>>
: index_list<i..., (sizeof...(i)+i)..., (2*sizeof...(i)+j)...> {};

template <int N> struct make_index_list
: concat_list<typename make_index_list<N/2>::type, typename make_index_list<N%2>::type> {};
template <> struct make_index_list<1> : index_list<0> {};
template <> struct make_index_list<0> : index_list<> {};

template<typename T, typename =  typename make_index_list<T::size>::type> // Der Trick mit dem default-Argument ist auch gut.
struct accumulate;
template<int ... args, int ...ind>
struct accumulate<index_list<args...>, index_list<ind...>>
{
    static const int arr[];
    static const int value;
};

template<int ... args, int ... ind>
const int accumulate<index_list<args...>, index_list<ind...>>::arr[]{ 0, (arr[ind] + args)... }; // Bei initializer-lists ist die Auswertungsreihenfolge definiert.
template<int ... args, int ... ind>
const int accumulate<index_list<args...>, index_list<ind...>>::value = arr[sizeof...(args)]; // ... und value ist nicht constexpr.
    0
  • C
    Mod

    Ein constexpr kann problemlos hinzugefügt werden

    template <int... i, int... j>
constexpr const int acc<index_list<i...>, index_list<j...>>::value = acc().rack<sizeof...(j)-1>::v;

    So oder so kann v dann in konstanten Ausdrücken verwendet werden.
    Mit dem Array funktioniert das nicht (wobei ich den Standard an dieser Stelle für unklar halte).

    0
  • S
     

    template <int... i, int... j> 
constexpr const int acc<index_list<i...>, index_list<j...>>::value

    Was ist das? oO Wie soll das gehen?

    Edit: Das geht doch überhaupt nicht!
    Aber du hast Recht, v ist constexpr.

    0
  • S

    Sone schrieb:

    Aber du hast Recht, v ist constexpr .

    Nö, auch das nicht!

    note: 'constexpr acc<index_list<i ...>, index_list<j ...> >::acc() [with int ...i = {1, 2, 3}; int ...j = {0, 1, 2}]' is not usable as a constexpr function because:|

    (Es folgt nichts)
    Kann auch ein Bug sein. Ist der GCC 4.8.1...

    Nach GCC 4.8.1 jedenfalls ist deine Lösung nicht statischer als meine. Auch meine lässt sich als Array-Bound verwenden, nicht aber als initializer für eine constexpr -Variable.

    0
  • C
    Mod

    Ich betrachte das mal als Bug (von gcc).
    Der entscheidene Test sollte sein, ob nach der Definition value als konstanter Ausdruck verwendet werden kann.

    constexpr int foo = accumulate<list>::value;

    extern const int foo;
constexpr int foo = 42;

    ist legal (und sowieso die einzige Möglichkeit, da constexpr immer einen Initialisierer benötigt, liese sich eine solche Variable sonst gar nicht nur deklarieren).

    0
  • S

    Die Map:

    enum class lookup_mode { FirstSec, SecFirst };

template <lookup_mode lk, int, typename T, typename, typename = typename make_index_list<T::size>::type>
struct lookup;

template <lookup_mode lk, int key, int... first, int ... second,  int... indices>
struct lookup<lk, key, index_list<first...>, index_list<second...>, index_list<indices...>>:
    rack<-1>, rack<indices>...
{
    constexpr lookup() :
        rack<-1>{0}, rack<indices>{ ( rack<indices-1>::v ?
                                0
                              : ( lk == lookup_mode::FirstSec ?
                                  (first == key) * second
                                : (second == key) * first ) ) + rack<indices-1>::v } ... {}

    static const int value;
};

template <lookup_mode lk, int val, int... i, int ... k, int... indices>
const int lookup<lk, val, index_list<i...>, index_list<k...>, index_list<indices...>>::value = lookup{}.rack<sizeof...(indices)-1>::v;

int main()
{
    std::cout << lookup<lookup_mode::FirstSec, 8, index_list<4, 8, 6>, index_list<0, 47, 95>>::value << '\n';
    std::cout << lookup<lookup_mode::SecFirst, 6, index_list<4, 74, 68, 6>, index_list<0, 6, 6, 95>>::value << '\n';
}

    Auch hier wäre deine Idee von typedefs mit template-parameter packs schön, das würde besser passen.

    using pack_typedef_name = ... std::conditional< lk == lookup_mode::FirstSec, tpp_wrapper<first...>, tpp_wrapper<second...> >::type::pack;

    (Die Ellipse gibt an, dass pack ein parameter-pack ist)

    camper schrieb:

    (und sowieso die einzige Möglichkeit, da constexpr immer einen Initialisierer benötigt, liese sich eine solche Variable sonst gar nicht nur deklarieren).

    Aber schon, wenn sie eine statische Membervariable ist (wie ja auch in [dcl.constexpr]/1 erklärt). Das implementiert aber GCC 4.8.1 nicht korrekt...

    0
  • ?
     

    template <int Key, bool Flipped=false> struct hook { int value; };

template <typename, typename> struct static_map;

template <int... first, int ... second>
struct static_map<index_list<first...>, index_list<second...> >
  : hook<first>..., hook<second, true>... {
  static_map() : hook<first>{second}..., hook<second, true>{first}... {}

  template <int V> static constexpr int lookup_key() {
    return static_cast<hook<V> >(static_map{}).value;
  }
  template <int V> static constexpr int lookup_value() {
    return static_cast<hook<V, true> >(static_map{}).value;
  }
};
    0
Anmelden zum Antworten