Importancia de como recorrer una matriz

Supongamos que tenemos una matriz NxM o (NxN) que esta llena de números aleatorios. Normalmente cuando la recorremos, lo hacemos usando como bucle exterior el recorrido de filas y como bucle interior el recorrido de columnas. Pero afecta en algo si queremos recorrerla de otra forma? Si queremos que el bucle exterior recorra las columnas y el interior las filas? Puede parecer una tontería, pero veréis que no lo és.

Si lanzamos la ejecución de ambos recorridos sobre un mismo código, podremos que el resultado es que, el recorrido haciendo que el bucle exterior sea el de filas y el interior el de columnas (llamemosle recorrido filas-cols) tarda mucho menos que el otro recorrido (llamemosle cols-filas). Por ejemplo cuando es una matriz de 1000×1000

Prueba realizada con Ubuntu 14.04 + openJDK

Filas-Cols tarda entorno a unos 700ms

Cols-Filas tarda entorno a unos 1500ms

Prueba realizada con Windows 10 + Oracle JDK8 (fue más sangrante)

Filas-Cols tarda entorno a unos 150ms

Cols-Filas tarda entorno a unos 8000ms (8s)

Cual es el motivo de tanta diferencia si la matriz es la misma, y no tenemos ninguna condición que haga que salga de la matriz en ninguno de los dos casos? Os dejo el código en Java para que podáis ejecutarlo y ver que no hay trampa.

Dejar un comentario aquí abajo explicando porque creéis que sucede esto.

import java.util.Random;

public class StrangesArrays {
	int MAXcols = 10000;
	int MAXrows = 10000;
	Random rd;
	int[][] MATRIX = new int[MAXrows][MAXcols];
	int cantidad = 0;
	public StrangesArrays() {
		rd = new Random();
		this.initalizeMatrix();		
	}

	public void initalizeMatrix() {
		for (int i=0; i<MAXrows; i++) {
			for (int j=0; j<MAXcols; j++) {
				this.MATRIX[i][j] = this.getRandom();
			}
		}
	}
	public int getRandom() {
		return this.rd.nextInt(200);
	}

	public long recorreFilasColumnas(int value) {
		cantidad = 0;
		long tsStart = System.currentTimeMillis(); 
		long tsStop = 0;
		for (int i=0; i<MAXrows; i++) {
			for (int j=0; j<MAXcols; j++) {
				if ( this.MATRIX[i][j] == value ) { cantidad++; } 
			}
		}
		tsStop = System.currentTimeMillis();
		return (tsStop-tsStart);
	}

	public long recorreColumnasFilas(int value) {
		cantidad = 0;
		long tsStart = System.currentTimeMillis(); 
		long tsStop = 0;
		for (int i=0; i<MAXcols; i++) {
			for (int j=0; j<MAXrows; j++) {
				if ( this.MATRIX[j][i] == value ) { cantidad++; } 
			}
		}
		tsStop = System.currentTimeMillis();
		return (tsStop-tsStart);
	}	
		
	public static void main(String[] args) {
		StrangesArrays test = new StrangesArrays();
		System.out.println("Time outer rows - inner cols: "+test.recorreFilasColumnas(10));
		System.out.println("Time outer cols - inner rows: "+test.recorreColumnasFilas(10));
	}
}

El motivo por el que se llena de valores la matriz y se incrementa un contador cada vez que encontramos un valor que coincide con el pasado por parámetro es para que el compilador NO haga trampas y haga que el ejecutable haya de recorrer la matriz. En el siguiente vídeo podéis ver el funcionamiento y el tiempo que tarda en recorrer la matriz.