c - 自下而上集生成和排序

Question

关于您知道的任何可能相关的任何数值方法的任何方法，请在此处发布!

背景

我有一个数组 values对于每个集合，每个值的索引对应于该值绑定(bind)到的集合，因此我将集合表示为整数，其中元素表示位位置，例如其中元素为 1 的集合表示为 ...001哪里1是 LSB .

所以集合只是一个索引，从不存储，它是动态生成的，它是导致数组中表示集合值的索引的键。

我所做的是给定一个集合，是任何成对不相交子集的总和值大于该集合的值。例如。如果设置 0111值为 3，其中两个子集的值为 0100 = 2和 0011 = 2 ，那么这种拆分更有利。我对集合的所有子集都这样做。

给定三个代理，排序是集合数表示。

val[8] = {0,1,2,4,3,2,4,2} the values is not important, only how they are ordered
          0 0 0 0 1 1 1 1 MSB bit representation of the index
          0 0 1 1 0 0 1 1
          0 1 0 1 0 1 0 1 LSB

111 的最佳拆分是 011 和 100，总和为 7。
因此，要获得仅包含第一个元素的集合的值，即 001，您放置 val[1]，对于具有元素 1 和 3(101) 的集合，您放置 val[5]。

按基数分组时如何对 val 数组进行排序

val[8] = {0,1,2,3,4,2,4,2}
          0 0 0 1 0 1 1 1 MSB bit representation of the index
          0 0 1 0 1 0 1 1
          0 1 0 0 1 1 0 1 LSB

在这里，您必须将索引转换为数组中的正确 bin，因此对于其中只有第三个元素(100)val[translate(4)] 的集合，它看起来像这样。想想大小大于 2^25 个元素的数组。
看 Improving random memory access when random access is needed进一步澄清。

但是，这会导致内存中随机访问的高阶顺序，即使我按照基数对它们进行分组。当前按基数对它们进行分组，并生成索引比在集合代表的数字之后对它们进行排序要慢。

我使用按基数分组的集合生成索引的方法是在常量内存中使用帕斯卡三角形，如 Determin the lexicographic distance between two integers 中的答案所述。

使用四个代理按基数进行排序和分组时，集合值所在的位置

n index 1  2  4  8     3  5  6  9  10 12    7  11 13 14    15
        -----------------------------------------------------
MSB     0  0  0  1  |  0  0  0  1  1  1  |  0  1  1  1  |  1
        0  0  1  0  |  0  1  1  0  0  1  |  1  0  1  1  |  1
        0  1  0  0  |  1  0  1  0  1  0  |  1  1  0  1  |  1
LSB     1  0  0  0  |  1  1  0  1  0  0  |  1  1  1  0  |  1

n 索引表示如果不按基数排序它将具有的索引。这只是为了显示每个集合的值所在的位置。

整数集表示值数组中的一个索引，通过直接索引(我目前正在做的，提供随机访问)或通过从集合到索引的转换。

想法

我没有将集合拆分为子集，而是自下而上地生成集合。例如。而不是拆分 0111对于所有成对不相交的子集，我会在某个时候从集合中生成 if {0100,0011},{0010,0101},{0001,0110} .

它应该如何以及为什么起作用

假设我们要评估基数为 3 的集合的所有 split ，ergo 集合 7,11,13,14 .由于拆分基数为 3 的集合的唯一方法是拆分为基数 1 和 2 的集合，因此我们需要评估基数 1 和基数 2 的所有不相交子集的总和是否大于这些集合的并集。

需要什么的符号(可能有点缺陷):
|C|=n,∀ a,b : a ∪ b = C , a ∩ b ={Ø}, |a|+|b| = n
因此，通过使用对每个线程的合并内存访问读取值，对于形成基数 n 的集合的每个子集，检查它的值是否大于形成的集合，如果是，则更新该值。

简单的例子，如果 n = 2那么你应该读入所有基数为 1 的值，并进行这些集合的所有组合并相应地更新。这个例子很简单，因为所有集合都是不相交的:

pseudo code for 4 threads, input card1 is pointer to array of sets |s| =1
__shared__ int value[4];
tid = threadIdx.x;
value[tid] = card1[tid]; // coalesced memory access
int thvalue = value[tid]; // holds the value for the thread, to avoid bank conflict
int rvalue[blockDim.x/2]= 0; //holds the sum
int i = blockDim.x;
int x = 0;
//reduction loop that dont generate duplicate sets
for(;i>0;i>>=1) {
    if(tid < i) {
        x++;
        rvalue[x-1] = value[(tid+x)%blockDim.x] + thvalue; 
    }
}
for(i = 0; i < x; i++) {
    int index = getindex(tid,i,1); //gets the index for the set it generated, 1 represent the cardinality
    if(output[index] < rvalue[i])
        output[index] = rvalue[i];
}

减少循环的迭代

Thread set specific for thread  first iteration second iteration 
0      0001                     0001 + 0010     0001 + 0100
1      0010                     0010 + 0100     0010 + 1000
2      0100                     0100 + 1000     none
3      1000                     1000 + 0001     none

如您所见，它已经获取了构成基数集 2 的所有子集的所有值。

然而，问题是生成大于 2 的基数集更加棘手，因为并非所有集都是不相交的。例如。 0001 和 0011 不是不相交的。

请记住，我不会将集合存储在任何地方，只存储集合的值。

最后

考虑到这一点，您将如何进行，创建一个算法来读取合并的内存，并从不相交的子集生成所有集合。在不检查子集是否不相交的情况下，它应该是完全确定的。

赏金

算法应该是标出不同步骤的描述文本，或者是伪代码。

应该用例子来证明它是有效的。并不是说这个算法达到了 n^32 个集合，所以它需要很好地扩展。

允许将算法吐出到两个或更多实例，例如一为偶数，一为奇数。

我很乐意引用有关您使用的技术的来源。

该算法应使用尽可能少的赋值和指令，并应避免任何分歧。但是如果你认为你得到了一个，即使你有很多这样的，试着发布，我会对任何信息感到满意。

如果它以另一种方式订购但它仍然像我描述的那样工作，我敦促您将其张贴在这里，任何帮助都非常有帮助

请问有什么不清楚的。

TL/DR 简单说明

我有一个数组 Z带值，索引 i如 Z[i]表示一个整数集，取决于 Z 的顺序, 值按基数分组，并按二进制字典排列排序 -> 集合值所在的位置 1,2,4,3,5,6,7 <- 所以我使用了一个函数(我实现了这个函数)将索引转换为正确的索引。例如。设置 3-> 索引 4。

通过将集合的值按基数分组，我想要的是，想看看是否有任何成对不相交的集合值大于它们形成的集合。

例如。 |a| = 3, |b|+|c| =3, b ∩ c ={Ø}, |b| =1所以阅读 X b 类型的值的数量, 和 X来自类型 c 的值的数量，找出 b 的所有不相交子集和 c来自类型 a (基数集 3)并得到它们的总和。继续直到所有集合都被“生成”

以供引用

Hamming weight based indexing

Determin the lexicographic distance between two integers

Improving random memory access when random access is needed

Answer 1

我不知道这对你有没有帮助，但我找到了一个 无分支计数一个字中的所有 1 位函数 在 Hacker's Delight 中，它似乎有助于您确定集合的基数:

int pop(unsigned int x) {
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

在文本中，Warren 声称上述序列可以编译为少至 21 条指令。
然而，在 i7 开发机器上使用 MSVC 2010，我检查了这个函数的反汇编，发现它在实际计算中大约有 22 条指令，总共有 33 条指令(计算堆栈操作)。在现代 CPU 或 GPU 上，它应该非常快，因为它没有分支。