Tenga en cuenta que este es un diagrama 3D. El gradiente representa la “presión” que tienes.
No temas hacer preguntas. ¡Incluso puede terminar notando que el problema tiene grandes fallas!
- ¿Es malo si no entiendo un algoritmo? He estado tratando de entender algunos algoritmos (los recursivos en su mayoría), entiendo la mayoría de ellos, pero no pude entender algunos.
- ¿Para qué sirven las estructuras y algoritmos de datos en el desarrollo de aplicaciones, con ejemplos?
- ¿Cómo podría implementar un gráfico inductivo en Haskell?
- ¿Cuál es el mejor algoritmo de extracción de características para comparar dos imágenes?
- Cómo encontrar el segundo número más pequeño de 3 entradas sin usar la matriz
Una vez me pidieron que codificara un sistema para consultar datos de varias fuentes: CSV, XML, base de datos, servicio de descanso … ¡en una hora!
¡Me dieron dos números de teléfono para preguntas y luego me dejaron solo en una habitación y una computadora!
Yo estaba como “WTF!”. Entonces, saqué un poco de papel y comencé a hacer un pequeño diagrama de acuerdo con las especificaciones. Pensé: “Ah, necesito un lenguaje de consulta, así que pongamos un ‘analizador de idiomas’. Necesito que se analice en una consulta para el medio. Hum, vamos a poner un `QueryAdapter`. ¡Por supuesto, necesito una fuente de datos! ”.
¡Estuve así durante media hora! Luego escribí una pequeña parte del sistema para su validación. Entonces no me vuelvo loco con UML.
Como no sabía si eso cumplía con las expectativas, llamé a la secretaria (uno de los dos números de teléfono) y le pedí que llamara a los entrevistadores por mí.
Luego dije: “Necesito que vengas a la sala para ver mi solución”.
Entraron, vieron pocas líneas de PHP y mis dibujos. Le expliqué el diagrama y las pocas preocupaciones que tenía. La entrevista había terminado: contratada.
Le pregunté por qué no habían encontrado a alguien más y respondieron: “Usted es el primero en ir con diagramas, otros se apresuraron a hacerlo”.
Podría haber estresado como “¡Maldita mierda, no tengo nada funcionando!”. En cambio, dije: “Hum, 1h es muy corto. Hagamos el máximo, no podré completar en ningún caso “. Entonces, estaba realmente relajado y tenía una mente clara como resultado, lo que trajo una solución limpia. (Sí, volví al estrés cuando entraron en la habitación ^^)
Además, la optimización es un tema difícil.
Hace unos días, tuvimos que clasificar 4000000 en clases (rangos).
MySQL no pudo hacerlo bien, así que lo hicimos en memoria en PHP.
Fue muy lento, lo hicimos en Go, fue rápido.
Luego nos dimos cuenta de que la versión Go tenía una optimización en la rutina de clasificación: utilizamos el método de dicotomía porque era parte de la biblioteca estándar y era obvio. ¡Fue el resultado de la pereza!
Entonces, respaldamos el método en PHP. Todavía era pobre aunque un poco mejor.
Nos preguntamos si podríamos hacerlo mejor, así que optimizamos mirando los dos límites y aún usando la dicotomía.
PHP:> 8 GB (memoria); ~ 100% un núcleo; 3 minutos (VS 40 minutos antes de la optimización)
Ir: <10 MB (memoria); ~ 5% hasta 8 núcleos; 30 segundos
Claramente, habíamos elegido el tiempo de “ejecución” como la métrica.
Si elige los 3 parámetros como la métrica, terminará con algo promedio o deficiente.
Además, el triángulo puede verse desde las propiedades del problema:
Estos triángulos le muestran el costo relativo para acercarse a un menor uso de un recurso.
Por lo tanto, debe tener una idea justa de cuánto cuesta cada “movimiento”. No es preciso porque es realmente muy difícil.
Ahora esta parte:
Conozco todas las estructuras de datos básicas, pero no puedo relacionarlas con el problema de codificación y terminar obteniendo la peor solución.
En realidad, grita “Sé solo los nombres y cómo usar las estructuras de datos”.
Entonces, sabes que puedes empujar y saltar en una pila. Ese es un buen comienzo.
Ahora, debes pensar en las propiedades.
Como ejemplo, se puede usar una pila para recordar cosas. En la pila que es invisible está la “pila de llamadas”. Cuando se ejecuta una función, la dirección de retorno y los argumentos se pasan a la pila. Entonces, la función “pop” cada argumento y cuando haya terminado, pop la dirección de retorno y empujar el resultado. (Si alguna)
Debe recordar la acción en orden inverso para muchas cosas, como la navegación en un laberinto, al intentar valores múltiples (rastreo hacia atrás), …
¡Lo que mostré arriba es conocimiento sobre la estructura!
Algunas estructuras son un poco “más duras”. Me gusta Linked List y arrays.
Las matrices son partes contiguas, las Listas vinculadas son nodos que están conectados entre sí.
Tiene consideraciones de tiempo de ejecución:
Agregar una entrada en una lista de Me gusta no es costoso:
- Iterar para encontrar el puesto
- Desvincular el nodo anterior
- Enlace el nodo anterior al valor a agregar
- Enlace el valor que se agregará al siguiente nodo
Agregar una entrada en una matriz es costoso:
- Crecer la matriz
- El espacio es suficiente:
- Agregar una celda
- Copie cada entrada después de N a P + 1
- Copiar nueva entrada en N + 1
- El espacio no es suficiente
- Encuentra espacio lo suficientemente grande
- Crear matriz con una celda adicional
- Copie las primeras entradas N-1
- Copie la nueva entrada
- Copie las entradas después de N-1
Pero el acceso aleatorio se ve muy afectado. En las matrices, es algo así como “base_adr + i * elem_size” para encontrar dónde se encuentra un elemento.
En la lista vinculada, debe mirar cada nodo uno por uno para encontrar “el nex” hasta llegar al índice deseado.
Decimos O (1) y O (n) para acceder.
Lo que debes hacer es elegir una estructura. Como un “árbol”, y anotando sus principales propiedades. Luego, crea algunos escenarios donde sea la mejor y la peor estructura.
Tomará algo de trabajo y dedicación, pero será algo muy bueno para usted.
