arrays - tipo - Localidad temporal frente a espacial con matrices

manejo de arrays en java

Question

Estoy un poco confundido sobre los significados de la localidad espacial y temporal. Espero que al verlo con un ejemplo de matriz me ayude a entenderlo mejor.

En un ejemplo como este: A [0] [1], A [0] [2], A [0] [3] .... etc

¿Demuestra esto la localidad temporal? Veo que se accede a la misma fila muchas veces pero en diferentes desplazamientos ... ¿significa esto que se accede a una dirección diferente?

Además, estoy en lo cierto al decir que un ejemplo como este: A [1], A [2], A [3] ... etc.

Demuestra localidad espacial?

Esperemos que alguna aclaración sobre cómo funcionan las localidades temporales y espaciales en código real me ayude a comprenderlas mejor.

Answer 1

Aquí hay un ejemplo de código con localidad:

var sum = 0;
for (i = 0; i < n; i++){
  for(j=0; j < m ; j++){
    sum += a[i][j];
    }
}
return sum;

• Existe una localidad temporal porque se accede a la suma con frecuencia en el bucle. La localidad temporal se explota manteniendo los valores de datos e instrucciones utilizados recientemente en la memoria caché y explotando una jerarquía de caché. O incluso en un registro, no en la memoria en absoluto.

• Existe una localidad espacial porque tenemos una matriz ''a'' y accedemos a cada elemento de la matriz en orden. La localidad espacial generalmente se explota mediante el uso de bloques de caché más grandes e incorporando mecanismos de captación previa (recuperación de elementos de uso anticipado) en la lógica de control de caché.

Answer 2

En palabras simples,

Localidad temporal: el concepto de que un recurso al que se hace referencia en un momento determinado se volverá a hacer referencia en el futuro cercano.

Localidad espacial: el concepto de que la probabilidad de hacer referencia a un recurso es mayor si se hizo referencia a un recurso cercano a él.

Fuente (s): Wikipedia

Answer 3

La localidad espacial y temporal describe dos características diferentes de cómo los programas acceden a los datos (o instrucciones). Wikipedia tiene un buen artículo sobre la localidad de referencia .

Se dice que una secuencia de referencias tiene spatial localidad spatial si las cosas a las que se hace referencia en el tiempo también están cerca en el espacio (direcciones de memoria cercanas, sectores cercanos en un disco, etc.). Se dice que una secuencia tiene temporal localidad temporal si los accesos a la misma cosa se agrupan en el tiempo.

Si un programa accede a todos los elementos de una matriz grande y lo lee una vez y luego pasa al siguiente elemento y no repite el acceso a ninguna ubicación determinada hasta que haya tocado en cualquier otra ubicación, entonces es un caso claro de localidad espacial pero no Localidad temporal . Por otro lado, si un programa pasa tiempo accediendo repetidamente a un subconjunto aleatorio de las ubicaciones en la matriz antes de pasar a otro subconjunto aleatorio, se dice que tiene una localidad temporal pero no una localidad espacial . Un programa bien escrito tendrá estructuras de datos que agrupan cosas a las que se accede, asegurando así la localidad espacial . Si es probable que su programa acceda a B poco después de que acceda a A, entonces A y B deben asignarse cerca de cada uno.

Tu primer ejemplo

A[0][1], A[0][2], A[0][3]

muestra la localidad espacial , las cosas a las que se accede de cerca en el tiempo están cerca del espacio. No muestra la localidad temporal porque no ha accedido a la misma cosa más de una vez.

Tu segundo ejemplo

A[1], A[2], A[3]

También muestra la localidad espacial , pero no la localidad temporal .

Aquí hay un ejemplo que muestra la localidad temporal.

A[1], A[2000], A[1], A[1], A[2000], A[30], A[30], A[2000], A[30], A[2000], A[30], A[4], A[4]

Answer 4

La localidad temporal es el caso especial de la localidad espacial.