Algoritmo para recorrer una matriz desde el centro hacia afuera?

Estoy trabajando en un algoritmo de dividir y vencer (de hecho, uno que se ajusta a la curva de una serie de puntos de entrada). Para la parte 'dividir', necesito calcular un término de error para cada punto, y si el error excede un umbral dado, deseo dividir la curva en ese punto y procesar las secciones izquierda y derecha de la entrada por separado. Un simple bucle hace el truco; pero sería ventajoso para mí comenzar a la mitad de la sección actual y trabajar hacia afuera. (Para aclarar: si encuentro un punto cuyo error es demasiado grande, llamo recursivamente y genero curvas separadas para las secciones izquierda y derecha; si todos los puntos están dentro del umbral, entonces mi curva se ajusta y yo regreso).Algoritmo para recorrer una matriz desde el centro hacia afuera?

Después de un poco de rascarse la cabeza, se me ocurrió esto (los puntos están en una matriz, y la sección actual es de startIndex a endIndex incluido):

int steps = (endIndex+1-startIndex); 
int i = (startIndex+endIndex)>>1; 
int stepdir = 1; 
for(int q=0; q<steps; q++, i+=stepdir*q, stepdir=-stepdir) 
{ 
    // test point i here and return early if error exceeds threshold 
}

En otras palabras, comenzando cerca en el medio, avance un índice, dos atrás, tres adelante, cuatro atrás ... Funciona, y estoy seguro de que es eficiente, pero me parece que debería haber una forma más limpia de hacerlo, en particular, terminé tener que verificar la especificación del lenguaje Java para asegurarse de que las declaraciones en la expresión para la actualización se evaluaron en secuencia (aunque no es un operador de secuencia como lo es en C/C++).

Cualquier idea agradecida. ¿Hay una manera más limpia?

Fuente

2011-07-26 Chris Nash

¿Está utilizando este bucle como parte de una función recursiva? es decir, dividir y llamar recursivamente en cada división. –

Sí ... he editado la pregunta para aclarar. El resultado final es una serie de curvas "simples" unidas en algunos puntos de origen y "lo suficientemente cerca" de las intermedias. –

Esto sería más fácil de leer en mi humilde opinión

for (int q=0; q < steps; q++) { 

    int index = i + (q% 2 == 0 ? q/2 : -(q/2+1)); //index lookup here 
}

Editar: se dio cuenta de un error en la búsqueda por índice

Fuente

2011-07-27 00:03:28 jontro

De acuerdo. Esto hace que sea más evidente que cada índice se visita exactamente una vez y que toda la matriz está cubierta. Gracias. –

¿no visita cero dos veces? – phkahler

Si q == 1 sería index = i + - (0 + 1). Si q == 2 sería index = i + (1). Agregaré corchetes al ejemplo para hacerlo más claro – jontro

Si el corrector de exceso de error es sencillo (por ejemplo, una llamada de función), lo más claro es el de escribe:

int mid = npoints/2; 
for (int i = 0; i <= mid; i++) { 
    if(excess_error(mid + i + 1)) { 
      // divide at mid + i + 1 
    } else if excess_error(mid - i) { 
      // divide at mid - i 
    } 
}

una vez más el código "brecha en XYZ" debería ser una llamada de función, o que se cortan & código pegado.

(no he pensado cuidadosamente sobre casos de esquina, y off-by-one errores, así que tenga cuidado cuando == mitad, pero se obtiene la imagen.)

Fuente

2011-07-27 12:51:09

Tan pronto como encuentre un error que es demasiado grande, salgo del ciclo y vuelvo a repetir las dos mitades ... por lo que la parte 'dividir' está bastante dividida punto variable y salir del bucle. Guardo los resultados del cálculo del error para informes posteriores; por lo que definitivamente vale la pena señalar que el comportamiento común debe implementarse dentro de la llamada de función. –

Ok, entonces save-point and break también es bastante simple, la cantidad de repetición de código sería casi tan mínima como para una llamada de función. –

Aquí es una solución más general para cualquier persona que necesita buscar hacia afuera desde un punto arbitrario (en este ejemplo celda [6] en una matriz de longitud 7).

int arraySize = 7; 
int start = 6; 

for (int i=0; i < arraySize; i++) { 
    int index = (start+((i%2==0)?i/2:arraySize-(i+1)/2))%arraySize; 
    print(index+","); 
} 
exit();

imprime 6,5,0,4,1,3,2,

Fuente

2012-04-16 15:47:42

Algoritmo para recorrer una matriz desde el centro hacia afuera?

Respuesta

Cuestiones relacionadas