Come posso migliorare la complessità di spazio O (N ^ 2) per una ricerca di sequenza di tipo?

Question

Come posso migliorare la complessità di spazio O (N ^ 2) per una ricerca di sequenza di tipo?

#1 da (2 voti)
#2 da (1 voti)

2

Supponiamo di avere una sequenza di tipi attraverso la quale voglio cercare:

template <typename...> struct TypeSequence { using type = TypeSequence; };

Voglio creare un metafunction Search che restituisce true se un determinato tipo esiste nella mia sequenza di tipo, o false altrimenti, e Voglio che abbia di meglio di O (N ^ 2) spazio-complessità !

Al momento, in pratica, devo scorrere ogni elemento e creare un true_type se il primo elemento corrisponde, oppure continuare con 1 dei tipi troncati finché non raggiungo la fine.

In C ++ assomiglia a questo:

template <typename Enable, typename Type, typename... T>
struct SearchImpl;

// empty type sequence
template <typename Type>
struct SearchImpl<void, Type> : std::false_type
{
};

// first element matches
template <typename Type, typename T1, typename... T>
struct SearchImpl<
    typename std::enable_if<std::is_same<Type, T1>::value>::type,
    Type, T1, T...>
:
    std::true_type
{
};

// first element doesn't match
template <typename Type, typename T1, typename... T>
struct SearchImpl<
    typename std::enable_if<!std::is_same<Type, T1>::value>::type,
    Type, T1, T...>
:
    SearchImpl<void, Type, T...>
{
};

// check if a type exists within a type list
template <typename TypeList, typename T>
struct Search;

template <template <typename...> class TypeList, typename T, typename... Types>
struct Search<TypeList<Types...>, T>
:
    SearchImpl<void, T, Types...>
{
};

Per una sequenza di tipi di lunghezza N con il tipo corrispondente situato a N/2 , questa operazione di ricerca crea N/2 tipi unici con una lunghezza dell'ordine N ciascuno, equivalente a qualcosa nell'ordine di O ( N ^ 2) complessità dello spazio in fase di compilazione.

Esiste un modo per eseguire una ricerca di questo tipo con una complessità inferiore?

Quanto segue sarebbe molto economico, ma è illegale perché richiede un pacchetto variadico non alla fine dell'elenco degli argomenti:

template <typename T, typename... Types>
struct Has : std::false_type
{
};

template <typename T, typename... T1, typename... T2>
struct Has<T, T1..., T, T2...> : std::true_type // illegal!
{
};

Come posso inquadrare meglio una soluzione a questo problema per ridurre la complessità dello spazio (cioè il numero di tipi istanziati). So che posso ridurlo semplicemente cercando tra blocchi più grandi, ma questo non riduce la complessità stessa (cioè non scala bene).

La risposta può essere in pseudo-codice, purché scrivibile in codice template c ++.

c++ optimization templates

posta quant 04.11.2014 - 03:27

fonte

2 risposte

Leggi altre domande sui tag c++ optimization templates

migrazione del database con i dati già presenti nel database in produzione Modello SaaS, 1DB per client

score 2 · Answer 1

Il trucco base qui è un post sul blog che descrive un'implementazione di std :: tuple . Siamo limitati nelle nostre opzioni per argomenti modello variadic, ma possiamo usarli per definire le classi base per una classe.

template<typename T, typename... Haystack>
struct SearchImpl : std::is_same<T, Haystack>...
{
};

Questa classe eredita da std :: true_type per ogni tipo corrispondente e std :: false_type per ogni tipo non corrispondente. Quindi tutto ciò che dobbiamo fare è determinare se eredita da std :: true_type.

template<typename T, typename... Haystack>
struct Search : std::is_base_of<std::true_type, SearchImpl<T, Haystack...>>::type 
{
};

score 1 · Answer 2

Partendo dalla risposta di Winston Ewart, ho scoperto qualcosa che utilizza ancora solo O(n) di istanze di tipo, ma funziona anche quando si hanno tipi duplicati nel proprio pacchetto di parametri

// we want to get a different size if the types match
template <typename A, typename B> struct Same { char padding[3]; };
template <typename A> struct Same<A,A> { char padding[7]; };
template <typename T> struct Diff: public Same<int,bool> {};

#include <cstddef>
constexpr std::size_t SameSize = sizeof(Same<bool,bool>);       // size if really same
constexpr std::size_t DiffSize = SameSize - sizeof(Diff<bool>); // difference in size

// we instantiate only two flat tuples, hence O(n)
#include <tuple>
template <typename Needle, typename... Haystack>
struct SearchImpl {
    typedef std::tuple<Same<Needle,Haystack>...> SameTypes; // some may be matches
    typedef std::tuple<Diff<Haystack>...> DiffTypes;        // none will be matches

    static constexpr size_t matches = (sizeof(SameTypes)-sizeof(DiffTypes)) / DiffSize;
    static constexpr bool result = (matches > 0);
};

template <typename Needle, typename... Haystack>
struct Search: public std::integral_constant<bool, SearchImpl<Needle,Haystack...>::result>
{};

Nota che la tupla non può comprimere i membri (non sono mai vuoti), quindi il calcolo delle dimensioni è corretto e ottieni il numero di corrispondenze come bonus.