Enumeración de combinaciones de manera distribuida

Question

Tengo un problema donde debo analizar combinaciones de 500C5 (255244687600) de algo. Distribuirlo en un clúster de 10 nodos donde cada grupo procesa aproximadamente 10^6 combinaciones por segundo significa que el trabajo estará completo en aproximadamente siete horas.

El problema que tengo es la distribución de las 255244687600 combinaciones sobre los 10 nodos. Me gustaría presentar cada nodo con 25524468760, sin embargo, los algoritmos que estoy usando solo pueden producir las combinaciones secuencialmente, me gustaría poder pasar el conjunto de elementos y un rango de índices de combinación, por ejemplo, [0 -10^7), [10^7,2.0 10^7), etc. y hacen que los nodos mismos determinen las combinaciones.

Los algoritmos que estoy usando en este momento son de lo siguiente:

• pregunta

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

• desbordamiento de pila Efficiently computing vector combinations

He considerado el uso de una nodo maestro, que enumera cada una de las combinaciones y envía trabajo a cada una de las des. Sin embargo, la sobrecarga incurrida al iterar las combinaciones desde un solo nodo y comunicar el trabajo de ida y vuelta es enorme, y posteriormente conducirá a que el nodo maestro se convierta en el cuello de botella.

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

Answer 1

Es posible que tenga algo de éxito con combinatorial numbers, que le permiten recuperar el º N'(n /10a) k: combinación con un algoritmo simple; luego ejecute el algoritmo next_combinationn/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.

Answer 2

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

Answer 3

Sé que esta pregunta es antigua, pero así es cómo se puede hacer de manera eficiente.

Todo el código actualmente en Python que estoy seguro será lo suficientemente fácil de traducir a C++.
- Probablemente quiera pasar de usar un número entero para el vector característico a usar una matriz de bits, ya que los enteros utilizados necesitarán 500 bits (no es un problema en Python)
- No dude en actualizar a C++ a cualquiera.

---

1. Distribuir a los nodos de su gama de combinaciones (start número y length para procesar), el conjunto de items de la que combinaciones son para ser elegido, y el número, k, de artículos a elegir.
2. Inicialice cada nodo haciendo que encuentre su combinación inicial directamente desde start y items.
3. Ejecute cada nodo haciendo que haga el trabajo para la primera combinación, luego repita el resto de sus combinaciones y realice el trabajo asociado.

---

Para realizar hacer como usted sugiere encontrar n-elegir-k y se divide en rangos - en su caso 500-Elija-5 es, como usted ha dicho, 255244687600 así, para el nodo = 0 a 9 que se distribuya:
(start=node*25524468760, length=25524468760, items=items, k=5)

para realizar se puede encontrar la combinación de partida directamente (sin iteración) usando el sistema de numeración combinatoria y encontrar la representación entera de vector característico de la combinación (para ser utilizado para la iteración en) 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 de característica tiene k bits puestos en las posiciones de los elementos que componen la combinación.

Para realizar puede utilizar corte de Gosper para iterar a la siguiente vector característico para la combinación en el mismo sistema de numeración (la siguiente combinación que aparecería en una lista ordenada de combinaciones ordenados inversa en relación a 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 este length-1 veces (ya que has encontrado ya el primero directamente).

---

Por ejemplo:

cinco nodos de procesamiento 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 
>>>