16

我有一个问题，我必须分析某些东西的 500C5 组合（255244687600）。将其分布在一个 10 节点集群上，每个集群每秒处理大约 10^6 个组合，这意味着该作业将在大约 7 小时内完成。

我遇到的问题是将 255244687600 组合分布在 10 个节点上。我想为每个节点提供 25524468760，但是我使用的算法只能按顺序生成组合，我希望能够传递一组元素和一系列组合索引，例如 [0 -10^7)、[10^7,2.0 10^7) 等，并让节点自己找出组合。

我目前使用的算法来自以下：

我考虑过使用一个主节点，它枚举每个组合并将工作发送到每个节点。但是，从单个节点迭代组合和来回通信所产生的开销是巨大的，并且随后会导致主节点成为瓶颈。

是否有任何好的组合迭代算法为高效/最佳分布式枚举做好准备？

4

3 回答 3

3

您可能在组合数方面取得了一些成功，它允许您使用简单的算法检索第N 'th ( n /10th) k组合；然后在十个节点中的每一个上运行next_combination算法n / 10 次以进行迭代。

可以在MSDN上找到示例代码（在 C# 中，但对于 C++ 程序员来说非常易读） 。

于 2011-01-15T08:50:54.417 回答
0

从第 n 个开始，每第十个组合让节点号 n 处理一次。

于 2011-01-15T09:09:19.200 回答
0

我知道这个问题很老，但这里是如何有效地完成它。

目前在 Python 中的所有代码，我确信它们很容易转换为 C++。
- 您可能希望从使用整数作为特征向量转为使用位数组，因为使用的整数需要 500 位（在 Python 中不是问题）
- 任何人都可以随时更新到 C++。

  1. start将它们的组合范围（数量和length要处理）、items要从中选择组合的集合以及要选择的项目的数量分配给节点k。
  2. start通过让每个节点直接从和中找到其起始组合来初始化每个节点items。
  3. 通过让每个节点完成第一个组合的工作来运行每个节点，然后迭代其余的组合，并完成相关的工作。

要按照您的建议执行1，找到 n-choose-k 并将其划分为范围 - 在您的情况下 500-Choose-5 是，如您所说， 255244687600 因此，对于 node=0 到 9 您分配：
(start=node*25524468760, length=25524468760, items=items, k=5)

要执行2，您可以使用组合数系统直接（无需迭代）找到起始组合，并同时找到组合特征向量的整数表示（用于3中的迭代）：

def getCombination(index, items, k):
    '''Returns (combination, characteristicVector)
    combination - The single combination, of k elements of items, that would be at
    the provided index if all possible combinations had each been sorted in
    descending order (as defined by the order of items) and then placed in a
    sorted list.
    characteristicVector - an integer with chosen item's bits set.
    '''
    combination = []
    characteristicVector = 0
    n = len(items)
    nCk = 1
    for nMinusI, iPlus1 in zip(range(n, n - k, -1), range(1, k + 1)):
        nCk *= nMinusI
        nCk //= iPlus1
    curIndex = nCk
    for k in range(k, 0, -1):
        nCk *= k
        nCk //= n
        while curIndex - nCk > index:
            curIndex -= nCk
            nCk *= (n - k)
            nCk -= nCk % k
            n -= 1
            nCk //= n
        n -= 1
        combination .append(items[n])
        characteristicVector += 1 << n
    return combination, characteristicVector

特征向量的整数表示在构成组合的项目的位置上设置了 k 位。

要执行3，您可以使用 Gosper 的 hack 迭代到相同数字系统中组合的下一个特征向量（下一个组合将出现在相对于 的反向排序组合的排序列表中items），同时创建组合：

def nextCombination(items, characteristicVector):
    '''Returns the next (combination, characteristicVector).
    combination - The next combination of items that would appear after the
    combination defined by the provided characteristic vector if all possible
    combinations had each been sorted in descending order (as defined by the order
    of items) and then placed in a sorted list.
    characteristicVector - an integer with chosen item's bits set.
    '''
    u = characteristicVector & -characteristicVector
    v = u + characteristicVector
    if v <= 0:
        raise OverflowError("Ran out of integers") # <- ready for C++
    characteristicVector =  v + (((v ^ characteristicVector) // u) >> 2)
    combination = []
    copiedVector = characteristicVector
    index = len(items) - 1
    while copiedVector > 0:
        present, copiedVector = divmod(copiedVector, 1 << index)
        if present:
            combination.append(items[index])
        index -= 1
    return combination, characteristicVector

重复这个length-1时间（因为你已经直接找到了第一个）。

例如：

五个节点处理 7-choose-3 字母：

>>> items = ('A','B','C','D','E','F','G')
>>> k = 3
>>> nodes = 5
>>> n =  len(items)
>>> for nmip1, i in zip(range(n - 1, n - k, -1), range(2, k + 1)):
...     n = n * nmip1 // i
...
>>> for node in range(nodes):
...     length = n // nodes
...     start = node * length
...     print("Node {0} initialised".format(node))
...     combination, cv = getCombination(start, items, k)
...     doWork(combination)
...     for i in range(length-1):
...             combination, cv = nextCombination(items, cv)
...             doWork(combination)
...
Node 0 initialised
Doing work with: C B A
Doing work with: D B A
Doing work with: D C A
Doing work with: D C B
Doing work with: E B A
Doing work with: E C A
Doing work with: E C B
Node 1 initialised
Doing work with: E D A
Doing work with: E D B
Doing work with: E D C
Doing work with: F B A
Doing work with: F C A
Doing work with: F C B
Doing work with: F D A
Node 2 initialised
Doing work with: F D B
Doing work with: F D C
Doing work with: F E A
Doing work with: F E B
Doing work with: F E C
Doing work with: F E D
Doing work with: G B A
Node 3 initialised
Doing work with: G C A
Doing work with: G C B
Doing work with: G D A
Doing work with: G D B
Doing work with: G D C
Doing work with: G E A
Doing work with: G E B
Node 4 initialised
Doing work with: G E C
Doing work with: G E D
Doing work with: G F A
Doing work with: G F B
Doing work with: G F C
Doing work with: G F D
Doing work with: G F E
>>>
于 2016-04-07T14:25:23.277 回答