16

何かの 500C5 の組み合わせ (255244687600) を分析しなければならないという問題があります。各クラスターが毎秒約 10^6 の組み合わせを処理する 10 ノードのクラスターに分散すると、ジョブは約 7 時間で完了することになります。

私が抱えている問題は、255244687600 の組み合わせを 10 個のノードに分散させることです。各ノードに 25524468760 を表示したいのですが、使用しているアルゴリズムは組み合わせを順番にしか生成できません。たとえば、[0 -10^7)、[10^7,2.0 10^7) などで、ノード自体に組み合わせを割り出させます。

現在使用しているアルゴリズムは次のとおりです。

各組み合わせを列挙し、各ノードに作業を送信するマスター ノードの使用を検討しました。ただし、1 つのノードから組み合わせを反復し、作業をやり取りするために発生するオーバーヘッドは膨大であり、その後、マスター ノードがボトルネックになることにつながります。

効率的/最適な分散型列挙に適した反復アルゴリズムの組み合わせはありますか?

4

3 に答える 3

3

単純なアルゴリズムでN番目（n / 10番目）のkの組み合わせを取得できる組み合わせ番号である程度の成功を収めることができます。次に、10個のノードのそれぞれでアルゴリズムをn / 10回実行して、反復します。next_combination

サンプルコード（C＃ですが、C ++プログラマーにとっては非常に読みやすいものです）は、MSDNにあります。

于 2011-01-15T08:50:54.417 に答える
0

ノード番号nに、n番目から開始して10番目の組み合わせごとに処理させます。

于 2011-01-15T09:09:19.200 に答える
0

この質問は古いことは知っていますが、効率的に行う方法は次のとおりです。

現在 Python で書かれているすべてのコードは、C++ に簡単に変換できると確信しています。
- 使用される整数は 500 ビットを必要とするため (Python では問題ではありません)、特性ベクトルに整数を使用することから、ビット配列を使用するように移行することをお勧めします
。

  1. start組み合わせの範囲 ( 処理する数 と)、どの組み合わせから選択するかlengthのセット、および選択する項目の数をノードに配布します。itemsk
  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 のハックを使用して、同じ数体系の組み合わせの次の特性ベクトル ( に対して逆に並べ替えられた組み合わせの並べ替えリストに表示される次の組み合わせ) を反復処理し、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 文字を処理する 5 つのノード:

>>> 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 に答える