c++ - Enumerar combinaciones de manera distribuida.

algorithm distributed

Question

Tengo un problema donde debo analizar las combinaciones 500C5 (255244687600) de algo. Distribuyéndolo en un clúster de 10 nodos donde cada clúster procesa aproximadamente 10 ^ 6 combinaciones por segundo significa que el trabajo se completará en aproximadamente siete horas.

El problema que tengo es distribuir las combinaciones 255244687600 en los 10 nodos. Me gustaría presentar cada nodo con 25524468760, sin embargo, los algoritmos que estoy usando solo pueden producir las combinaciones de forma secuencial, me gustaría poder pasar el conjunto de elementos y un rango de indicaciones de combinación, por ejemplo, [0 -10 ^ 7), [10 ^ 7,2.0 10 ^ 7), etc. y haga que los nodos mismos resuelvan las combinaciones.

Los algoritmos que estoy usando en este momento son los siguientes:

• http://howardhinnant.github.io/combinations.html

• Pregunta de desbordamiento de pila Calcula de manera eficiente combinaciones de vectores

He considerado usar un nodo maestro, que enumera cada una de las combinaciones y envía trabajo a cada uno de los nodos. Sin embargo, la sobrecarga en la que se incurre al iterar las combinaciones de un solo nodo y comunicar el trabajo de ida y vuelta es enorme, y posteriormente hará que el nodo maestro se convierta en el cuello de botella.

¿Existe alguna buena combinación de algoritmos de iteración preparados para una enumeración distribuida eficiente / óptima?

Answer 1

Haga que el número de nodo n procese cada décima combinación, comenzando desde el n.

Answer 2

Sé que esta pregunta es antigua, pero aquí es cómo puede hacerse de manera eficiente.

Todo el código actualmente en Python que estoy seguro será bastante fácil de traducir a C ++.
- Probablemente querrá pasar de usar un entero para el vector característico a usar una matriz de bits, ya que los enteros usados ​​necesitarán 500 bits (no es un problema en Python)
- Siéntase libre de actualizar a C ++ a cualquier persona.

1. Distribuya a los nodos su rango de combinaciones (número de start y length a procesar), el conjunto de items entre los cuales se elegirán las combinaciones y el número, k , de elementos a elegir.
2. Inicialice cada nodo haciendo que encuentre su combinación de start directamente desde el start y los items .
3. Ejecute cada nodo haciendo que haga el trabajo de la primera combinación, luego repita el resto de sus combinaciones y realice el trabajo asociado.

Para llevar a cabo 1 haz lo que sugieres, encuentra n-Choose-K y divídelo en rangos; en tu caso, 500-Choose-5 es, como dijiste, 255244687600, entonces, para los nodos = 0 a 9, distribuyes:
(start=node*25524468760, length=25524468760, items=items, k=5)

Para realizar 2 , puede encontrar la combinación inicial directamente (sin iteración) utilizando el sistema numérico combinatorio y encontrar la representación entera del vector característico de la combinación (que se usará para la iteración en 3 ) al mismo tiempo:

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 

La representación entera del vector característico tiene k bits establecidos en las posiciones de los elementos que forman la combinación.

Para realizar 3 , puede usar el truco de Gosper para recorrer el siguiente vector característico de la combinación en el mismo sistema numérico (la siguiente combinación que aparecería en una lista ordenada de combinaciones ordenadas en sentido inverso en relación con los items ) y, al mismo tiempo, crear la combinación:

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

Repita esta length-1 veces (ya que ya encontró la primera directamente).

Por ejemplo:

Cinco nodos procesando 7-elegir-3 letras:

>>> 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
>>>

Answer 3

Puede tener cierto éxito con los números combinatorios , que le permiten recuperar la combinación N ''th ( n / 10th) k con un algoritmo simple; luego ejecute el next_combination algoritmo de next_combination n / 10 veces en cada uno de los diez nodos para iterar.

El código de muestra (en C #, pero bastante legible para un programador de C ++) se puede encontrar en MSDN .