una - vectores en c
¿Por qué el acceso a un elemento en una matriz lleva tiempo constante? (8)
Digamos que tengo una matriz como:
int a [] = {4,5,7,10,2,3,6}
cuando accedo a un elemento, como un [3], ¿qué sucede realmente detrás de la escena? ¿Por qué muchos libros de algoritmos (como el libro Cormen ...) dicen que lleva un tiempo constante?
(Solo soy un novato en la programación de bajo nivel, así que me gustaría aprender más de ustedes)
"tiempo constante" realmente significa "tiempo que no depende del ''tamaño del problema''". Para el "problema" "sacar algo de un contenedor", el "tamaño del problema" es el tamaño del contenedor.
Acceder a un elemento de matriz requiere básicamente la misma cantidad de tiempo (esto es una simplificación) independientemente del tamaño del contenedor, porque se usa un conjunto fijo de pasos para recuperar el elemento: se calcula su ubicación en la memoria (esto también es una simplificación). y luego se recupera el valor en esa ubicación en la memoria.
Una lista vinculada, por ejemplo, no puede hacer esto, porque cada enlace indica la ubicación de la siguiente. Para encontrar un elemento, debe trabajar con todos los anteriores; en promedio, trabajará en la mitad del contenedor, por lo que obviamente importa el tamaño del contenedor.
Array es una colección de tipos de datos similares. Entonces, todos los elementos tomarán la misma cantidad de memoria. Por lo tanto, si conoce la dirección base de la matriz y el tipo de datos que contiene, puede obtener fácilmente la matriz Array [i] en tiempo constante usando la fórmula que se indica a continuación:
int takes 4 bytes in a 32 bit system.
int array[10];
base address=4000;
location of 7th element:4000+7*4.
array[7]=array[4000+7*4];
Por lo tanto, es claramente visible que puede obtener i-ésimo elemento en tiempo constante si conoce la dirección base y el tipo de datos que contiene. Visite this enlace para obtener más información sobre la estructura de datos de matriz.
La matriz, efectivamente, es conocida por una ubicación de memoria (un puntero). Accediendo a[3] se puede encontrar en tiempo constante, ya que es solo location_of_a + 3 * sizeof (int).
En C, puedes ver esto directamente. Recuerde, a[3] es lo mismo que *(a+3) - que es un poco más claro en términos de lo que está haciendo (desreferenciando el puntero "3 ítems").
Porque las matrices se almacenan en la memoria de forma secuencial. Entonces, cuando accedes a la matriz [3] le estás diciendo a la computadora: "Obtén la dirección de memoria del comienzo de la matriz, luego sume 3, luego accede a ese punto". Como agregar lleva tiempo constante, ¡también lo hace el acceso a la matriz!
Si conocemos la ubicación de la memoria a la que se debe acceder, este acceso es en tiempo constante. En el caso de una matriz, la ubicación de la memoria se calcula utilizando el puntero base, el índice del elemento y el tamaño del elemento. Esto implica la operación de multiplicación y adición, que lleva un tiempo constante en ejecutarse. Por lo tanto, el acceso al elemento dentro de la matriz lleva un tiempo constante.
Una matriz es secuencial, lo que significa que la dirección del siguiente elemento en la matriz está al lado de la actual. Entonces, si desea obtener el quinto elemento de una matriz, calcule la dirección del quinto elemento sumando la dirección base de la matriz con 5. Esta dirección directa ahora se usa directamente para obtener el elemento en esa dirección.
Ahora puede hacer la misma pregunta aquí: "¿Cómo sabe la computadora / accede a la dirección calculada directamente?" Esta es la naturaleza y el principio de la memoria de la computadora (RAM). Si está más interesado en cómo la RAM accede a cualquier dirección en tiempo constante, puede encontrarla en cualquier texto de organización de la computadora o simplemente puede buscarla en Google.
una matriz de 10 variables enteras, con los índices 0 a 9, puede almacenarse como 10 palabras en las direcciones de memoria 2000, 2004, 2008, ... 2036, de modo que el elemento con índice i tenga la dirección 2000 + 4 × i. este proceso toma una multiplicación y una adición, ya que estas dos operaciones toman un tiempo constante. Así que podemos decir que el acceso puede realizarse en tiempo constante.
Para ser completo, "¿a qué estructura se accede en tiempo lineal?" Se accede a una estructura de lista enlazada en tiempo lineal. Para obtener el n elemento tienes que viajar a través de n-1 elementos previos. Ya sabes, como una grabadora o un casete VHS, dónde ir al final de la cinta / VHS tenías que esperar mucho tiempo :-)
Una matriz es más similar a un disco duro: cada punto es accesible en tiempo "constante" :-)
Esta es la razón por la cual la RAM de una computadora se llama RAM: memoria de acceso aleatorio. Puede ir a cualquier ubicación si conoce su dirección sin atravesar toda la memoria antes de esa ubicación.
Algunas personas me dijeron que el acceso a HD no es realmente en tiempo constante (donde por acceso quiero decir "tiempo para ubicar la cabeza y leer un sector de la HD"). Debo decir que no estoy seguro de eso. He buscado en Google y no he encontrado a nadie hablando de eso. SÍ, sé que el tiempo no es lineal, porque todavía se accede aleatoriamente. Al final, si crees que el acceso HD no es lo suficientemente constante para ti (pero entonces, ¿qué es constante? El acceso de la memoria RAM? Teniendo en cuenta la caché, la captura previa, la localización de datos y las optimizaciones del compilador?), Puedes considerar la oración como una matriz es más similar a una unidad de disco USB: cada punto es accesible en tiempo "constante" :-)