¿Cómo son las matrices y los hash los mapas de tiempo constante en su acceso?

Question

Específicamente: dado un hash (o un índice de matriz), ¿cómo llega la máquina a los datos en tiempo constante?

Me parece que incluso pasar por todas las otras ubicaciones de memoria (o lo que sea) tomaría una cantidad de tiempo igual al número de ubicaciones pasadas (tiempo tan lineal). Un compañero de trabajo ha intentado explicarme esto valientemente, pero tuvo que darse por vencido cuando llegamos a los circuitos.

Ejemplo:

my_array = new array(:size => 20) 
my_array[20] = "foo" 
my_array[20] # "foo" 

acceso de "foo" en la posición 20 es constante porque sabemos qué cubeta "foo" está en ¿Cómo hemos mágicamente llegar a ese cubo sin pasar a todos los demás en el camino. ? Para llegar a la casa # 20 en un bloque, igual tendría que pasar por el otro 19 ...

Answer 1

¿Cómo hemos mágicamente llegar a eso balde sin pasar a todos los demás en el camino?

"Nosotros" no "vamos" a la cubeta en absoluto. La forma en que la memoria RAM funciona físicamente es más como transmitir el número de la cubeta en un canal en el que todos los cubos escuchan, y aquel a quien se llamó el número le enviará su contenido.

Los cálculos ocurren en la CPU. En teoría, la CPU tiene la misma "distancia" de todas las ubicaciones de memoria (en la práctica no lo es, debido al almacenamiento en caché, lo que puede tener un gran impacto en el rendimiento).

Si desea los detalles arenosos, lea "What every programmer should know about memory".

Answer 2

Luego, para comprenderlo, debe observar cómo se organiza y se accede a la memoria. Puede que tenga que ver la forma en que funciona address decoder. El caso es que NO tienes que pasar por todas las otras direcciones para llegar a la que deseas en la memoria. En realidad puedes saltar al que quieras. De lo contrario, nuestras computadoras serían realmente muy lentas.

Answer 3

A diferencia de una máquina turing, que tendría que acceder a la memoria secuencialmente, las computadoras usan memoria de acceso aleatorio, o RAM, lo que significa que si saben dónde comienza la matriz y saben que quieren acceder al 20 elemento de la matriz, saber qué parte de la memoria mirar.

Es menos como conducir por una calle y más como elegir la ranura de correo correcta para su apartamento en un buzón compartido.

Answer 4

2 cosas son importantes:

1. my_array tiene información de en qué lugar de la memoria del ordenador debe saltar para obtener esta matriz.
2. índice * sizeof type se compensa desde el principio de la matriz.

1 + 2 = O (1) donde los datos se pueden encontrar

Answer 5

Big O no funciona así. Se supone que es una medida de la cantidad de recursos computacionales que utiliza un algoritmo y una función en particular. No está destinado a medir la cantidad de memoria utilizada y si estás hablando de recorrer esa memoria, todavía es un tiempo constante. Si necesito encontrar la segunda ranura de una matriz, es cuestión de agregar una compensación a un puntero. Ahora, si tengo una estructura de árbol y quiero encontrar un nodo particular, ahora está hablando de O (log n) porque no lo encuentra en la primera pasada. En promedio se necesita O (log n) para encontrar ese nodo.

Answer 6

Discutamos esto en términos de C/C++; hay algunas cosas adicionales para saber acerca de las matrices de C#, pero no es realmente relevante al punto.

Dado un conjunto de valores enteros de 16 bits:

short[5] myArray = {1,2,3,4,5}; 

Lo que realmente sucedió es que el ordenador ha asignado un bloque de espacio en la memoria. Este bloque de memoria está reservado para esa matriz, es exactamente el tamaño necesario para mantener la matriz completa (en nuestro caso 16 * 5 == 80 bits == 10 bytes), y es contigua. Estos hechos son dados; si alguna o ninguna de ellas es verdadera en su entorno en un momento dado, generalmente corre el riesgo de que su programa se bloquee debido a un acceso vialoation.

Por lo tanto, dada esta estructura, lo que la variable myArray realmente es, detrás de las escenas, es la dirección de memoria del inicio del bloque de memoria. Esto también es, convenientemente, el comienzo del primer elemento. Cada elemento adicional se alinea en la memoria inmediatamente después del primero, en orden. El bloque de memoria asignada para myArray podría tener este aspecto:

00000000000000010000000000000010000000000000001100000000000001000000000000000101 
^    ^   ^   ^   ^
myArray([0]) myArray[1]  myArray[2]  myArray[3]  myArray[4] 

Se considera una operación constante de tiempo para acceder a una dirección de memoria y leer un número constante de bytes. Como en la figura anterior, puede obtener la dirección de memoria para cada uno si conoce tres cosas; el inicio del bloque de memoria, el tamaño de la memoria de cada elemento y el índice del elemento que desea. Por lo tanto, cuando se pide myArray[3] en su código, esa petición se convierte en una dirección de memoria mediante la siguiente ecuación:

myArray[3] == &myArray+sizeof(short)*3; 

Por lo tanto, con un cálculo en tiempo constante, que ha encontrado la dirección de memoria del cuarto elemento (índice 3), y con otra operación de tiempo constante (o al menos así se considera, la complejidad real del acceso es un detalle de hardware y lo suficientemente rápido como para que no le importe) puede leer esa memoria. Esto es, si alguna vez se preguntó, por qué los índices de colecciones en la mayoría de los lenguajes de estilo C comienzan en cero; el primer elemento de la matriz comienza en la ubicación de la matriz en sí, sin desplazamiento (sizeof (cualquier cosa) * 0 == 0)

En C#, hay dos diferencias notables. Las matrices C# tienen información de encabezado que es útil para el CLR. La cabecera es lo primero en el bloque de memoria, y el tamaño de esta cabecera es constante y conocida, por lo que la ecuación de abordar tiene sólo una diferencia clave:

myArray[3] == &myArray+headerSize+sizeof(short)*3; 

C# no permite hacer referencia a la memoria directamente en su gestión entorno, pero el tiempo de ejecución en sí utilizará algo como esto para realizar el acceso a memoria fuera del montón.

Lo segundo, que es común para la mayoría de los sabores de C/C++ también, es que ciertos tipos siempre se tratan "por referencia". Todo lo que tiene que usar la palabra clave new para crear es un tipo de referencia (y hay algunos objetos, como cadenas, que también son tipos de referencia aunque parezcan tipos de valores en el código). Un tipo de referencia, cuando se crea una instancia, se coloca en la memoria, no se mueve y generalmente no se copia. Cualquier variable que represente ese objeto es, por lo tanto, detrás de escena, solo la dirección de memoria del objeto en la memoria. Las matrices son tipos de referencia (recuerde que myArray era solo una dirección de memoria). Las matrices de tipos de referencia son matrices de estas direcciones de memoria, por lo que acceder a un objeto que es un elemento de una matriz es un proceso de dos pasos; primero calcula la dirección de memoria del elemento en la matriz y la obtiene.Esa es otra dirección de memoria, que es la ubicación del objeto real (o al menos sus datos mutables, cómo los tipos compuestos están estructurados en la memoria es un conjunto de otros gusanos). Esta sigue siendo una operación de tiempo constante; solo dos pasos en lugar de uno.