Вопрос:

C ++ вычисляет и сортирует вектор во время компиляции

c++ c++11 metaprogramming

3602 просмотра

7 ответа

63 Репутация автора

У меня class Aесть std::vector<int>атрибут as. Aнеобходимо заполнить этот вектор при создании экземпляра A. Расчет может занять некоторое время, и я хотел бы знать, если:

  1. это можно сделать во время компиляции.
  2. вектор может быть отсортирован также во время компиляции

Я не знаком с метапрограммированием и пока не нашел способа сделать это. Это не специфичный для ОС вопрос.

Вот A.cppфайл:

#include "A.h"
#define SIZEV 100

A::A()
{
    fillVector();
}

void A::fillVector()
{
    // m_vector is an attribute of class "A"
    // EXPECTATION 1 : fill the vector with the following calculation at compile time

    const int a=5;
    const int b=7;
    const int c=9;

    for(int i=0;i<SIZEV;i++){
        for(int j=0;j<SIZEV;j++){
            for(int k=0;k<SIZEV;k++){
                this->m_vector.push_back(a*i+b*j+c*k);
            }
        }
    }

    // EXPECTATION 2 : sort the vector as compile time 
}

std::vector<int> A::getVector() const
{
    return m_vector;
}

void A::setVector(const std::vector<int> &vector)
{
    m_vector = vector;
}

и main.cpp(приложение Qt, но это не имеет значения):

#include <QCoreApplication>
#include "A.h"

int main(int argc, char *argv[])
{
    QCoreApplication app(argc, argv);

    A a;
    auto vec = a.getVector();

    // use vec, etc ...

    return app.exec();
}
Автор: BlackPopa Источник Размещён: 18.09.2015 08:28

Ответы (7)


13 плюса

55210 Репутация автора

Решение

У A std::vector<int>нет constexprконструкторов (поскольку динамическое выделение памяти запрещено constexpr). Так что вы не можете сортировать std::vector<int>во время компиляции.

Вы можете создать std::array<int, N>во время компиляции для константы N, но вам придется написать свою собственную процедуру сортировки, потому что std::sortэто не constexprтак.

Вы также можете написать вектор или список во время компиляции Boost.MPL и использовать sortпроцедуру этого. Но это не будет масштабироваться так же хорошо std::array.

Другим углом атаки может быть сохранение вектора в staticпеременной и выполнение сортировки при инициализации программы. Ваша программа запускается немного дольше, но это не повлияет на остальные основные функции.

Поскольку сортировка выполняется O(N log N), вы можете даже создать двухэтапную сборку и записать отсортированный вектор в файл и либо скомпилировать / связать его с вашей основной программой, либо загрузить его O(N)при запуске программы в staticпеременную.

Автор: TemplateRex Размещён: 18.09.2015 08:39

5 плюса

103967 Репутация автора

Классический подход для длинных вычислений, который может быть предварительно вычислен, состоит в том, чтобы вычислять результат как часть процесса сборки, генерируя .cppкод, который жестко кодирует результат (на платформах, которые имеют встроенные ресурсы, они также могут использоваться). ,

Однако, здесь расчет очень прост, медленная часть, вероятно , просто выделение, которое, если вы хотите сохранить данные в std::vector, имеет произойти во время выполнения. Если вы можете жить с массивом в стиле C, вы можете поместить все это в исполняемый файл, как описано выше, но это приведет к увеличению размера исполняемого файла на 4 МБ, а замедление загрузки из-за диска сведет на нет все преимущества предварительного вычисления в скорости.

IOW: предварительный расчет во время сборки имеет смысл, когда вычисления дорогостоящие, а выходные данные малы. Ваш случай прямо противоположен спектру, поэтому я бы его избегал.

Автор: Matteo Italia Размещён: 18.09.2015 08:41

2 плюса

535 Репутация автора

Возможно, не совсем то, что вы ищете, но вы могли бы написать отдельную программу для вычисления вектора, отсортировать его и затем вывести его в список. Тогда вы можете просто прочитать в этом файле.

Если чтение с диска слишком медленное, вы можете также преобразовать вывод в допустимый файл C ++, который инициализирует экземпляр вашего класса, имеющий жестко закодированные значения, отвечающие вашим требованиям. Затем он может быть связан с вашим основным проектом и скомпилирован, по сути, предоставляя ту же функциональность, что и гораздо более сложная задача метапрограммирования, которую вы здесь изложили.

Автор: AGML Размещён: 18.09.2015 08:47

4 плюса

192795 Репутация автора

Хотя это можно сделать ( живой пример ), вы не должны этого делать. Это займет много времени компиляции.

Компилятор не предназначен для быстрой и эффективной массовой обработки чисел. Пока ограничьте вашу работу во время компиляции относительно простыми вещами, не сортируя 10 миллионов элементов.

Даже если вы напишите «совместимый» код, большинство современных компиляторов взорвется от вас. Код, который я написал, умирает довольно рано, хотя я пытался быть осторожным с ограничением глубины рекурсии.

Во всяком случае, для потомков:

template<class T>struct tag{using type=T;};
template<class Tag>using type_t=typename Tag::type;

template<int...Xs> struct values { constexpr values() {}; };

template<int...Xs> constexpr values<Xs...> values_v = {};

template<class...Vs> struct append;
template<class...Vs> using append_t=type_t<append<Vs...>>;
template<class...Vs> constexpr append_t<Vs...> append_v = {};

template<> struct append<>:tag<values<>>{};
template<int...Xs>struct append<values<Xs...>>:tag<values<Xs...>>{};
template<int...Lhs, int...Rhs, class...Vs>
struct append<values<Lhs...>,values<Rhs...>,Vs...>:
    tag<append_t<values<Lhs...,Rhs...>,Vs...>>
{};

template<int...Lhs>
constexpr values<Lhs...> simple_merge( values<Lhs...>, values<> ) { return {}; }
template<int...Rhs>
constexpr values<Rhs...> simple_merge( values<>, values<Rhs...> ) { return {}; }
constexpr values<> simple_merge( values<>, values<> ) { return {}; }

template<int L0, int...Lhs, int R0, int...Rhs>
constexpr auto simple_merge( values<L0, Lhs...>, values<R0, Rhs...> )
-> std::conditional_t<
    (R0 < L0),
    append_t< values<R0>, decltype( simple_merge( values<L0,Lhs...>{}, values<Rhs...>{} ) ) >,
    append_t< values<L0>, decltype( simple_merge( values<Lhs...>{}, values<R0, Rhs...>{} ) ) >
> {
    return {};
}

template<class Lhs, class Rhs>
using simple_merge_t = decltype( simple_merge( Lhs{}, Rhs{} ) );
template<class Lhs, class Rhs>
constexpr simple_merge_t<Lhs, Rhs> simple_merge_v = {};

template<class Values, size_t I> struct split
{
private:
    using one = split<Values, I/2>;
    using two = split<typename one::rhs, I-I/2>;
public:
    using lhs = append_t< typename one::lhs, typename two::lhs >;
    using rhs = typename two::rhs;
};
template<class Values, size_t I> using split_t=type_t<split<Values, I>>;

template<class Values> struct split<Values, 0>{
    using lhs = values<>;
    using rhs = Values;
};
template<int X0, int...Xs> struct split<values<X0, Xs...>, 1> {
    using lhs = values<X0>;
    using rhs = values<Xs...>;
};
template<class Values, size_t I> using before_t = typename split<Values, I>::lhs;
template<class Values, size_t I> using after_t = typename split<Values, I>::rhs;

template<size_t I>using index_t=std::integral_constant<size_t, I>;
template<int I>using int_t=std::integral_constant<int, I>;
template<int I>constexpr int_t<I> int_v={};

template<class Values> struct front;
template<int X0, int...Xs> struct front<values<X0, Xs...>>:tag<int_t<X0>>{};
template<class Values> using front_t=type_t<front<Values>>;
template<class Values> constexpr front_t<Values> front_v = {};

template<class Values, size_t I>
struct get:tag<front_t< after_t<Values, I> >> {};
template<class Values, size_t I> using get_t = type_t<get<Values, I>>;
template<class Values, size_t I> constexpr get_t<Values, I> get_v = {};

template<class Values>
struct length;
template<int...Xs>
struct length<values<Xs...>>:tag<index_t<sizeof...(Xs)>> {};
template<class Values> using length_t = type_t<length<Values>>;
template<class Values> constexpr length_t<Values> length_v = {};

template<class Values> using front_half_t = before_t< Values, length_v<Values>/2 >;
template<class Values> constexpr front_half_t<Values> front_half_v = {};
template<class Values> using back_half_t = after_t< Values, length_v<Values>/2 >;
template<class Values> constexpr back_half_t<Values> back_half_v = {};

template<class Lhs, class Rhs>
struct least : tag< std::conditional_t< (Lhs{}<Rhs{}), Lhs, Rhs > > {};
template<class Lhs, class Rhs> using least_t = type_t<least<Lhs, Rhs>>;
template<class Lhs, class Rhs>
struct most : tag< std::conditional_t< (Lhs{}>Rhs{}), Lhs, Rhs > > {};
template<class Lhs, class Rhs> using most_t = type_t<most<Lhs, Rhs>>;

template<class Values>
struct pivot {
private:
    using a = get_t<Values, 0>;
    using b = get_t<Values, length_v<Values>/2>;
    using c = get_t<Values, length_v<Values>-1>;
    using d = most_t< least_t<a,b>, most_t< least_t<b,c>, least_t<a,c> > >;
public:
    using type = d;
};
template<int X0, int X1>
struct pivot<values<X0, X1>>: tag< most_t< int_t<X0>, int_t<X1> > > {};

template<class Values> using pivot_t = type_t<pivot<Values>>;
template<class Values> constexpr pivot_t<Values> pivot_v = {};

template<int P>
constexpr values<> lower_split( int_t<P>, values<> ) { return {}; }
template<int P, int X0>
constexpr std::conditional_t< (X0<P), values<X0>, values<> > lower_split( int_t<P>, values<X0> ) { return {}; }

template<int P, int X0, int X1, int...Xs >
constexpr auto lower_split( int_t<P>, values<X0, X1, Xs...> )
-> append_t<
    decltype(lower_split( int_v<P>, front_half_v<values<X0, X1, Xs...>> )),
    decltype(lower_split( int_v<P>, back_half_v<values<X0, X1, Xs...>> ))
>{ return {}; }
template<int P>
constexpr values<> upper_split( int_t<P>, values<> ) { return {}; }
template<int P, int X0>
constexpr std::conditional_t< (X0>P), values<X0>, values<> > upper_split( int_t<P>, values<X0> ) { return {}; }
template<int P, int X0, int X1, int...Xs>
constexpr auto upper_split( int_t<P>, values<X0, X1, Xs...> )
-> append_t<
    decltype(upper_split( int_v<P>, front_half_v<values<X0, X1, Xs...>> )),
    decltype(upper_split( int_v<P>, back_half_v<values<X0, X1, Xs...>> ))
>{ return {}; }

template<int P>
constexpr values<> middle_split( int_t<P>, values<> ) { return {}; }
template<int P, int X0>
constexpr std::conditional_t< (X0==P), values<X0>, values<> > middle_split( int_t<P>, values<X0> ) { return {}; }
template<int P, int X0, int X1, int...Xs>
constexpr auto middle_split( int_t<P>, values<X0, X1, Xs...> )
-> append_t<
    decltype(middle_split( int_v<P>, front_half_v<values<X0, X1, Xs...>> )),
    decltype(middle_split( int_v<P>, back_half_v<values<X0, X1, Xs...>> ))
>{ return {}; }

template<class Values>
using lower_split_t = decltype(lower_split( pivot_v<Values>, Values{} ) );
template<class Values> constexpr lower_split_t<Values> lower_split_v = {};
template<class Values>
using upper_split_t = decltype(upper_split( pivot_v<Values>, Values{} ) );
template<class Values> constexpr upper_split_t<Values> upper_split_v = {};
template<class Values>
using middle_split_t = decltype(middle_split( pivot_v<Values>, Values{} ) );
template<class Values> constexpr middle_split_t<Values> middle_split_v = {};

constexpr values<> simple_merge_sort( values<> ) { return {}; }
template<int X>
constexpr values<X> simple_merge_sort( values<X> ) { return {}; }

template<class Values>
using simple_merge_sort_t = decltype( simple_merge_sort( Values{} ) );
template<class Values>
constexpr simple_merge_sort_t<Values> simple_merge_sort_v = {};

template<int X0, int X1, int...Xs>
constexpr auto simple_merge_sort( values<X0, X1, Xs...> )
-> 
simple_merge_t<
    simple_merge_t<
        simple_merge_sort_t<lower_split_t<values<X0, X1, Xs...>>>, simple_merge_sort_t<upper_split_t<values<X0, X1, Xs...>>>
    >,
    middle_split_t<values<X0, X1, Xs...>>
>
{ return {}; }


template<class Values>constexpr Values cross_add( Values ) { return {}; }
template<class Values>constexpr values<> cross_add( values<>, Values ) { return {}; }
template<int A0, int...B>constexpr values<(B+A0)...> cross_add( values<A0>, values<B...> ) { return {}; }

template<int A0, int A1, int...A, int...B>
constexpr auto cross_add( values<A0, A1, A...>, values<B...>)
-> append_t<
    decltype(cross_add( front_half_v<values<A0, A1, A...>>, values_v<B...> ) ),
    decltype(cross_add( back_half_v<values<A0, A1, A...>>, values_v<B...> ) )
> { return {}; }

template<class V0, class V1, class V2, class... Vs>
constexpr auto cross_add( V0, V1, V2, Vs... )
-> decltype(
    cross_add( cross_add( V0{}, V1{} ), V2{}, Vs{}... )
) { return {}; }

template<class...Vs>
using cross_add_t = decltype( cross_add(Vs{}...) );
template<class...Vs>
constexpr cross_add_t<Vs...> cross_add_v = {};

template<int X, int...Xs>
constexpr values<(X*Xs)...> scale( int_t<X>, values<Xs...> ) { return {}; }
template<class X, class Xs>
using scale_t = decltype( scale(X{}, Xs{}) );
template<class X, class Xs> constexpr scale_t<X,Xs> scale_v = {};

template<int X0, int...Xs> struct generate_values : generate_values<X0-1, X0-1, Xs...> {};
template<int...Xs> struct generate_values<0,Xs...>:tag<values<Xs...>>{};
template<int X0> using generate_values_t = type_t<generate_values<X0>>;

медиана-три-сортировки во время компиляции и генератор перекрестных продуктов. Я мог бы, с усилием, возможно, значительно сократить количество строк.

Вероятно, выполнение этого с помощью a constexpr std::arrayбудет быстрее, чем приведенное выше решение чистого типа.

Автор: Yakk - Adam Nevraumont Размещён: 19.09.2015 03:22

4 плюса

144134 Репутация автора

Данные целые числа от 0до SIZEV * (a+b+c), но число целых равно SIZEV3 . Это плотная группа целых чисел с небольшим диапазоном, поэтому CountingSort идеально подходит (и вам не нужно создавать несортированный массив, просто приращения счетчиков при генерации).

Независимо от того, чтобы держать в пределах подсчета / суммы префикса, CountingSort , безусловно, станет большим выигрышем во время запуска для сортировки вектора по сравнению с другими видами, оставляя все остальное таким же.

Вы можете сохранить компактную форму (размер O (cuberoot (n))) ваших данных в виде вектора сумм префиксов для поиска из m_vector за время O (log (cuberoot (n))) (двоичный поиск по суммам префиксов), где n - длина m_vector. Увидеть ниже.

В зависимости от задержки кеша / памяти, не расширение m_vector может привести к выигрышу в производительности. Если требуется диапазон значений, вы можете очень быстро генерировать последовательные элементы m_vector на лету из сумм префиксов.

class A {
    // vector<uint16_t> m_counts;  // needs to be 32b for SIZEV>=794 (found experimentally).

    vector<uint32_t> m_pos;     // values are huge: indices into m_vector, up to SIZEV**3 - 1
    vector<uint16_t> m_vector;  // can be 16b until SIZEV>3121: max val is only (a+b+c) * (SIZEV-1)
}
void A::fillVector()
{
    const int a=5;
    const int b=7;
    const int c=9;

    const auto max_val = (SIZEV-1) * (a+b+c);

    m_vector.reserve(SIZEV*SIZEV*SIZEV);
    m_vector.resize(0);
    // or clear it, but that writes tons of mem, unless you use a custom Allocator::construct to leave it uninit
    // http://en.cppreference.com/w/cpp/container/vector/resize

    m_pos.resize(max_val + 1);  // again, ideally avoid zeroing
                  // but if not, do it before m_counts

    m_counts.clear();  // do this one last, so it's hot in cache even if others wasted time writing zeros.
    m_counts.resize(max_val + 1); // vector is now zeroed
    // Optimization: don't have a separate m_counts.
    // zero and count into m_pos, then do prefix summing in-place


    // manually strength-reduce the multiplication to addition
    // in case the compiler decides it won't, or can't prove it won't overflow the same way
    // Not necessary with gcc or clang: they both do this already
    for(int kc=c*(SIZEV-1) ; kc >= 0 ; kc-=c) {
      for(int jb=b*(SIZEV-1) ; jb >= 0 ; jb-=b) {
        for(int ia=a*(SIZEV-1) ; ia >= 0 ; ia-=a) {
          m_counts[kc + jb + ia]++;
          // do the smallest stride in the inner-most loop, for better cache locality
        }
      }
    }
// write the early elements last, so they'll be hot in the cache when we're done


    int val = 0;
    uint32_t sum = 0;
    for ( auto &count : m_counts ) {
       m_vector.insert(m_vector.end(), count, val++);
       // count is allowed to be zero for vector::insert(pos, count, value)
       m_pos[val] = sum;   // build our vector of prefix sums
       sum += count;

       //count = (sum+=count);  // in-place conversion to prefix sums
    }
    assert(m_vector.size() == SIZEV*SIZEV*SIZEV);
}

Или, вместо фактического расширения массива 1,6 ГБ, создайте префиксные суммы отсчетов, давая вам вектор начальной позиции прогона этого индекса в качестве элемента в m_vector. то есть idx = m_pos[val]; m_vector[idx] == val. (Это ломается для val <= 13, где есть значения, которые не могут быть представлены как сумма a, b и c, поэтому есть нули m_countи повторяются в m_pos)

В любом случае, вы можете заменить чтение m_vector[i]на двоичный поиск iвm_pos . Вы ищете самый высокий индекс, m_posкоторый имеет значение <= i. Этот индекс - то, что вы найдете в m_vector[i]. (Или что-то в этом роде; у меня может быть ошибка «один за другим».)

Хеш-таблица не будет работать, потому что вам нужно сопоставить несколько значений iкаждого числа от 0 .. (750 * (a + b + c)). (Все is m_vector[i]имеют одинаковое значение.)

Если вам нужен ряд последовательных элементов, сгенерируйте их на лету в буфер tmp. Посмотрите, m_pos[i+1]чтобы увидеть, когда появится следующий элемент с другим значением. (Глядя на это m_countsможет сэкономить некоторое вычитание, но вам, вероятно, лучше просто взять разницу в m_posинвертировании сумм префиксов, чтобы избежать пропусков кэша / загрязнения кэша от прикосновения ко второму массиву.)

На самом деле, m_countsвероятно, вообще не нужно быть участником класса, просто временным в FillVector. Или FillVector может рассчитывать m_posи преобразовывать его на месте в префиксные суммы.

В идеале есть что-то умное, что вы можете сделать с шаблонами, чтобы выбрать типы, которые достаточно широки, но не шире, чем нужно, для m_counts и m_vector. Теория чисел IDK, так что я не знаю, как доказать, что не будет ни одной корзины с такими m_countsпереполнениями a uint16_t. Средний отсчет будет 750 ** 3 / (750 * (5 + 7 + 9)) = 26786, и они , безусловно , сгруппированы по направлению к верхней границе m_counts. На практике SIZEV = 793 может использовать счетчики uint16_t, в то время как SIZEV = 794 производит несколько счетчиков> 65536 (спасибо Крису за рабочий пример, где я мог легко это проверить).

m_vectorможно uint16_tдо (SIZEV-1)*(a+b+c) > MAX_UINT16(65535). т.е. до SIZEV> = 3122, в этот момент m_vectorзанимает 28,3 ГБ ОЗУ.


При SIZEV = 750 m_posразмер кэша L1 составляет около 2х (ЦП Intel) ( 750*(5+7+9) * 4B per short = 63000B). Если компилятор делает хорошую работу и выполняет бинарный поиск с условным перемещением вместо непредсказуемых инструкций ветвления, это может быть довольно быстрым. Это, безусловно, сэкономит вам много трафика основной памяти, что ценно, если у вас несколько потоков.

Кроме того, никогда не трогать m_vectorозначает, что вы можете обрабатывать проблемы размеров, которые потребовали бы больше памяти, чем вы должны хранить список.

Если вы хотите по-настоящему креативно оптимизировать кеш при создании m_counts в первую очередь (с тройным вложенным циклом), пусть внутренний цикл будет идти вперед, а затем назад, вместо одного и того же направления оба раза. Это будет иметь значение только для очень большого SIZEV, или если другая гиперпотока оказывает большое давление на кэш.

  for(int kc=c*(SIZEV-1) ; kc >= 0 ; kc-=c) {
    for(int jb=b*(SIZEV-1) ; jb >= 0 ; jb-=b) {

      for(int ia=0 ; ia<SIZEV*a ; ia+=a)
        counts[kc + jb + ia]++;
      if (! (jb-=b )) break;
      for(int ia=a*(SIZEV-1) ; ia >= 0 ; ia-=a)
        counts[kc + jb + ia]++;

    }
  }

Обратный отсчет до нуля (с двунаправленными внутренними циклами или без них) весьма вероятен небольшой выигрыш для начала следующего цикла, прежде чем он станет связанным с памятью, выполняя большие наборы параметров памяти, когда число увеличивается. Также выигрыш для сканирования вперед, чтобы сделать префиксные суммы на месте.


мой предыдущий ответ, который, вероятно, тупик:

Есть ли надежда найти формулу замкнутой формы для iэлемента th в отсортированном векторе? Или даже алгоритм O (log i) для его генерации на лету?

Если вам не нужно много последовательных элементов из этого вектора, когда вы обращаетесь к нему, может быть быстрее вычислить его на лету. Память медленная, процессор быстрый, поэтому, если вы можете вычислить a[i]менее чем за ~ 150 тактов, вы впереди. (Предполагая, что каждый доступ является пропуском кеша или не затрагивает всю эту векторную память, уменьшает пропуски кеша в остальной части вашей программы).

Если бы мы могли сделать это, мы могли бы теоретически написать отсортированный массив по порядку в первую очередь.

Для этого: перемешайте константы так a <= b <= c.

0, a, [a*2 .. a*int(b/a)], b, [b + a .. b + a*int((c-b)/a) mixed with b*2 .. b*int(c/b)], c, [some number of b*x + a*y], c+a, [more b*x + a*y], ...

Итак, это превращается в комбинаторный беспорядок, и эта идея, вероятно, не является жизнеспособной. По крайней мере, не для общего случая каких-либо a, b и c.

С а = 5, б = 7, с = 9:

0, 5 = a, 7 = b, 9 = c, 10 = 2a, 12 = b + a, 14 = 2b, 14 = c + a, 15 = 3a, 16 = c + b, 18 = 2c

Я слишком сонный, чтобы увидеть шаблон, но вот более длинный список

# bash
limit=5; for ((i=0 ; i<limit ; i++)); do
             for ((j=0 ; j<limit ; j++)); do 
               for ((k=0 ; k<limit ; k++)); do 
                 printf "%2d: %d %d %d\n" $((5*i + 7*j + 9*k)) $i $j $k; 
           done; done; done | sort -n | cat -n
     1   0: 0 0 0
     2   5: 1 0 0
     3   7: 0 1 0
     4   9: 0 0 1
     5  10: 2 0 0
     6  12: 1 1 0
     7  14: 0 2 0
     8  14: 1 0 1
     9  15: 3 0 0
    10  16: 0 1 1
    11  17: 2 1 0
    12  18: 0 0 2
    13  19: 1 2 0
    14  19: 2 0 1
    15  20: 4 0 0
    16  21: 0 3 0
    17  21: 1 1 1
    18  22: 3 1 0
    19  23: 0 2 1
    20  23: 1 0 2
    21  24: 2 2 0
    22  24: 3 0 1
    23  25: 0 1 2
    24  26: 1 3 0
    25  26: 2 1 1
    26  27: 0 0 3
    27  27: 4 1 0
    28  28: 0 4 0
    29  28: 1 2 1
    30  28: 2 0 2
    31  29: 3 2 0
    32  29: 4 0 1
    33  30: 0 3 1
    34  30: 1 1 2
    35  31: 2 3 0
    36  31: 3 1 1
    37  32: 0 2 2
    38  32: 1 0 3
    39  33: 1 4 0
    40  33: 2 2 1
    41  33: 3 0 2
    42  34: 0 1 3
    43  34: 4 2 0
    44  35: 1 3 1
    45  35: 2 1 2
    46  36: 0 0 4
    47  36: 3 3 0
    48  36: 4 1 1
    49  37: 0 4 1
    50  37: 1 2 2
    51  37: 2 0 3
    52  38: 2 4 0
    53  38: 3 2 1
    54  38: 4 0 2
    55  39: 0 3 2
    56  39: 1 1 3
    57  40: 2 3 1
    58  40: 3 1 2
    59  41: 0 2 3
    60  41: 1 0 4
    61  41: 4 3 0
    62  42: 1 4 1
    63  42: 2 2 2
    64  42: 3 0 3
    65  43: 0 1 4
    66  43: 3 4 0
    67  43: 4 2 1
    68  44: 1 3 2
    69  44: 2 1 3
    70  45: 3 3 1
    71  45: 4 1 2
    72  46: 0 4 2
    73  46: 1 2 3
    74  46: 2 0 4
    75  47: 2 4 1
    76  47: 3 2 2
    77  47: 4 0 3
    78  48: 0 3 3
    79  48: 1 1 4
    80  48: 4 4 0
    81  49: 2 3 2
    82  49: 3 1 3
    83  50: 0 2 4
    84  50: 4 3 1
    85  51: 1 4 2
    86  51: 2 2 3
    87  51: 3 0 4
    88  52: 3 4 1
    89  52: 4 2 2
    90  53: 1 3 3
    91  53: 2 1 4
    92  54: 3 3 2
    93  54: 4 1 3
    94  55: 0 4 3
    95  55: 1 2 4
    96  56: 2 4 2
    97  56: 3 2 3
    98  56: 4 0 4
    99  57: 0 3 4
   100  57: 4 4 1
   101  58: 2 3 3
   102  58: 3 1 4
   103  59: 4 3 2
   104  60: 1 4 3
   105  60: 2 2 4
   106  61: 3 4 2
   107  61: 4 2 3
   108  62: 1 3 4
   109  63: 3 3 3
   110  63: 4 1 4
   111  64: 0 4 4
   112  65: 2 4 3
   113  65: 3 2 4
   114  66: 4 4 2
   115  67: 2 3 4
   116  68: 4 3 3
   117  69: 1 4 4
   118  70: 3 4 3
   119  70: 4 2 4
   120  72: 3 3 4
   121  74: 2 4 4
   122  75: 4 4 3
   123  77: 4 3 4
   124  79: 3 4 4
   125  84: 4 4 4
Автор: Peter Cordes Размещён: 19.09.2015 04:11

1 плюс

71 Репутация автора

This is a simple compile time sort for ints. It works by for each element, working out its position within the list. From this it works out what should be at each position. Then it builds a new list inserted at the appropriate positions. It's probably not as efficient in terms of complexity (it's O(n^2)) as the previous solution but it's much easier to understand and it doesn't use recursion.

#include <initializer_list>
#include <array>
#include <tuple>

template<int... members>
struct IntList
{
    constexpr bool operator==(IntList) const { return true; }

    template<int... others>
    constexpr bool operator==(IntList<others...>) const { return false; }

    template<int idx>
    static constexpr auto at() 
    {
        return std::get<idx>(std::make_tuple(members...));
    }

    template<int x>
    static constexpr auto indexOf()
    {
        int sum {};
        auto _ = { 0, (x > members ? ++sum : 0)... };
        return sum;
    }

    template<int x>
    static constexpr auto count()
    {
        int sum {};
        auto _ = { 0, (x == members ? ++sum : 0)... };
        return sum;
    }

    template<int i>
    static constexpr auto ith()
    {
        int result{};
        auto _ = {
            ( i >= indexOf<members>() && i < indexOf<members>() + count<members>() ? 
              result = members : 0 )...
        };
        return result;
    }

    template<std::size_t... i>
    static constexpr auto sortImpl(std::index_sequence<i...>)
    {
        return IntList< ith<i>()... >();
    }

    static constexpr auto sort() 
    {
        return sortImpl(std::make_index_sequence<sizeof...(members)>());
    }
};

static_assert(IntList<1, 2, 3>().at<1>() == 2, "");

static_assert(IntList<>().indexOf<1>()           == 0, "");
static_assert(IntList<1>().indexOf<1>()          == 0, "");
static_assert(IntList<1, 2, 3, 4>().indexOf<3>() == 2, "");

static_assert(IntList<>().count<1>()        == 0, "");
static_assert(IntList<1>().count<1>()       == 1, "");
static_assert(IntList<1, 1>().count<1>()    == 2, "");
static_assert(IntList<2, 2, 1>().count<1>() == 1, "");
static_assert(IntList<1, 2, 1>().count<1>() == 2, "");

static_assert(IntList<>().sort()        == IntList<>(),        "");
static_assert(IntList<1>().sort()       == IntList<1>(),       "");
static_assert(IntList<1, 2>().sort()    == IntList<1, 2>(),    "");
static_assert(IntList<2, 1>().sort()    == IntList<1, 2>(),    "");
static_assert(IntList<3, 2, 1>().sort() == IntList<1, 2, 3>(), "");
static_assert(IntList<2, 2, 1>().sort() == IntList<1, 2, 2>(), "");
static_assert(IntList<4, 7, 2, 5, 1>().sort() == IntList<1, 2, 4, 5, 7>(), "");
static_assert(IntList<4, 7, 7, 5, 1, 1>().sort() == IntList<1, 1, 4, 5, 7, 7>(), "");
Автор: Ab Wilson Размещён: 13.03.2018 03:15

0 плюса

1 Репутация автора

You can implement skew heap to sort ints in compile time. The following example is work for c++17.

#include <type_traits>
#include <utility>

template <class T, T... s>
using iseq = std::integer_sequence<T, s...>;

template <class T, T v>
using ic = std::integral_constant<T, v>;

template <class T, T v1, T v2>
constexpr auto ic_less_impl(ic<T, v1>, ic<T, v2>) -> ic<bool, v1 < v2>;
template <class ic1, class ic2>
using ic_less = decltype(ic_less_impl(ic1(), ic2()));

template <bool b>
using bool_cond_t = std::conditional_t<b, std::true_type, std::false_type>;

struct nil {};

template <class T, T v, T... s>
constexpr auto iseq_front_impl(iseq<T, v, s...>) -> ic<T, v>;
template <class T>
constexpr auto iseq_front_impl(iseq<T>) -> nil;
template <class seq>
using iseq_front = decltype(iseq_front_impl(seq()));

template <class T, T v, T... s>
constexpr auto iseq_pop_front_impl(iseq<T, v, s...>) -> iseq<T, s...>;
template <class seq>
using iseq_pop_front = decltype(iseq_pop_front_impl(seq()));

template <class T, T v, T... s>
constexpr auto iseq_append_impl(iseq<T, s...>, ic<T, v>) -> iseq<T, s..., v>;
template <class T, T v>
constexpr auto iseq_append_impl(nil, ic<T, v>) -> iseq<T, v>;
template <class seq, class c>
using iseq_append = decltype(iseq_append_impl(seq(), c()));

template <class seq>
using iseq_is_empty = bool_cond_t<std::is_same<iseq_front<seq>, nil>::value>;

template <class X, class L, class R>
struct skew_heap {};

template <class X, class L, class R>
constexpr auto skh_get_top_impl(skew_heap<X, L, R>) -> X;
template <class H>
using skh_get_top = decltype(skh_get_top_impl(H()));

template <class X, class L, class R>
constexpr auto skh_get_left_impl(skew_heap<X, L, R>) -> L;
template <class H>
using skh_get_left = decltype(skh_get_left_impl(H()));

template <class X, class L, class R>
constexpr auto skh_get_right_impl(skew_heap<X, L, R>) -> R;
template <class H>
using skh_get_right = decltype(skh_get_right_impl(H()));

template <class H>
using skh_is_empty = bool_cond_t<std::is_same<H, nil>::value>;

template <class H1, class H2>
constexpr auto skh_merge_impl(H1, H2) -> decltype(auto) {
    if constexpr (skh_is_empty<H1>::value) {
        return H2{};
    } else if constexpr (skh_is_empty<H2>::value) {
        return H1{};
    } else {
        using x1 = skh_get_top<H1>;
        using l1 = skh_get_left<H1>;
        using r1 = skh_get_right<H1>;

        using x2 = skh_get_top<H2>;
        using l2 = skh_get_left<H2>;
        using r2 = skh_get_right<H2>;

        if constexpr (ic_less<x2, x1>::value) {
            using new_r2 = decltype(skh_merge_impl(H1(), r2()));
            return skew_heap<x2, new_r2, l2> {};
        } else {
            using new_r1 = decltype(skh_merge_impl(r1(), H2()));
            return skew_heap<x1, new_r1, l1>{};
        }
    }
}
template <class H1, class H2>
using skh_merge = decltype(skh_merge_impl(H1(), H2()));

template <class H1, class IC1>
using skh_push = skh_merge<H1, skew_heap<IC1, nil, nil>>;

template <class H>
using skh_pop = skh_merge<skh_get_left<H>, skh_get_right<H>>;

template <class H, class seq>
constexpr auto skh_heapify_impl(H, seq) -> decltype(auto) {
    if constexpr (iseq_is_empty<seq>::value) {
        return H{};
    } else {
        using val = iseq_front<seq>;
        return skh_heapify_impl(skh_push<H, val>{}, iseq_pop_front<seq>{});
    }
}
template <class seq>
using skh_heapify = decltype(skh_heapify_impl(nil(), seq()));

template <class H, class seq>
constexpr auto skh_to_sortseq_impl(H, seq) -> decltype(auto) {
    if constexpr (skh_is_empty<H>::value) {
        return seq{};
    } else {
        using val = skh_get_top<H>;
        return skh_to_sortseq_impl(skh_pop<H>{}, iseq_append<seq, val>{});
    }
}
template <class H>
using skh_to_sortseq = decltype(skh_to_sortseq_impl(H(), nil()));

template <class seq>
using sort_seq = skh_to_sortseq<skh_heapify<seq>>;

static_assert(std::is_same<iseq<int, 1, 2, 3, 4, 5, 6, 7, 8, 9>, sort_seq<iseq<int, 2, 3, 5, 8, 9, 6, 7, 1, 4>>>::value);
Автор: firejox Размещён: 13.06.2019 05:27
Вопросы из категории :
32x32