C++在编译时计算和排序向量

Question

我有一个class A具有std::vector<int>作为属性. 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();
}

Answer 1

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变量中.

Answer 2

可以预先计算的冗长计算的经典方法是将结果计算为构建过程的一部分,生成.cpp硬编码结果(在具有嵌入资源的平台上也可以使用)..

但是,这里的计算非常简单,慢速部分可能只是分配,如果要保持数据std::vector,则必须在运行时进行.如果您可以使用C风格的阵列,您可以将其全部放在可执行文件中,如上所述,但这会产生大4 MB的可执行文件,并且从磁盘加载它的速度减慢将抵消预先计算的任何速度优势.

IOW:当计算成本高且输出很小时,在构建时预先计算是有意义的.你的情况与频谱完全相反,所以我会避免它.

Answer 3

数据是从0toSIZEV * (a+b+c)的整数，但整数的数量是SIZEV³。它是一组具有小范围的密集整数，因此CountingSort是完美的（并且您永远不需要构建未排序的数组，只需在生成时增加计数）。

不管保持计数/前缀总和，CountingSort在启动时间对向量进行排序方面绝对是一个巨大的胜利，与其他排序相比，保持其他所有内容相同。

您可以将数据的紧凑形式（O(cuberoot(n)) 大小）保留为前缀和的向量，以便在 O(log (cuberoot(n))) 时间内从 m_vector 进行查找（二进制搜索前缀和），其中 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.6GB 数组，而是对计数进行Prefix 总和，为您提供该索引运行的起始位置的向量作为m_vector. 即idx = m_pos[val]; m_vector[idx] == val。（这在 val <= 13 时分解，其中有些值无法表示为 a、b 和 c 的总和，因此在 中有零m_count，并在 中重复m_pos）

无论如何，您可以用m_vector[i]对iin的二进制搜索替换读取m_pos。您正在寻找m_pos值 <= i的最高索引。该索引就是您在m_vector[i]. （或类似的东西；我可能有一个逐一的错误。）

哈希表不起作用，因为您需要将 的多个值映射i到 0..(750*(a+b+c)) 中的每个数字。（所有is wherem_vector[i]都具有相同的值。）

如果您需要一系列顺序元素，请将它们即时生成到 tmp 缓冲区中。查看m_pos[i+1]下一个具有不同值的元素何时到来。（查看m_counts可能会节省一些减法，但您最好只考虑差异m_pos来反转前缀和，以避免缓存未命中/缓存污染接触第二个数组。）

实际上，m_counts可能根本不需要保留作为类成员，只是 FillVector 中的一个临时对象。或者 FillVector 可以计入m_pos，并就地将其转换为前缀总和。

理想情况下，您可以使用模板做一些聪明的事情，为 m_counts 和 m_vector 选择足够宽但不超过所需宽度的类型。IDK数论，所以我不知道如何证明不会有一个桶m_counts溢出一个uint16_t. 的平均计数将是750 ** 3 /（750 *（5 + 7 + 9））= 26786，他们正在朝一定的高端群集m_counts。在实践中，SIZEV=793 可以使用 uint16_t 计数器，而SIZEV=794 会产生多个计数 > 65536 （感谢 Chris 提供的工作示例，我可以轻松地对此进行测试）。

m_vector可以uint16_t一直到(SIZEV-1)*(a+b+c) > MAX_UINT16(65535)。即直到 SIZEV >= 3122，此时m_vector需要 28.3 GiB 的 RAM。

在 SIZEV = 750 时，m_pos大约是 L1 缓存大小的 2倍（Intel CPU）（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]++;

    }
  }

在下一个循环开始时向零递减计数（有或没有双向内循环）很可能是一个小胜利，然后在计数变高时它成为内存限制做大 memset 之前。通过转发扫描以进行适当的前缀和也是一个胜利。

我之前的回答，这可能是一个死胡同：

有没有希望为i排序向量中的第 th 个元素找到一个闭式公式？或者甚至是一个 O(log i) 算法来动态生成它？

除非您在访问它时需要来自该向量的大量顺序元素，否则动态计算它可能会更快。内存很慢，CPU 很快，所以如果你能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 的一般情况。

当 a=5, b=7, c=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

Answer 4

这是一个简单的整数编译时排序。它为每个元素工作，计算出它在列表中的位置。由此可以确定每个位置应该是什么。然后它构建一个插入到适当位置的新列表。它在复杂性方面可能不如以前的解决方案有效（它是 O(n^2)），但它更容易理解并且不使用递归。

#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>(), "");