Я знаю, что этот вопрос старый, но вот как это можно сделать эффективно.
Весь код в настоящее время в Python, который, я уверен, будет достаточно простым для перевода на C++.
- Вы, вероятно, захотите перейти от использования целого числа для вектор-характеристики к использованию битового массива, поскольку для использования целых чисел потребуется 500 бит (не проблема в Python).
- Не стесняйтесь обновлять никого на C++.
- Распределить к узлам их диапазон комбинаций (
start количество и length для обработки), набор из items, какие комбинации должны быть выбраны и число, k, элементов на выбор.
- Инициализируйте каждый узел, найдя его исходную комбинацию непосредственно с
start и items.
- Запустите каждый узел, запустив его для первой комбинации, затем повторите все остальные комбинации и выполните соответствующую работу.
Для выполнения сделать как вы предлагаете найти н-выбрать-к и разделить его на диапазоны - в вашем случае 500-Выберите-5, как вы сказали, 255244687600 так, для узла = от 0 до 9 вы распространяете:
(start=node*25524468760, length=25524468760, items=items, k=5)
чтобы выполнить можно найти начальную комбинацию непосредственно (без итерации) с использованием системы комбинаторного числа и найти целочисленное представление характеристического вектора комбинации (в который будет использоваться для итерации в) в то же самое время:
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
Целое представление характеристического вектора имеет к битам, установленных в позициях элементов, составляющих комбинацию.
Для выполнения вы можете использовать хак Госпером для итерации к следующей характеристике вектора для комбинации в одной и той же системе счисления (следующую комбинацию, которая будет отображаться в отсортированном списке обратных отсортирован комбинаций относительно 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-выбрать-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
>>>
Не так много опыта в этой области, но это звучит как проблема, которая может быть Google MapReduce применительно к. –
MapReduce здесь не имеет значения, так как речь идет о части «Карта» термина: Как эффективно отображать проблему пространства n-select-k в m частей без необходимости для центрального дистрибьютора. –
@Reyzooti: Отсюда «не много опыта». Счастлив исправить. –