Ich weiß, diese Frage ist alt, aber hier ist, wie es effizient getan werden kann.
Alle Code derzeit in Python, die ich sicher bin, wird einfach genug sein, um in C++ zu übersetzen.
- Sie werden wahrscheinlich von einer Ganzzahl für den Merkmalsvektor zur Verwendung eines Bit-Arrays wechseln wollen, da die verwendeten Ganzzahlen 500 Bits benötigen (in Python kein Problem)
- Fühlen Sie sich frei, auf C++ zu aktualisieren.
- die Knoten ihre Auswahl an Kombinationen (
start Anzahl und length zu verarbeiten), um den Satz von items aus denen Kombinationen verteilen gewählt werden, und die Anzahl, k, die Elemente zu wählen.
- Initialisieren Sie jeden Knoten, indem Sie seine Startkombination direkt von
start und items finden.
- Führen Sie jeden Knoten aus, indem Sie die Arbeit für die erste Kombination ausführen und dann den Rest der Kombinationen durchlaufen und die zugehörige Arbeit ausführen.
Um ausführen tun, wie Sie n-wählen-k vorschlagen finden und es in Bereiche unterteilen - in Ihrem Fall 500-Wählen-5 ist, wie Sie, die 255.244.687.600 so, für den Knoten = 0 bis 9 Sie verteilen:
(start=node*25524468760, length=25524468760, items=items, k=5)
auszuführen Sie die Start-Kombination direkt (ohne Iteration) finden können das kombinatorische Zahlensystem verwenden und die Ganzzahl-Darstellung der charakteristischen Vektors Kombination finden (um für die Iteration verwendet werden, in) zur gleichen Zeit:
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
Die ganzzahlige Darstellung der Kennvektor k Bits in den Positionen der Elemente einstellen, die die Kombination bilden.
Zur Durchführung Sie Gospers Hack verwenden können, um den nächsten charakteristischen Vektor für die Kombination in dem gleichen Zahlensystem (die nächste Kombination, die in einer sortierten Liste des Reverse sortierte Kombinationen in Bezug auf items erscheinen würde) zu durchlaufen und, zur gleichen Zeit, erstellen Sie die Kombination:
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
Wiederholen Sie diese length-1 mal (da Sie bereits die ersten direkt gefunden).
Zum Beispiel:
Fünf Knoten Verarbeitung 7-wählen-3 Buchstaben:
>>> 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
>>>
nicht viel Erfahrung in diesem Bereich, aber es klingt wie ein Problem, dass Google MapReduce sein könnte angewendet. –
MapReduce ist hier irrelevant, da es sich um den "Map" -Teil des Begriffs handelt: Wie kann man ein n-choose-k-Raumproblem effizient in m Teile abbilden, ohne dass ein zentraler Verteiler benötigt wird? –
@Reyzooti: Daher die "nicht viel Erfahrung". Glücklich, aber korrigiert zu werden. –