algorithm - resueltos - teoria de grupos

Algoritmo: ¿existe una forma de reducir mapas para fusionar un grupo de conjuntos eliminando todos los subconjuntos?

Question

El problema es: supongamos que tenemos un grupo de conjuntos: Set(1,2,3) Set(1,2,3,4) Set(4,5,6) Set(1,2,3,4,6) , tenemos que eliminar todos los subconjuntos y finalmente obtener el resultado: Set(4,5,6) Set(1,2,3,4,6) . (Dado que tanto Set(1,2,3) como Set(1,2,3,4) son los subconjuntos de Set(1,2,3,4,6) , ambos se eliminan).

Y supongamos que los elementos del conjunto tienen order , que puede ser Int, Char, etc.

¿Es posible hacerlo de una manera map-reduce?

La razón para hacerlo en una forma de reducir mapas es que a veces el grupo de Conjuntos tiene un tamaño muy grande, lo que hace que no sea posible hacerlo en la memoria de una sola máquina. Así que esperamos hacerlo de una manera que reduzca los mapas, puede que no sea muy eficiente, solo funcione.

Mi problema es:

1. No sé cómo definir una clave para el par clave-valor en el proceso map-reduce para agrupar Sets correctamente.

2. No sé cuándo debe finalizar el proceso, que todos los subconjuntos han sido eliminados.

EDIT:

1. El tamaño de los datos seguirá creciendo en el futuro.

2. La entrada puede ser un grupo de conjuntos o múltiples líneas con cada línea que contiene un grupo de conjuntos. Actualmente la entrada es val data = RDD[Set] , primero hago data.collect() , lo que da como resultado un grupo general de conjuntos. Pero puedo modificar la generación de la entrada en un RDD[Array[Set]] , que me dará múltiples líneas con cada línea que contiene un grupo de conjuntos.

3. Los elementos de cada conjunto se pueden ordenar modificando otras partes del programa.

Answer 1

Como el subconjunto de es una relación transitiva ( prueba ), puede aprovecharlo y diseñar un algoritmo iterativo que elimine subconjuntos en cada iteración.

La lógica es la siguiente:

Mapper :
eliminar subconjuntos locales y emitir solo los superconjuntos. Deje que la clave sea el primer elemento de cada superconjunto.

Reductor :
eliminar subconjuntos locales y emitir solo los superconjuntos.

También podría usar un combinador con la misma lógica.

Cada vez, el número de reductores debería disminuir, hasta que, en la última iteración, se use un solo reductor. De esta forma, puede definir desde el principio el número de iteraciones. Por ejemplo, al establecer inicialmente 8 reductores, y cada vez que use la mitad de ellos en la siguiente iteración, su programa terminará después de 4 iteraciones (8 reductores, luego 4, luego 2 y luego 1). En general, terminará en logn + 1 iteraciones (log base 2), donde n es el número inicial de reductores, por lo que n debería ser una potencia de 2 y, por supuesto, menor que la cantidad de mappers. Si esto se siente restrictivo, puede pensar en disminuciones más drásticas en el número de reductores (por ejemplo, disminución de 1/4 o más).

En cuanto a la elección de la clave, esto puede crear problemas de equilibrio, si, por ejemplo, la mayoría de los conjuntos comienzan con el mismo elemento. Entonces, quizás también podría utilizar otras teclas o definir un particionador para equilibrar mejor la carga. Sin embargo, esta política se asegura de que los conjuntos que sean iguales se eliminen tan pronto como sea posible.

Si tiene MapReduce v.2, podría implementar la lógica antes mencionada así (pseudocódigo):
Mapper:

Set<Set> superSets;

setup() {
    superSets = new HashSet<>();
}     

map(inputSet){
    Set toReplace = null;
    for (Set superSet : superSets) {
        if (superSet.contains(inputSet) {
            return;
        }
        if (inputSet.contains(superSet)) {
            toReplace = superSet;
            break;
        }            
    }
    if (toReplace != null) {
        superSets.remove(toReplace);
    }
    superSets.add(inputSet);
}

close() {
    for (Set superSet : superSets) {
        context.write(superSet.iterator.next(), superSet);
    }
}

Puede usar el mismo código en el reductor y en el combinador.

Como nota final, dudo que MapReduce sea el entorno adecuado para este tipo de cálculos. Quizás Apache Spark o Apache Flink ofrecen algunas mejores alternativas.

Answer 2

Dudo que esto pueda hacerse mediante una técnica tradicional de reducción de mapas, que es esencialmente un método de dividir y vencer. Esto es porque:

• en este problema, cada conjunto debe compararse esencialmente con todos los conjuntos de cardinalidad más grande cuyos elementos mínimo y máximo se encuentran alrededor del mínimo y máximo del conjunto más pequeño.
• a diferencia de la ordenación y otros problemas susceptibles de map-reduce, no tenemos una relación de transitividad, es decir, si A is not-a-subset-of B y B is-not-subset-of C , no podemos hacer ninguna declaración sobre A wrt C

En base a las observaciones anteriores, este problema parece ser similar a la detección de duplicados y hay investigaciones sobre la detección de duplicados, por ejemplo aquí . Técnicas similares funcionarán bien para el problema actual.

Answer 3

Si entiendo:

• su objetivo es detectar y eliminar un subconjunto de conjuntos en un gran conjunto de conjuntos

• también hay conjuntos que se deben gestionar por completo (límite de memoria)

• la estrategia es mapear y reducir (o algún tipo de )

Lo que tengo en cuenta:

• El principal problema es que no puedes manejar todo al mismo tiempo

• El método habitual map / reduce supone dividir datos y tratar cada parte. Esto no se hace totalmente así (porque cada subconjunto puede cruzarse con cada subconjunto).

Si hago algunos cálculos:

• supongamos que tiene un conjunto grande: 1000 000 de 3 a 20 números del 1 al 100. debe comparar 1000 mil millones de parejas de conjuntos

Incluso con 100 000 (10 mil millones), toma demasiadas veces (paré).

Lo que propongo (prueba con 100 000 sets):

1 define un criterio para dividir en más pequeños conjuntos compatibles . Los conjuntos compatibles son paquetes de conjuntos, y usted está seguro de que los subconjuntos de conjuntos están, al menos, en un mismo paquete: entonces está seguro de encontrar subconjuntos que eliminar con ese método. Diga de manera diferente: si el conjunto A es un subconjunto del conjunto B, entonces A y B residirán en uno (o varios) paquetes como ese.

Acabo de tomar: cada subconjunto que contiene un elemento definido (1, 2, 3, ...) => da aproximadamente 11 500 conjuntos con supuestos precedentes. Es razonable comparar (120 000 comparaciones). Lleva 180 segundos en mi máquina y encontró 900 subconjuntos para eliminar.

• tienes que hacerlo 100 veces (luego 18 000 segundos).

• y, por supuesto, puedes encontrar duplicados (pero no demasiados: algunos%, y el gool es eliminar).

2 Al final, es fácil y rápido de aglomerar. El trabajo duplicado es liviano.

3 filtros más grandes:

con un filtro con 2 elementos, reduces a 1475 sets => obtienes aproximadamente 30 sets para eliminar, toma 2-3 segundos

y tienes que hacer eso 10 000

Interés de este método:

• la selección de conjuntos en el criterio es lineal y muy simple. También es hierárico: dividido en un elemento, en un segundo, etc.

• es sin estado: puede filtrar millones de conjuntos. Solo debes conservar el bueno. Cuantos más datos tenga, más filtro tendrá que hacer => la solución es escalable.

• si quieres tratar nubes pequeñas, puedes tomar 3, 4 elementos en común, etc.

• así, puedes extender tu tratamiento entre múltiples máquinas (tantas como tengas).

Al final, debe reconciliar todos sus datos / eliminación.

Esta solución no ahorra mucho tiempo en general (puede hacer cálculos), pero se adapta a la necesidad de dividir el trabajo.

Espero eso ayude.