campers TMP-Aufgabe(n): 7

Sone

Mir fällt auf, mein sub_list -Konstrukt ist schön. Keine Rekursion. Schön direkt.
Daher kann man verschiedene Dinge damit schön schreiben:

template<typename, std::size_t> struct cyclic_shift_list;
template<int_type... args, std::size_t size>
struct cyclic_shift_list<index_list<args...>, size> :
    concat<typename sub_list<index_list<args...>, size, sizeof...(args) - size>::identity,
           typename sub_list<index_list<args...>, 0, size>::identity> {};

Oder

template<typename> struct accumulate;

template<int_type ... args>
struct accumulate<index_list<args...>>
{
    typedef index_list<args...> list;
    static constexpr int_type value = list::arr[list::length - 1] 
                                    + accumulate<typename sub_list<list, 0, list::length - 1>::identity>::value;
};

template<int_type first>
struct accumulate<index_list<first>> :
    std::integral_constant<int_type, first> {};

Das interessante an dieser Definition von accumulate ist die Tatsache, dass accumulate<1, 2, 3, 4> zu 4 + accumulate<1, 2, 3>::value wird - aber accumulate<1, 2, 3> wurde schon,
im Zuge der Expansions-Reihenfolge von partial_sum(_impl) , vorher instantiiert(!).
Also keine wirkliche Rekursion, da im Prinzip nur zwei vorhandene Werte addiert werden. Natürlich nur beim speziellen Fall von partial_sum .
Daher ist das recht effizient. Und das ganze ist dann auch campers Aufgabe entsprechend - es gibt zwar eine Rekursion, aber nur bei make_indices .
Dieses Prinzip, wo die Rekursion erschnellt wird in dem die Spezialisierungen alle von unten nach oben instantiiert werden, kann man bestimmt auch auf andere Dinge übertragen.

#include <type_traits>

typedef unsigned int_type;

template<int_type ... args>
struct index_list
{
    typedef index_list identity;
    static constexpr auto length = sizeof...(args);
    static constexpr int_type arr[]{args...};
};
template<int_type ... args>
constexpr int_type index_list<args...>::arr[];

/// concat + make_indices: ///////////////////////////////////////////////////////////////////////////////////////

template<typename, typename> struct concat;
template<int_type ... args1, int_type ... args2>
struct concat<index_list<args1...>, index_list<args2...>> : index_list<args1..., args2...> {};

template<std::size_t N>
struct make_indices : concat<typename make_indices<N-1>::identity, index_list<N-1>> {};
template<> struct make_indices<0> : index_list<> {};

/// sub-list: ///////////////////////////////////////////////////////////////////////////////////////

template<typename, typename, std::size_t start, std::size_t len> struct sub_list_impl;
template<int_type ... args, int_type ... indices, std::size_t start, std::size_t len>
struct sub_list_impl<index_list<args...>, index_list<indices...>, start, len> :
    index_list< index_list<args...>::arr[indices + start]...> {};

template<typename, std::size_t start, std::size_t len> struct sub_list;
template<int_type ... args, std::size_t start, std::size_t len>
struct sub_list<index_list<args...>, start, len> : sub_list_impl<index_list<args...>, typename make_indices<len>::identity, start, len>
{
    static_assert( start + len <= sizeof...(args), "invalid range!" );
};

/// accumulate: ///////////////////////////////////////////////////////////////////////////////////////

template<typename> struct accumulate;

template<int_type ... args>
struct accumulate<index_list<args...>>
{
    typedef index_list<args...> list;
    static constexpr int_type value = list::arr[list::length - 1]
                                    + accumulate<typename sub_list<list, 0, list::length - 1>::identity>::value;
};

template<int_type first>
struct accumulate<index_list<first>> :
    std::integral_constant<int_type, first> {};

/// partial-sum: ///////////////////////////////////////////////////////////////////////////////////////

template<typename,
         typename>
struct partial_sum_impl;

template<int_type ... values,
         int_type ... indices>
struct partial_sum_impl<index_list<values...>, index_list<indices...>> :
    index_list< accumulate< typename sub_list<index_list<values...>, 0, indices + 1>::identity >::value... > {};

template<int_type ... args>
struct partial_sum :
    partial_sum_impl<index_list<args...>, typename make_indices<sizeof...(args)>::identity> {};

/// ///////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <iterator>
int main()
{
    typedef partial_sum<1, 2, 3, 4> mul;
    std::copy(std::begin(mul::arr), std::end(mul::arr), std::ostream_iterator<int_type>(std::cout, ", "));
}

knivil

Ihr sucht Aufgaben: Generierung einer Sortierfunktion basierend auf Sortiernetzwerke. Breite, also Anzahl der zu sortierenden Elemente, ist zur Kompilezeit bekannt.

camper

Sone schrieb:

Das interessante an dieser Definition von accumulate ist die Tatsache, dass accumulate<1, 2, 3, 4> zu 4 + accumulate<1, 2, 3>::value wird - aber accumulate<1, 2, 3> wurde schon,
im Zuge der Expansions-Reihenfolge von partial_sum(_impl) , vorher instantiiert(!).
Also keine wirkliche Rekursion, da im Prinzip nur zwei vorhandene Werte addiert werden. Natürlich nur beim speziellen Fall von partial_sum .

Das ist wahrscheinlich ein Trugschluss. M.W.s schreibt der Standard die Reihenfolge der Instantiierung nicht vorgegeben für Templates mit dem gleichen Instantiierungspunkt nicht vor. Ein Compiler könnte also immer noch wegen Überschreitung der rekursiven Instantiierungstiefe aussteigen (wenn die Liste lang genug ist).

Die Lösung erfüllt möglicherweise die Aufgabenstellung, so wie sie gestellt wurde, nicht aber, wie sie gemeint war. Was ich nicht möchte, ist, dass das Argumentpack (auch nicht irgendwie verpackt) stückweise gekürzt und verarbeitet wird (also Zerlegung in Elementzahl+Rest, wobei die Länge des Rests von der ursprünglichen Packgröße abhängt). Deine Lösung geht schon in die richtige Richtung, indem das Problem ein bisschen platter geklopft wurde, aber es fehlt noch etwas.

@knivil: Kannst du ein kurzes Beispiel machen? Ich sehe die Möglichkeit, die parallelen Sortierschritte mittels Threads/openmp&co. oder über Vektorformen durchzuführen.

camper

kleine Aufgabe für zwischendurch:
maps
Gegeben seien zwei index_listen gleicher Länge und eine zusätzliche Zahl.
wenn die Zahl in der ersten Liste enthalten ist, soll der entsprechende Wert aus der zweiten Liste zurückgegeben werden.
Keine Rekursion.
lookup<map<index_list<2,3,5,7>,index_list<1,2,3,5>>,5>::value ergibt 3
Bonuspunkte, wenn die map bidirektionales Lookup erlaubt.

Ethon

Was spricht gegen std::binary_search?

Ich wusste bis eben nicht dass der Compiler bei

template<int... Values>
bool contains(int v)
{
    int arr[sizeof... Values] = { Values... };
    return binary_search(begin(arr), end(arr), v);
}

wirklich sämtlich Overhead rausoptimiert, zumindestens macht das der GCC bei -O3.

So macht es natürlich weniger Sinn. Trotzdem schöne Lösungen ihr 2.

Sone

Ich habe gerade, glaube ich, einen genialen Trick gefunden.

Sone schrieb:

Ich habe gerade, glaube ich, einen genialen Trick gefunden.

Dann teil ihn wenigstens mit uns.

Sone

fghfghfgh schrieb:

Sone schrieb:

Ich habe gerade, glaube ich, einen genialen Trick gefunden.

Dann teil ihn wenigstens mit uns.

Mit GCC 4.8 wird das nix. Versuch es jetzt mit Clang... (Edit: Scheiße. Ich krieg Clang nicht installiert. Führt wohl nix um Linux herum... *sigh*)

template<int N>
struct Tag
{
    static constexpr int value = N;

    constexpr Tag(){}

    template<int N2>
    constexpr Tag<N+N2> operator,(Tag<N2>)
    { return Tag<N+N2>(); }
};

decltype( Tag<args>... )::value

Sone

camper schrieb:

kleine Aufgabe für zwischendurch:
maps
Gegeben seien zwei index_listen gleicher Länge und eine zusätzliche Zahl.
wenn die Zahl in der ersten Liste enthalten ist, soll der entsprechende Wert aus der zweiten Liste zurückgegeben werden.
Keine Rekursion.
lookup<map<index_list<2,3,5,7>,index_list<1,2,3,5>>,5>::value ergibt 3
Bonuspunkte, wenn die map bidirektionales Lookup erlaubt.

template<typename, typename, int> struct lookup;
template<int ... keys, int ... vals, int index>
struct lookup<index_list<keys...>, index_list<vals...>, index>
{
    typedef index_list<((keys == index) * vals)...> hilighted_second;
    typedef index_list<((vals == index) * keys)...> hilighted_first;
};

Jetzt muss man nur noch aufaddieren (ggf. mit dem Trick oben) und man hat die Werte. Null bei keinem Fund, Summe der Werte bei mehreren Funden... letzteres ist ein Problem, nehme ich an?

Edit: Ach, wenn dieser Trick oben ginge... man könnte so viel geiles damit machen...

camper

Sone schrieb:

fghfghfgh schrieb:

Sone schrieb:

Ich habe gerade, glaube ich, einen genialen Trick gefunden.

Dann teil ihn wenigstens mit uns.

Mit GCC 4.8 wird das nix. Versuch es jetzt mit Clang... (Edit: Scheiße. Ich krieg Clang nicht installiert. Führt wohl nix um Linux herum... *sigh*)
template<int N>
struct Tag
{
    static constexpr int value = N;

    constexpr Tag(){}

    template<int N2>
    constexpr Tag<N+N2> operator,(Tag<N2>)
    { return Tag<N+N2>(); }
};
decltype( Tag<args>... )::value

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

Sone

camper schrieb:

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

Verdammt...!

camper

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

Sone

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)

Ethon

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...

Sone

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.

camper

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.

Sone

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.

camper

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

Sone

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

Sone

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.