estructura - modelo transitorio odoo

Generación y orden del conjunto de abajo hacia arriba

Question

Cualquier método sobre cualquier método numérico que conozca que pueda ser relevante, ¡por favor publíquelo aquí!

Fondo

Tengo una matriz de values para cada conjunto, y el índice de cada valor corresponde al conjunto al que está vinculado el valor, por lo tanto, represento un conjunto como un entero, donde los elementos representan la posición del bit, por ejemplo, un conjunto con el elemento uno se representa como ...001 donde 1 es el LSB .

Entonces el conjunto es solo un índice y nunca se almacena, se genera sobre la marcha, es la clave que conduce al índice en la matriz que representa los valores de los conjuntos.

Lo que hago se da un conjunto, es el valor sumado para cualquiera de los subconjuntos disjuntos por pares mayor que el valor para ese conjunto. Por ejemplo, si el conjunto 0111 tiene un valor de 3, donde dos subconjuntos tienen el valor de 0100 = 2 y 0011 = 2 , entonces esta división es más beneficiosa de hacer. Lo hago para todos los subconjuntos del conjunto.

Dado tres agentes y el orden es la representación del número de conjuntos.

val[8] = {0,1,2,4,3,2,4,2} the values is not important, only how they are ordered
0 0 0 0 1 1 1 1 MSB bit representation of the index
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 LSB

La mejor división de 111 es 011 y 100 con una suma de 7. Entonces, para obtener el valor del conjunto que contiene solo el primer elemento, ergo 001, se pone val [1], para establecer con los elementos 1 y 3 (101), usted pone val [5].

Cómo se ordena la matriz de val cuando se agrupa por cardinalidad

val[8] = {0,1,2,3,4,2,4,2}
0 0 0 1 0 1 1 1 MSB bit representation of the index
0 0 1 0 1 0 1 1
0 1 0 0 1 1 0 1 LSB

Aquí tiene que traducir el índice al bin correcto en el array, así se vería así para un conjunto con solo el tercer elemento (100), val [translate (4)]. Piensa en arreglos de tamaño> 2 ^ 25 elementos. Consulte Mejora del acceso a memoria aleatoria cuando se necesita acceso aleatorio para obtener más aclaraciones.

Sin embargo, esto da como resultado un alto orden de acceso aleatorio en la memoria, incluso si los agrupo después de la cardinalidad. Actualmente, agruparlos por cardinalidad y generar un índice es más lento que ordenarlos después del número que representa el conjunto.

La forma en que genero un índice con los conjuntos agrupados por cardinalidad es mediante el uso de triángulos pascales en la memoria constante, como se describe en la respuesta en Determinar la distancia lexicográfica entre dos enteros

Donde se encuentra el valor de los conjuntos cuando se ordena y agrupa por cardinalidad con cuatro agentes

n index 1 2 4 8 3 5 6 9 10 12 7 11 13 14 15
-----------------------------------------------------
MSB 0 0 0 1 | 0 0 0 1 1 1 | 0 1 1 1 | 1
0 0 1 0 | 0 1 1 0 0 1 | 1 0 1 1 | 1
0 1 0 0 | 1 0 1 0 1 0 | 1 1 0 1 | 1
LSB 1 0 0 0 | 1 1 0 1 0 0 | 1 1 1 0 | 1

n índice representa el índice que tendría si no ordenado en cardinalidad. Esto es solo para mostrar dónde se encuentra el valor de cada conjunto.

El conjunto entero representa un índice en la matriz de valores, ya sea a través del índice directo (lo que estoy haciendo actualmente, otorga acceso aleatorio) o mediante una traducción del conjunto a un índice.

La idea

En lugar de dividir un conjunto en subconjuntos, pensé en generar los conjuntos de abajo hacia arriba. Por ejemplo, en lugar de dividir 0111 en todos sus subconjuntos disjuntos por parejas, en algún momento generaría si proviene de los conjuntos {0100,0011},{0010,0101},{0001,0110} .

Cómo y por qué debería funcionar

Digamos que queremos evaluar todas las divisiones de los conjuntos con una cardinalidad de 3, ergo establece 7,11,13,14 . Como la única forma de dividir un conjunto de cardinalidad 3 es mediante la división en conjuntos de cardinalidad 1 y 2, debemos evaluar si la suma de cualquiera de los subconjuntos disjuntos de cardinalidad 1 y 2 es mayor que la unión de esos conjuntos.

Notación de lo que se requiere (puede ser un poco defectuoso):

|C|=n,∀ a,b : a ∪ b = C , a ∩ b ={Ø}, |a|+|b| = n

Entonces al leer los valores usando el acceso de memoria fusionada a cada hilo, para cada subconjunto que forme un conjunto de cardinalidad n, verifique si su valor es mayor que el conjunto formado, de ser así, actualice el valor.

Ejemplo simple, si n = 2 entonces debe leer todos los valores con cardinalidad 1, y hacer todas las combinaciones de esos conjuntos y actualizar en consecuencia. Este ejemplo es fácil ya que todos los conjuntos son disjuntos:

pseudo code for 4 threads, input card1 is pointer to array of sets |s| =1
__shared__ int value[4];
tid = threadIdx.x;
value[tid] = card1[tid]; // coalesced memory access
int thvalue = value[tid]; // holds the value for the thread, to avoid bank conflict
int rvalue[blockDim.x/2]= 0; //holds the sum
int i = blockDim.x;
int x = 0;
//reduction loop that dont generate duplicate sets
for(;i>0;i>>=1) {
if(tid < i) {
x++;
rvalue[x-1] = value[(tid+x)%blockDim.x] + thvalue;
}
}
for(i = 0; i < x; i++) {
int index = getindex(tid,i,1); //gets the index for the set it generated, 1 represent the cardinality
if(output[index] < rvalue[i])
output[index] = rvalue[i];
}

Iteración del ciclo de reducción

Thread set specific for thread first iteration second iteration
0 0001 0001 + 0010 0001 + 0100
1 0010 0010 + 0100 0010 + 1000
2 0100 0100 + 1000 none
3 1000 1000 + 0001 none

Como puede ver, ha obtenido todos los valores para todo el subconjunto que forma los conjuntos de cardinalidad 2.

El problema es, sin embargo, que generar conjuntos de cardinalidad mayores a 2 es más complicado, debido a que no todos los conjuntos son disjuntos. Por ejemplo, 0001 y 0011 no son disjuntos.

Tenga en cuenta que no guardo los juegos en ninguna parte, solo el valor de los conjuntos.

Finalmente

¿Cómo haría para tener esto en cuenta, crear un algoritmo que se lea en la memoria fusionada y generar todos los conjuntos a partir de subconjuntos disjuntos? Sin verificar si los subconjuntos son disjuntos, debería ser completamente determinista.

Por recompensa

El algoritmo debe ser texto descripto con distintos pasos marcados o pseudo código.

Debería probarse con ejemplos que funciona. No es que este algoritmo llegue a n ^ 32 conjuntos, por lo que necesita escalar bien.

Se permite dividir el algoritmo en dos o más instancias, por ejemplo, uno para el número par y uno para impar.

Con mucho gusto me referiré a fuentes sobre la técnica que usas.

El algoritmo debe usar tan pocas asignaciones e instrucciones como sea posible y debe evitar cualquier divergencia. Pero si crees que tienes uno incluso, aunque tienes mucho de esto, intenta y publica, estaré contento con cualquier información.

Si está ordenado de otra manera pero aún funciona como lo he descrito, le insto a que lo publique aquí, cualquier ayuda es realmente útil.

Por favor, pregunte si hay algo poco claro.

TL / DR explicación simple

Tengo una matriz Z con valores, el índice i como en Z[i] representa un conjunto entero, según el orden de Z Los valores se agrupan por cardinalidad y se ordenan mediante permutación lexicográfica binaria -> la posición en la que el valor de los conjuntos es ubicado 1,2,4,3,5,6,7 <- así que uso una función (tengo esta función implementada) para traducir el índice al índice correcto. Ej. Establecer 3-> índice 4.

Al tener los valores para el conjunto agrupados por cardinalidad, lo que quiero es, quiero ver si alguno de los pares de valores disjuntos es mayor que el conjunto que forman.

Eg |a| = 3, |b|+|c| =3, b ∩ c ={Ø}, |b| =1 |a| = 3, |b|+|c| =3, b ∩ c ={Ø}, |b| =1 |a| = 3, |b|+|c| =3, b ∩ c ={Ø}, |b| =1 Entonces, leyendo en X cantidad de valores de tipo b , y X cantidad de valores de tipo c , encuentre todos los subconjuntos disjuntos de c que provienen del tipo a (conjuntos de cardinalidad 3) y obtenga su suma. Continúe hasta que todos los conjuntos hayan sido "generados"

Para referencia

Hamming peso basado en la indexación

Determinar la distancia lexicográfica entre dos enteros

Mejorando el acceso aleatorio a la memoria cuando se necesita acceso aleatorio

Answer 1

No sé si esto te ayudará o no, pero encontré una función de count-all-the-word-in-a-word sin sucursales en Hacker''s Delight que parece que podría ser útil para ayudarte a determinar la cardinalidad de un conjunto:

int pop(unsigned int x) {
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}

En el texto, Warren afirma que la secuencia anterior se puede compilar hasta en 21 instrucciones. Sin embargo, al usar MSVC 2010 en una máquina de desarrollo i7, verifiqué el desmontaje de esta función y descubrí que registraba aproximadamente 22 instrucciones para el cálculo real y 33 instrucciones en total (recuento de operaciones de la pila). En una CPU o GPU moderna, debería ser bastante rápido, ya que no tiene ramificaciones.

Answer 2

Intente explotar la numeración de ternany

Para la terminología estoy llamando "valor" a la función de valoración de su conjunto y "objetivo" a su función objetivo, que es el máximo de la suma de valores sobre cada partición binaria.

Cada división de un número binario B en dos partes disjuntas, L y R, puede representarse por un número ternario C, donde

B = L | R (bitwise OR)
L ^ R = 0 (bitwise XOR)
C[i] = 0 means B[i] = 0 and L[i] = R[i] = 0
C[i] = 1 means B[i] = 1 and L[i] = 1
C[i] = 2 means B[i] = 2 and R[i] = 1

Luego "simplemente" enumere los números del 1 al 3 ** n en ternario: ej. (N = 3): 000, 001, 002, 010, 011, 012, 020, ...

De acuerdo, de hecho, contar eficazmente en ternario no es completamente trivial cuando todo lo que tienes a mano es binario. Pero tengan paciencia conmigo, les explicaré un poco después de revisar el alto nivel de algo ...

Entonces cuentas en ternario en orden, y dado un número ternario C, obtienes L y R - ¿cómo? Te lo explicaré a continuación también, créeme :)

Dado L y R, ahora puede buscar su valoración en L y R y actualizar el objetivo en B: objetivo [B] = máximo (val [L], val [R]).

OK, ese es el algoritmo de alto nivel. No puedo probarlo en tan poco tiempo, pero parece que tiene muy buenas propiedades de localidad de caché. En otras palabras, el valor [L] y el valor [R] tenderán a permanecer en un pequeño número de líneas de caché a la vez. También creo que la mejor apuesta para paralelizar es dividir i en valores módulo 3, valores módulo 9, etc.

conteo ternario eficiente en binario

¿Cómo podemos contar en ternario de manera eficiente? Pruebe lo siguiente: cuente en la base 4 y omita algunos.

En otras palabras, un dígito ternario estará representado por dos bits, y no permitiremos la combinación 11 .

 repr | value
0 0 | 0
0 1 | 1
1 0 | 2
1 1 | *undefined*

Ahora, ¿cómo sabemos de manera eficiente cuándo omitir? Bueno, el patrón de incrementos es bastante fácil de entender:

1 1 2 1 1 2 1 1 6 1 1 2 1 1 2 1 1 6 1 1 2 1 1 2 1 1 22 1 1 2 ...

Mi sugerencia sería precalicular un gran trozo de tamaño con una potencia de 3 (por ejemplo, 3 ** 7 = 2187) y calcular la enésima potencia de 3 sobre la marcha de vez en cuando [sugerencia: está relacionado con los cubos de n ..] .

Entonces comienzas con 00.00.00. Agregas 1 eso es 00.00.01. Agregas 1 eso es 00.00.10. Ahora debe agregar 2 para omitir la combinación 11, que lo deja con 00.01.00. Etc.

cómo obtener L y R desde C

Ahora C en nuestra representación cuaternaria de ternario es en realidad simplemente L y R intercalados. Para recuperar L y R de manera eficiente, puede verificar la respuesta a esta pregunta de S / O o aplicar otros hackeos de twiddling.

idea tardía

En general, no estoy seguro de si realmente hemos estado usando la base 3 o la base 4. Ah, bueno ...

¡Diviértete y buena suerte!