个人中心
gpt4 book ai didi

algorithm - 如何生成 block 中的组合

转载 作者：行者123 更新时间：2023-12-02 19:55:37 26 4
gpt4 key购买 nike

我有算法为输入元素的每个组合执行计算，例如对于 100 个元素集中的每个 5 个元素子集。我正在将它移植到 GPU，现在我已经准备好了它的初始版本。为了加快速度，我想从本地内存加载数据，这是有限的(例如 32KB)并且可以容纳 100 个中的 20 个输入元素。所以我必须以某种方式划分我的工作并生成块组合。现在这是困难的部分，如何做到这一点。很可能我必须首先加载 20 个元素的数据，然后对这 20 个元素的 5 个元素子集进行计算。在此之后，我将不得不用新的替换它们中的一些(或全部)并为它们执行计算，然后冲洗并重复。你能告诉我我应该如何在本地内存中选择替换元素，以避免重复工作吗？到目前为止，我得出的结论是，我必须一次更换至少 16 个，以避免重复工作问题。

编辑:这是从 5 个元素中生成 2 个元素组合的示例。以下是所有可能情况的完整列表:

1, 2
1, 3
1, 4
1, 5
2, 3
2, 4
2, 5
3, 4
3, 5
4, 5

GPU 上的本地内存是有限的 - 假设它只能容纳 3 个元素。所以我必须以某种方式将我的问题划分为生成 3 个元素中的 2 个元素的组合。我必须多次重复这个，直到我从上面的列表中得到所有组合。作为第一步，我可以将元素 1、2、3 加载到本地内存中，因此我将获得以下组合: 
1, 2
1, 3
2, 3

现在我必须加载另一组元素并计算它们的组合。它可以是 1、4、5。它将产生以下组合: 
1, 4
1, 5
4, 5

另一方面，设置 1, 2, 4 无效 - 它会导致重复组合: 
1, 2 // duplicate
1, 4 // ok, new
2, 4 // ok, new

在这一步之后，还有 4 个组合要生成(列表如下)。算法必须能够从 3 个元素中生成另一个 2 元素组合，并以某种方式处理最后(第 10 个)组合。 
2, 4
2, 5
3, 4
3, 5

通过以这种方式拆分工作，我将能够使用只能容纳其中一部分的有限本地内存来处理原始输入集的所有组合。

最佳答案

说例如你有 100 个元素，你可以在内存中保存 20 个，你需要所有 5 个元素的组合，其中有 C(100,5) = 75,287,520。
为了能够生成所有组合，每个 5 个元素的组合都必须在某个时间点在内存中。这可以通过将元素分成 20/5 = 4 个元素的组来完成；输入中有 25 个这样的组，C(25,5) = 53,130 个组的组合。
对于每个组的组合，我们将首先从五个组中的每一个中生成一个元素的组合；这给了我们 53,130 x 45 = 54,405,120 个独特的组合。
我们现在有了每个元素来自不同组的组合，即分区 [1,1,1,1,1]。我们仍然需要找到分区 [2,1,1,1]、[2,2,1]、[3,1,1]、[3,2] 和 [4,1] 的组合。最简单的方法是在单独的阶段执行此操作，但最快的方法当然是将这些合并到 [1,1,1,1,1] 的第一阶段，因为我们将永远需要在第一阶段的某个时刻加载到内存中。
对于分区 [2,1,1,1]，我们将依次加载每个组作为具有 2 个元素的组，然后从其余 24 个组中加载 3 个组的每个组合，并从每个组中取出一个元素。这将需要 25 x C(24,3) = 50,600 个步骤，每个步骤产生 C(4,2) x 43 = 384 个组合，或总共 19,430,400 个。
像 [2,2,1] 这样的分区有点不同，因为我们将依次加载每个组作为具有 2 个元素的第一组，但只有在它之后的组作为具有 2 个元素的第二组，以便避免重复。然后对于其中的每一个，我们将加载其他 23 个组中的每一个以获得最终元素。这将需要 C(25,2)/2 x 23 = 6,900 个步骤，每个步骤产生 C(4,2) x C(4,2) x C(4,1) = 144 个组合，总共 993,600 个。
分区 [3,1,1] 需要 25 x C(24,2) = 25 x 276 = 6,900 个步骤，每个步骤产生 C(4,3) x 42 = 64 个组合，总共 441,600 个。
分区 [3,2] 需要 25 x 24 = 600 个步骤，每个步骤产生 C(4,3) x C(4,2) = 24 个组合，总共 14,400 个。
分区 [4,1] 需要 25 x 24 = 600 个步骤，每个步骤产生 C(4,4) x C(4,1) = 4 个组合，总共 2,400 个。
所以我们总共有:

[1,1,1,1,1] -> 54,405,120
[2,1,1,1]   -> 19,430,400
[2,2,1]     ->    993,600
[3,1,1]     ->    441,600
[3,2]       ->     14,400
[4,1]       ->      2,400
               ----------
               75,287,520 combinations
正如您会注意到的，分区 [3,2] 和 [4,1] 都需要两组的每种组合，因此它们可以轻松集成到一个阶段。当然，如果将它们全部集成到 [1,1,1,1,1] 的第一阶段，则只需将 53,130 个组组合加载到内存中，这是绝对最小值。
(如果在每一步只将一组新元素加载到内存中会更快，而不是按字典顺序遍历组的组合，请查看 this answer 。)

不同阶段的整合
遍历分区 [1,1,1,1,1] 的所有组组合的最简单方法是将组 1 到 21 加载为组 A，然后将 A 之后的所有组直到 22 作为组 B，之后的所有组B组23人为C组，C组24人为D组，D组25人为E组。 
 A  B  C  D  E
 1  2  3  4  5    <- ABCDE
 1  2  3  4  6    <- ABCDE
...
 1  2  3  4 25    <- ABCDE
 1  2  3  5  6    <- ABCDE
...
 1  2  3 24 25    <- ABCDE
 1  2  4  5  6    <- ABCDE
...
 1  2 23 24 25    <- ABCDE
 1  3  4  5  6    <- ABCDE
...
 1 22 23 24 25    <- ABCDE
 2  3  4  5  6    <- ABCDE
...
21 22 23 24 25    <- ABCDE
可以通过取[2,1,1,1]、[1,2,1,1]、[1,1,2,1]和[1,1,1,2]元素来整合四部分的分区来自四组的这些组合: 
 A  B  C  D  E
 1  2  3  4  5    <- ABCD ABCE ABDE ACDE BCDE
 1  2  3  4  6    <- ABCE ABDE ACDE BCDE
 ...        
 1  2  3  4 25    <- ABCE ABDE ACDE BCDE
 1  2  3  5  6    <- ABDE ACDE BCDE
 ...        
 1  2  3 24 25    <- ABDE ACDE BCDE
 1  2  4  5  6    <- ACDE BCDE
...
 1  2 23 24 25    <- ACDE BCDE
 1  3  4  5  6    <- BCDE
...
 1 22 23 24 25    <- BCDE
 2  3  4  5  6    <- none
...
21 22 23 24 25    <- none
三个部分的分区可以通过取[2,2,1]、[2,1,2]、[1,2,2]、[3,1,1]、[1,3,1]和[1,1,3] 来自这些三组组合的元素: 
 A  B  C  D  E
 1  2  3  4  5    <- ABC ABD ACD BCD ABE ACE BCE ADE BDE CDE
 1  2  3  4  6    <- ABE ACE BCE ADE BDE CDE
...
 1  2  3  4 25    <- ABE ACE BCE ADE BDE CDE
 1  2  3  5  6    <- ADE BDE CDE
...     
 1  2  3 24 25    <- ADE BDE CDE
 1  2  4  5  6    <- CDE
...
 1  2 23 24 25    <- CDE
 1  3  4  5  6    <- none
...
21 22 23 24 25    <- none
可以通过从以下两组组合中获取 [2,3]、[3,2]、[4,1] 和 [1,4] 元素来整合具有两部分的分区: 
 A  B  C  D  E
 1  2  3  4  5    <- AB AC BC AD BD CD AE BE CE DE
 1  2  3  4  6    <- AE BE CE DE
...
 1  2  3  4 25    <- AE BE CE DE
 1  2  3  5  6    <- DE
...
 1  2  3 24 25    <- DE
 1  2  4  5  6    <- none
...
21 22 23 24 25    <- none

一般情况
有e个元素，m个元素可以加载到内存中，你想要k个元素的所有组合。使用 k 组大小为 g = m/k。
生成 k 的所有分区，部分限制为大小 g: 
[1,1,1 ... 1] [2,1,1 ... 1] [2,2,1 ... 1] ... [k]        (if k <= g)
[1,1,1 ... 1] [2,1,1 ... 1] [2,2,1 ... 1] ... [g,k-g]    (if k > g)
对于其中的每一个，生成所有唯一的排列，例如: 
[3,2,2,1] -> [3,2,2,1] [3,2,1,2] [3,1,2,2]
             [2,3,2,1] [2,3,1,2] [1,3,2,2]
             [2,2,3,1] [2,1,3,2] [1,2,3,2]
             [2,2,1,3] [2,1,2,3] [1,2,2,3]
对每个部分的排列进行排序，例如: 
k:   [1,1,1 ... 1]
k-1: [2,1 ... 1] [1,2 ... 1] ... [1,1 ... 2]
...
2:   [g,k-g] [k-g,g]
将前 k 个组加载到内存中，例如: 
A  B  C  D  E  F
1  2  3  4  5  6
对于分区 p 的每个长度，生成每组大小为 p 的组，例如: 
p=k:   ABCDEF                                 C(k,k)   sets
p=k-1: ABCDE ABCDF ABCEF ABDEF ACDEF BCDEF    C(k,k-1) sets
p=k-2: ABCD ABCE ABCF ABDE ABDF ... CDEF      C(k,k-2) sets
...
p=2:   AB AC AD AE AF BC BD BE BF ... EF      C(k,2)   sets
对于这些集合中的每一个，生成具有相应部分数量的分区的组合，例如: 
p=k-1: ABCDE [2,1,1,1,1] -> [a,a,b,c,d,e]    C(g,2)*C(g,1)^4 combinations
             [1,2,1,1,1] -> [a,b,b,c,d,e]
             [1,1,2,1,1] -> [a,b,c,c,d,e]
             [1,1,1,2,1] -> [a,b,c,d,d,e]
             [1,1,1,1,2] -> [a,b,c,d,e,e]
       ABCDE [2,1,1,1,1] -> [a,a,b,c,d,f]
             [1,2,1,1,1] -> [a,b,b,c,d,f]
             [1,1,2,1,1] -> [a,b,c,c,d,f]
             [1,1,1,2,1] -> [a,b,c,d,d,f]
             [1,1,1,1,2] -> [a,b,c,d,f,f]
       ...
       BCDEF [2,1,1,1,1] -> [b,b,c,d,e,f]
             [1,2,1,1,1] -> [b,c,c,d,e,f]
             [1,1,2,1,1] -> [b,c,d,d,e,f]
             [1,1,1,2,1] -> [b,c,d,e,e,f]
             [1,1,1,1,2] -> [b,c,d,e,f,f]
从集合列表中，删除不包含最后一组 (F) 的集合: 
p=k:   ABCDEF
p=k-1: ABCDF ABCEF ABDEF ACDEF BCDEF
p=k-2: ABCF ABDF ABEF ACDF ACEF ADEF BCDF BCEF BDEF CDEF
...
p=2:   AF BF CF DF EF
将下一组直到 e/g 作为组 F 加载到内存中，例如: 
A  B  C  D  E  F
1  2  3  4  5  7
...
1  2  3  4  5 e/g
同样，对于这些中的每一个，以及对于每个集合，生成具有相应部分数量的分区的组合。
从集合列表中删除不包含最后两个组 (EF) 的集合: 
p=k:   ABCDEF
p=k-1: ABCEF ABDEF ACDEF BCDEF
p=k-2: ABEF ACEF ADEF BCEF BDEF CDEF
...
p=2:   EF
将直到 e/g-1 的下一组作为 E 组加载到内存中，对于其中的每一个，将 E 到 e/g 之后的组作为 F 组加载到内存中，例如: 
A    B    C    D    E    F
1    2    3    4    6    7
...
1    2    3    4  e/g-1 e/g
同样，对于这些中的每一个，以及对于每个集合，生成具有相应部分数量的分区的组合。
从集合列表中删除不包含最后三个组 (DEF) 的集合: 
p=k:   ABCDEF
p=k-1: ABDEF ACDEF BCDEF
p=k-2: ADEF BDEF CDEF
...
p=2:   none
将下一组直到 e/g-2 作为组 D 加载到内存中，对于每个组，将 D 到 e/g-1 之后的组加载到内存中作为 E 组，对于每个组，将组加载到内存中在 E 到 e/g 之后作为组 F 进入内存，例如: 
A     B     C     D     E     F
1     2     3     5     6     7
...
1     2     3   e/g-2 e/g-1  e/g
同样，对于这些中的每一个，以及对于每个集合，生成具有相应部分数量的分区的组合。
依此类推，直到您达到: 
  A     B     C     D     E     F
e/g-5 e/g-4 e/g-3 e/g-2 e/g-1  e/g
只有: 
p=k:   ABCDEF

21,9,3 的运行

number of elements: e = 21
elements: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]
size of combinations: k = 3 elements
size of memory: m = 9 elements


准备工作: 
number of groups in memory: 3 (k)  
group size: g = m/k = 3 elements  
number of groups: e/g = 7  
groups: 1:[1,2,3] 2:[4,5,6] 3:[7,8,9] 4:[10,11,12] 5:[13,14,15] 6:[16,17,18] 7:[19,20,21]  
number of element sets loaded into memory: C(e/g,k) = C(7,3) = 35  
partitions of k with max part g: [1,1,1] [2,1] [3]  
permutations: 3:{[1,1,1]} 2:{[1,2],[2,1]} 1:{[3]}  
group sets: 3:{[A,B,C]} 2:{[A,B],[A,C],[B,C]} 1:{[A],[B],[C]}
阶段1: 
group sets: 3:{[A,B,C]} 2:{[A,B],[A,C],[B,C]} 1:{[A],[B],[C]}  (all)

A B C
1 2 3 -> elements in memory: [1,2,3] [4,5,6] [7,8,9] -> 84 combinations

3: [1,1,1]:[A,B,C] -> [a,b,c] -> [1,4,7] [1,4,8] [1,4,9] [1,5,7] [1,5,8] [1,5,9] [1,6,7] [1,6,8] [1,6,9]
                                 [2,4,7] [2,4,8] [2,4,9] [2,5,7] [2,5,8] [2,5,9] [2,6,7] [2,6,8] [2,6,9]
                                 [3,4,7] [3,4,8] [3,4,9] [3,5,7] [3,5,8] [3,5,9] [3,6,7] [3,6,8] [3,6,9]

2: [1,2]:[A,B] -> [a,b,b] -> [1,4,5] [1,4,6] [1,5,6] [2,4,5] [2,4,6] [2,5,6] [3,4,5] [3,4,6] [3,5,6]
   [1,2]:[A,C] -> [a,c,c] -> [1,7,8] [1,7,9] [1,8,9] [2,7,8] [2,7,9] [2,8,9] [3,7,8] [3,7,9] [3,8,9]
   [1,2]:[B,C] -> [b,c,c] -> [4,7,8] [4,7,9] [4,8,9] [5,7,8] [5,7,9] [5,8,9] [6,7,8] [6,7,9] [6,8,9]
   [2,1]:[A,B] -> [a,a,b] -> [1,2,4] [1,3,4] [2,3,4] [1,2,5] [1,3,5] [2,3,5] [1,2,6] [1,3,6] [2,3,6]
   [2,1]:[A,C] -> [a,a,c] -> [1,2,7] [1,3,7] [2,3,7] [1,2,8] [1,3,8] [2,3,8] [1,2,9] [1,3,9] [2,3,9]
   [2,1]:[B,C] -> [b,b,c] -> [4,5,7] [4,6,7] [5,6,7] [4,5,8] [4,6,8] [5,6,8] [4,5,9] [4,6,9] [5,6,9]

1: [3]:[A] -> [a,a,a] -> [1,2,3]
   [3]:[B] -> [b,b,b] -> [4,5,6]
   [3]:[C] -> [c,c,c] -> [7,8,9]
阶段2: 
group sets: 3:{[A,B,C]} 2:{[A,C],[B,C]} 1:{[C]}  (sets without C removed)

A B C
1 2 4 -> elements in memory: [1,2,3] [4,5,6] [10,11,12] -> 64 combinations

3: [1,1,1]:[A,B,C] -> [a,b,c] -> [1,4,10] [1,4,11] [1,4,12] [1,5,10] [1,5,11] [1,5,12] [1,6,10] [1,6,11] [1,6,12]
                                 [2,4,10] [2,4,11] [2,4,12] [2,5,10] [2,5,11] [2,5,12] [2,6,10] [2,6,11] [2,6,12]
                                 [3,4,10] [3,4,11] [3,4,12] [3,5,10] [3,5,11] [3,5,12] [3,6,10] [3,6,11] [3,6,12]

2: [1,2]:[A,C] -> [a,c,c] -> [1,10,11] [1,10,12] [1,11,12] [2,10,11] [2,10,12] [2,11,12] [3,10,11] [3,10,12] [3,11,12]
   [1,2]:[B,C] -> [b,c,c] -> [4,10,11] [4,10,12] [4,11,12] [5,10,11] [5,10,12] [5,11,12] [6,10,11] [6,10,12] [6,11,12]
   [2,1]:[A,C] -> [a,a,c] -> [1,2,10] [1,3,10] [2,3,10] [1,2,11] [1,3,11] [2,3,11] [1,2,12] [1,3,12] [2,3,12]
   [2,1]:[B,C] -> [b,b,c] -> [4,5,10] [4,6,10] [5,6,10] [4,5,11] [4,6,11] [5,6,11] [4,5,12] [4,6,12] [5,6,12]

1: [3]:[C] -> [c,c,c] -> [10,11,12]

A B C
1 2 5 -> elements in memory: [1,2,3] [4,5,6] [13,14,15] -> 64 combinations
1 2 6 -> elements in memory: [1,2,3] [4,5,6] [16,17,18] -> 64 combinations
1 2 7 -> elements in memory: [1,2,3] [4,5,6] [19,20,21] -> 64 combinations
第 3 阶段: 
group sets: 3:{[A,B,C]} 2:{[B,C]}  (sets without B removed)

A B C
1 3 4 -> elements in memory: [1,2,3] [7,8,9] [10,11,12] -> 45 combinations

3: [1,1,1]:[A,B,C] -> [a,b,c] -> [1,7,10] [1,7,11] [1,7,12] [1,8,10] [1,8,11] [1,8,12] [1,9,10] [1,9,11] [1,9,12]
                                 [2,7,10] [2,7,11] [2,7,12] [2,8,10] [2,8,11] [2,8,12] [2,9,10] [2,9,11] [2,9,12]
                                 [3,7,10] [3,7,11] [3,7,12] [3,8,10] [3,8,11] [3,8,12] [3,9,10] [3,9,11] [3,9,12]

2: [1,2]:[B,C] -> [b,c,c] -> [7,10,11] [7,10,12] [7,11,12] [8,10,11] [8,10,12] [8,11,12] [9,10,11] [9,10,12] [9,11,12]
   [2,1]:[B,C] -> [b,b,c] -> [7,8,10] [7,9,10] [8,9,10] [7,8,11] [7,9,11] [8,9,11] [7,8,12] [7,9,12] [8,9,12]

A B C
1 3 5 -> elements in memory: [1,2,3] [7,8,9] [13,14,15] -> 45 combinations
1 3 6 -> elements in memory: [1,2,3] [7,8,9] [16,17,18] -> 45 combinations
1 3 7 -> elements in memory: [1,2,3] [7,8,9] [19,20,21] -> 45 combinations
1 4 5 -> elements in memory: [1,2,3] [7,8,9] [13,14,15] -> 45 combinations
1 4 6 -> elements in memory: [1,2,3] [7,8,9] [16,17,18] -> 45 combinations
1 4 7 -> elements in memory: [1,2,3] [7,8,9] [19,20,21] -> 45 combinations
1 5 6 -> elements in memory: [1,2,3] [7,8,9] [16,17,18] -> 45 combinations
1 5 7 -> elements in memory: [1,2,3] [7,8,9] [19,20,21] -> 45 combinations
1 6 7 -> elements in memory: [1,2,3] [7,8,9] [19,20,21] -> 45 combinations
第 4 阶段: 
group sets: 3:{[A,B,C]}  (sets without A removed)

A B C
2 3 4 -> elements in memory: [4,5,6] [7,8,9] [10,11,12]       -> 27 combinations

3: [1,1,1]:[A,B,C] -> [a,b,c] -> [4,7,10] [4,7,11] [4,7,12] [4,8,10] [4,8,11] [4,8,12] [4,9,10] [4,9,11] [4,9,12]
                                 [5,7,10] [5,7,11] [5,7,12] [5,8,10] [5,8,11] [5,8,12] [5,9,10] [5,9,11] [5,9,12]
                                 [6,7,10] [6,7,11] [6,7,12] [6,8,10] [6,8,11] [6,8,12] [6,9,10] [6,9,11] [6,9,12]

A B C
2 3 5 -> elements in memory: [4,5,6] [7,8,9] [13,14,15]       -> 27 combinations
2 3 6 -> elements in memory: [4,5,6] [7,8,9] [16,17,18]       -> 27 combinations
2 3 7 -> elements in memory: [4,5,6] [7,8,9] [19,20,21]       -> 27 combinations
2 4 5 -> elements in memory: [4,5,6] [10,11,12] [13,14,15]    -> 27 combinations
2 4 6 -> elements in memory: [4,5,6] [10,11,12] [16,17,18]    -> 27 combinations
2 4 7 -> elements in memory: [4,5,6] [10,11,12] [19,20,21]    -> 27 combinations
2 5 6 -> elements in memory: [4,5,6] [13,14,15] [16,17,18]    -> 27 combinations
2 5 7 -> elements in memory: [4,5,6] [13,14,15] [19,20,21]    -> 27 combinations
2 6 7 -> elements in memory: [4,5,6] [16,17,18] [19,20,21]    -> 27 combinations
3 4 5 -> elements in memory: [7,8,9] [10,11,12] [13,14,15]    -> 27 combinations
3 4 6 -> elements in memory: [7,8,9] [10,11,12] [16,17,18]    -> 27 combinations
3 4 7 -> elements in memory: [7,8,9] [10,11,12] [19,20,21]    -> 27 combinations
3 5 6 -> elements in memory: [7,8,9] [13,14,15] [16,17,18]    -> 27 combinations
3 5 7 -> elements in memory: [7,8,9] [13,14,15] [19,20,21]    -> 27 combinations
3 6 7 -> elements in memory: [7,8,9] [16,17,18] [19,20,21]    -> 27 combinations
4 5 6 -> elements in memory: [10,11,12] [13,14,15] [16,17,18] -> 27 combinations
4 5 7 -> elements in memory: [10,11,12] [13,14,15] [19,20,21] -> 27 combinations
4 6 7 -> elements in memory: [10,11,12] [16,17,18] [19,20,21] -> 27 combinations
5 6 7 -> elements in memory: [13,14,15] [16,17,18] [19,20,21] -> 27 combinations
结果: 
Phase 1:      84 =   84 combinations
Phase 2:  4 x 64 =  256 combinations
Phase 3: 10 x 45 =  450 combinations
Phase 4: 20 x 27 =  540 combinations
                   ----
                   1330 combinations = C(21,3)

关于algorithm - 如何生成 block 中的组合，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46635137/

26 4 0
文章推荐： php mail() 在 IIS 6 中不起作用
文章推荐： hadoop - 错误:hbase:meta表不一致
文章推荐： hadoop - Hive 2.1.1版本是否支持数据库重命名？
文章推荐： python - Pyre2 比内置 re 模块慢？
行者123
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com