Conozca sus fundamentos de codificación: las principales diferencias entre conjuntos y matrices

Una pregunta que recibo mucho de mis estudiantes de informática en The Forge es por qué a menudo utilizo conjuntos en lugar de matrices antiguas en los problemas de entrevistas.

Para responder a esa pregunta, debemos comprender las diferencias fundamentales entre un conjunto y una matriz.

Si eres un aprendiz visual y prefieres una explicación en video, aquí tienes un video de 3 minutos que explica la respuesta (aunque con menos profundidad).

Las matrices fueron una de las primeras estructuras de datos que aprendí a usar.

No solo son una estructura de datos fundamental que se utiliza en casi todas las aplicaciones de codificación, sino que también son bastante fáciles de entender.

No fue hasta mucho más tarde en mi carrera de software que me presentaron al primo extraño, pero mágico, de la matriz:

El conjunto.

Los conjuntos son como matrices ... excepto que no lo son.

Recordemos rápidamente cómo funciona una matriz

Matrices:

  • Están ordenados
  • Tienen índices que comienzan en 0
  • Puede contener elementos duplicados
  • Tenga un tiempo de búsqueda O (n) cuando busque un elemento

Sin embargo, los conjuntos se comportan un poco diferente

Conjuntos:

  • Están desordenados (en casi todos los idiomas)
  • Tienen índices hash
  • NO puede contener elementos duplicados
  • Tener un tiempo de búsqueda O (1) al buscar un elemento

Echemos un vistazo más a fondo.

1. Establece Insertar por hash

Los elementos de un conjunto se almacenan de manera bastante diferente a los de una matriz.

La forma en que un conjunto almacena sus elementos es mediante hash.

Supongamos que desea almacenar el carácter "A" en un conjunto y una matriz.

La matriz simplemente buscará el siguiente índice disponible, a menos que se especifique lo contrario, y colocará el elemento en ese índice.

Sin embargo, con el hash, las cosas se ven un poco diferentes.

Cómo funciona el hash

El hash es el acto de tomar la entrada (x), distorsionarla con una función hash específica (h) y obtener una salida final (y).

Básicamente h (x) = (y)

Parece un poco confuso, ¿verdad?

¡No se preocupe! Esto debería aclarar las cosas.

Un ejemplo sencillo de una función hash (h) podría agregar "asdf" al final de su entrada (x).

Si (x) es "A" y agregar "asdf" es (h), la salida (y) sería simplemente la siguiente:

"A" + "asdf" → "Aasdf"

Entonces "Aasdf" sería nuestro (y).

Entonces, ¿cómo usa un conjunto Hashing?

Un conjunto usa hash para decidir dónde almacenar su entrada (x).

En pocas palabras, un conjunto toma su entrada, la hash y la almacena en el índice que coincide con la entrada hash, también conocida como la salida (y).

Ésta es la razón por la que los conjuntos están desordenados en la mayoría de los idiomas.

La indexación de matrices es fácil, de 0 an, por lo que puede recordar fácilmente lo que sigue.

Pero con las complejas funciones de hash que utilizan la mayoría de los compiladores, no se puede encontrar el orden en el que se insertaron los elementos a menos que tenga un mecanismo de indexación secundario.

2. Los juegos no pueden contener duplicados

¡Así es!

Un conjunto solo puede contener elementos únicos.

Al contrario de lo que parece, esto puede ser extremadamente útil en muchas situaciones, incluidas las preguntas de entrevistas de Google.

¿Por qué hace eso, preguntas?

Bueno, ¡por el hash!

Dado que mi función hash (h) seguirá siendo consistente mientras se ejecuta mi programa, ingresar la misma (x) siempre le dará la misma (y).

Eso significa que si trato de insertar una segunda "A", mi función hash generaría la misma dirección que la primera "A", ¡y simplemente la sobrescribirá!

Con una matriz, simplemente agregaría la segunda "A" al siguiente índice disponible.

3. Los conjuntos tienen un tiempo de búsqueda de O (1)

Digamos que tiene una matriz de n elementos, donde n es un número grande, y quiere ver si "A" existía en esa matriz.

Bueno, en el peor de los casos, "A" no existe.

¡Y para averiguarlo, tendrías que recorrer todos los n elementos!

Eso le da a una matriz una complejidad de tiempo de O (n) cuando se trata de buscar un elemento.

Podemos ahorrar mucho tiempo con un Set

Si quisiéramos averiguar si un elemento existe o no en nuestro conjunto, ¡todo lo que tenemos que hacer es hash de ese elemento y verificar el índice!

Recuerde: el índice en el que se almacena un elemento está conectado al elemento en sí.

Por lo tanto, si quisiéramos ver si "A" existía o no en nuestro conjunto, solo tendríamos que aplicar un hash (+ "asdf") y verificar ese índice.

Dado que este proceso siempre requerirá una cantidad constante de operaciones, no importa cuán grande sea el conjunto, tiene una complejidad de tiempo constante.

Eso significa que un conjunto tiene una complejidad temporal de O (1) cuando se trata de buscar un elemento… ¡Lo cual es una gran mejora!

¿Puedes pensar en alguna situación en la que esto sea útil?

Si no puede, consulte esta Pregunta de entrevista de Google donde un conjunto marca la diferencia.

¡Gracias por leer!

.un

PD: para más tutoriales sobre estructuras de datos y algoritmos, y preparación para entrevistas, visite www.TheForge.ca.

¡Ayudamos a los estudiantes y recién graduados a conseguir el trabajo de software de sus sueños!