Explicación del algoritmo de resolución

[Pablo Abratte]

Hola a todos, les comento de nuevo mis reflexiones sobre el problema y la forma que elegí para resolverlo:

Primero que nada busqué una manera de poder manipular los conjuntos sin necesitar moverlos del vector, para eso, creé la siguiente estructura auxiliar.

struct set_data{

int *begin;

unsigned size;

bool repeated;

};

cada elemento de tipo set_data tiene el puntero a la posición en el vector donde comienza el conjunto y su tamaño. La bandera repeated se utiliza en la comparación y es para evitar comparar con un conjunto que ya se sabe que está repetido.

A medida que se van leyendo los datos, se ordena los conjuntos con sort(s.begin, s.begin+size); es decir, se ordenan los elementos del conjunto, esto permite realizar la comparación entre conjuntos de manera más fácil. Notar que el ordenamiento no resulta tan costoso por tratarse de pocos elementos, y que para utilizar sort() fue necesario hacer algunos truquillos sintácticos para sacarse de encima el const del vector.

El mayor problema al comparar los conjuntos es la gran cantidad que hay, por lo cual la fortaleza del algoritmo radica en agrupar los conjuntos según determinada característica para que el numero de comparaciones sea menor. Como característica para agrupar los conjuntos, el tamaño no sirve, porque tendríamos 5 grupos de aproximadamente 20000 elementos cada uno.

La solución que elegí fue utilizar una tabla de dispersión. Ésta es en esencia un vector cuyas posiciones tienen (otro vector) grupos de conjuntos que comparten una característica similar.

Para saber en que grupo va cada conjunto (su valor de hash) se suman todos los elementos y se aplica el resto:

while ((val=*(p++))>=0){

++s.size;

hash+= val;

}

sets[hash%nBins].push_back(s);

donde nBins es la cantidad de cubetas o grupos que existen en la tabla, en este caso 100000. La cantidad de cubetas la elegí por prueba y error, en general cuanto más cubetas, más rápido es el algoritmo porque menos comparaciones hay que hacer. Una cantidad de 1000000 cubetas tampoco tiene sentido porque habría, en promedio, un conjunto por cada cubeta. Como mencionó Mario, la distribución de los conjuntos resultó ser bastante uniforme, lo cual ayuda mucho, y para el valor de nBins = 100000 hay un promedio de 10 conjuntos por posición.

Como los conjuntos en una misma cubeta tienen la misma suma de elementos, sólo ellos son candidatos a ser iguales.

Una vez ubicado cada conjunto en su cubeta correspondiente, se procede a la comparación de los conjuntos de cada cubeta, elemento por elemento (están ordenados). Por supuesto se evita comparar contra conjuntos que tengan distinto tamaño o que ya hayan sido marcados como repetidos.

La función de hash elegida es muy simple y tiene colisiones (puede haber conjuntos distintos que tengan igual valor de hash) y por eso es necesaria la comparación.

Si se encontrara una función de hash que no tuviese colisiones y que no dependiera del orden de los elementos, se podría comparar directamente los valores de hash de cada conjunto.

Respecto a esto, intenté buscar dicha función, y lo mejor que logré fue:

sort(currentSetBegin, currentSetBegin+currentSetSize);

for(int c = 0; c<currentSetSize; c++){

const int &val = *(currentSetBegin+c);

setHash += (val/float(RAND_MAX))*pow(10, c);

} 

Ésta función mapea cada conjunto a un valor real único (no hay colisiones), la función depende de que los elementos estén ordenados, por lo que el sort sigue siendo necesario.

Lamentablemente, está opción tardaba el doble de tiempo que la solución que envié, supongo que por la gran cantidad de tiempo que insume las operaciones con valores flotantes, por lo que la descarte.

En base a esto, una buena función de hash para este caso debería preferentemente:

* no producir colisiones

* no depender del orden de los elementos

* ser rápida de calcular (preferentemente utilizar valores enteros)

Encontrar una función de hash adecuada para cada caso siempre tiene sus complicaciones.

Felicito nuevamente a los organizadores por la iniciativa! La verdad que para mi fue muy productivo (y divertido por supuesto!!!) porque aprendí muchas cosas que ignoraba, así que espero poder transmitirlas y que las puedan aprovechar ustedes también. Espero que se repita pronto y cuenten conmigo para darles una mano en organizar si lo necesitan.

Un abrazo!