Hola, buenas, tengo en un trozo de código de un módulo desarrollado un problema. Tengo tres bucles anidados (correspondientes a las 3 coordenadas del espacio) y mi pregunta es si sabe alguien optimizarlos de alguna manera, ya que tienen de tiempo de ejecución O(n3), y , cuando suble la n a un valor muy alto, la aplicación que usa esa función tarda demasiado e incluso me llega a cascar. Muchas gracias de antemano
A ver, os pongo el código de los bucles pero igual es mucho lío.
for(maComponent i=(maComponent)((readerPosition.GetX()-ratio)/xOverM);
i <= (maComponent)((readerPosition.GetX()+ratio)/xOverM); i++)
{
for(maComponent j=(maComponent)((readerPosition.GetY()-ratio)/yOverN);
j <= (maComponent)((readerPosition.GetY()+ratio)/yOverN); j++)
{
for(maComponent k=(maComponent)((readerPosition.GetZ()-ratio)/zOverL);
k <= (maComponent)((readerPosition.GetZ()+ratio)/zOverL); k++)
{
// función
}
}
}Os explico un poco. El tipo maComponent es un tipo de coordenadas discretas (-1,0,1,2...) y las variables xOverM, yOverN zOverL son un valor proporcional a las coordenadas reales. Ejemplo:
m = 2x n = 5y l = 3z
Entonces, a partir de la posición readerPosition, se tiene que recorrer todos los maComponent que están alrededor suyo a distancia x, que en el código se llama ratio. Si readerPosition es 0,0,0 y ratio es 1, ir desde -1,-1,-1 hasta 1,1,1. La cosa es que si la distancia es 1000, tiene que ir desde -1000, -1000, -1000 hasta 1000, 1000, 1000, y hacer un montón de iteraciones, no se si me explico. Lo que quiero es optimizar de alguna manera eso para que no pete, aunque mirando por ahi y viendo que tengo que recorrer todas las "casillas", supongo que no se puede hacer otra cosa
No lo he entendido bien, pero si de todas formas lo que hace el bucle es buscar algo, al encontrarlo haz un break para que pase al siguiente bucle. Repito, no he entendido lo que hace el bucle xD
Son bucles de búsqueda? Si son bucles de búsqueda usa algoritmos de búsqueda, no iteres las N posiciones.
Si es obligatorio recorrer las N posiciones lo tienes complicado.
Si tu objetivo es recorrer todas las casillas, no hay optimización posible.
Ahora bien, si se trata de encontrar una posición concreta que satisfaga ciertas premisas, hay técnicas de desarrollo(backtracking, PD...) que puede optimizar esa búsqueda.
Al final resulta que es en una búsqueda en un vector que hago dentro de los bucles :palm: . ¿¿Qué algoritmo de búsqueda me recomendáis para vectores STL?? (Descartada la binaria porque el vector no está ordenado :S)
edit: o es mejor igual que lo ordene primero y luego haga binaria?
#4
Aparte te recomiendo una cosa
for(maComponent i=(maComponent)((readerPosition.GetX()-ratio)/xOverM);i <= (maComponent)((readerPosition.GetX()+ratio)/xOverM); i++)
{
for(maComponent j=(maComponent)((readerPosition.GetY()-ratio)/yOverN);
j <= (maComponent)((readerPosition.GetY()+ratio)/yOverN); j++)
{
for(maComponent k=(maComponent)((readerPosition.GetZ()-ratio)/zOverL);
k <= (maComponent)((readerPosition.GetZ()+ratio)/zOverL); k++)
{
Sustituye en la declaración de tus bucles las funciones por valores precalculados, no sé cuantas iteraciones haces, pero lo vas a notar mucho.
maComponent iBreak = (maComponent)((readerPosition.GetX()+ratio)/xOverM);
maComponent iInit = (maComponent)((readerPosition.GetX()-ratio)/xOverM);
para luego hacer
for(maComponent i = iInit; i < iBreak; i++)
Luego, cuando hagas bucles muy intensos, puedes usar la técnica del desenrrollado de bucles, pero con cuidado de que factor de desenrrollado uses, porque si te pasas de factor de desenrrollado, deja de salir rentable (se llenan los registros o mierdas de esas).
==============
También se me ha olvidado comentar que depende de en que orden recorras la matriz que sea que estés recorriendo, puedes ganar velocidad, haz pruebas intercambiando el orden de los bucles a ver.
Por último, si nos pasas el código de la función te podremos ayudar más.
hombre, la optimizacion seria interesante en
// función
ya q se va a ejecutar la tira d veces, y d poco a ahorres un par d ciclos pues eso q t ahorras
y si puedes tb meterle mano a los bucles mas externos, q si ahorras una iteracion ahi tb t ahorras muchisimas llamdas a
// función
No explicas o yo no he entendido bien como tienes montado el vector, pero normalmente si son posiciones consecutivas en un rango dentro de un vector lo más rápido es usar memset.
#8 creo que todavía no me he enterado bien lo que tienes que hacer. Tienes un espacio de coordenadas, que al final viene siendo una matriz de tres dimensiones, y en cada una de esas posiciones, ¿tienes otro vector ademas desordenado ? con lo cual ya la complejidad se nos va a O(n4)
No tienes ninguna forma de discriminar las posiciones de la matriz de tres dimensiones, tienes que recorrer todas las posiciones (x, y, z), y en cada una de estas posiciones buscar un elemento dentro de un vector desordenado. Pufff, es que aunque ordenes el vector para buscar en el, vas a reducir la complejidad de O(n4) a O(n3 log n) Lo cual no creo que te suponga una mejora sustancial.
No se, sin tener el enunciado del problema con todos los datos, es complicado ayudarte mas.
#8 Ordena y busca. La ordenación del vector del STL es el algoritmo más rápido que te vas a encontrar (es decir, usar el Sort del vector del STL).
Estoy seguro que ordenando y buscando vas a mejorar esos tiempos.