1--*_*--1 11 c arrays algorithm cuda dynamic-programming
关于您知道哪些可能相关的数值方法的任何方法,请在此处发布!
我有一个values每个集合的数组,每个值的索引对应于值绑定的集合,因此我将集合表示为一个整数,其中元素表示位位置,例如,其中包含元素1的集合是表示为...001其中1是LSB.
所以集合只是一个索引并且从不存储,它是动态生成的,它是导致数组中代表集合值的索引的关键.
我所做的是给定一个集合,是任何成对不相交子集的总和值大于该集合的值.例如,如果set 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.因此,为了得到仅包含第一个元素ergo 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个元素的数组.当需要随机访问以进一步说明时,请查看改进随机存储器访问.
但是,这会导致内存中的高级随机访问,即使我在基数之后对它们进行分组也是如此.目前通过基数对它们进行分组,并且生成索引比在集合所代表的数字之后对它们进行排序要慢.
我使用基数分组的集合生成索引的方法是在常量内存中使用pascals三角形,如确定两个整数之间的词典距离中的答案所述
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 index表示如果没有在基数中排序它将具有的索引.这只是为了显示每个集合的值所在的位置.
整数集表示值数组中的索引,通过直接索引(我当前正在执行的操作,提供随机访问)或通过从集合到索引的转换.
我没有将集合分成子集,而是自下而上生成集合.例如0111,我不会分割成所有成对不相交的子集,而是在某些时候从集合中生成if {0100,0011},{0010,0101},{0001,0110}.
假设我们想要评估基数为3,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套,因此需要很好地扩展.
允许该算法被吐出到两个或更多个实例,例如,一个用于偶数,一个用于奇数.
我很乐意参考有关您使用的技术的消息来源.
该算法应使用尽可能少的分配和指令,并应避免任何分歧.但是如果你认为你有一个偶数 - 虽然你有很多这个,尝试发布,我会很高兴任何信息.
如果以其他方式订购,但它仍然按照我的描述进行,我建议您在此处发布,任何帮助都非常有帮助
请问是否有任何不清楚的地方.
我有一个数组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),并得到他们的总和.继续,直到所有集合都已"生成"
我不知道这是否对您有帮助，但我在Hacker's Delight中发现了一个无分支的单词中所有 1 位的函数，它似乎可以帮助您确定基数一组：
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 上，它应该相当快，因为它没有分支。