¿Big-O es realmente tan relevante cuando se trabaja en la industria?

En cada entrevista en la que he estado, he sido interrogado sobre el análisis matemático de la complejidad, incluida la notación big-O.

¿Qué tan relevante es el análisis big-O para el desarrollo en la industria? ¿Con qué frecuencia lo usa realmente y qué tan necesario es tener una mentalidad precisa para el problema?

Mi pregunta es, ¿qué tan relevante es esta prueba para el desarrollo en la industria?

Una comprensión sólida de la teoría de la complejidad computacional (por ejemplo, la notación O grande) es esencial para diseñar algoritmos, aplicaciones y sistemas escalables. Dado que la escalabilidad es muy relevante para la informática en la industria, la notación O grande también lo es.

¿Con qué frecuencia lo usa con regularidad y qué tan necesario es tener una mentalidad precisa para el problema?

Depende de lo que quieras decir con "usarlo realmente". Por un lado, nunca hago pruebas formales de complejidad computacional para el software que escribo. Por otro lado, la mayoría de los días tengo que lidiar con aplicaciones donde la escalabilidad es una preocupación potencial, y las decisiones de diseño incluyen la selección de (por ejemplo) tipos de colección apropiados en función de sus características de complejidad.

(No sé si es posible implementar sistemáticamente sistemas escalables sin una comprensión sólida de la teoría de la complejidad. Me inclinaría a pensar que no lo es).

La razón de esto es porque indica escalabilidad .

Un proceso que es O (n ^ 2) escalará peor que uno que sea O (n log n), pero mejor que uno en O (n ^ 3) o incluso O (n!).

Si no conoce las diferencias y cuándo se aplican, es menos adecuado para elegir las implementaciones correctas de funcionalidad, así como para extrapolar el rendimiento de la prueba al rendimiento de producción.

EDITAR: Una comparación de 48n con n ^ 3 de http://www.codinghorror.com/blog/2007/09/everything-is-fast-for-small-n.html (que a su vez es de Programming Pearls)

Depende de lo que estés haciendo.

Para los desarrolladores web (como yo), esto generalmente es muy importante. Desea que las aplicaciones web escalen. Si su aplicación tiene un cuello de botella que escala con O (n ^ 2), y cree que esto está bien, porque su servidor puede manejar 1000 usuarios simultáneos, parece que no necesita preocuparse. La cuestión es que, para manejar solo el doble (lo que es razonablemente probable que ocurra durante la noche), necesitará 4 veces la potencia de cálculo. Idealmente, desea que las aplicaciones web escalen en O (n), porque el hardware es barato en una proporción constante de usuario / servidor constante.

En general, en las aplicaciones, donde tienes 100000 objetos, la gran O vendrá y te comerá. Eres enormemente vulnerable a los picos. Por ejemplo, actualmente estoy trabajando en un juego 3D, que es una aplicación que maneja muchos datos. Además del renderizado, tiene comprobación de colisión, navegación, etc. No puede permitirse seguir el camino obvio. Necesita algoritmos eficientes, necesita mucho almacenamiento en caché para que los menos eficientes se amorticen. Y así.

Por supuesto, si lo que haces es algo así como crear una aplicación móvil al combinar una GUI en un diseñador de interfaz, conectar eso con algunos servicios web y listo, entonces nunca tendrás problemas con la complejidad. Porque los servicios web a los que llamas ya se encargan de ello.

En realidad, nunca apliqué formalmente la regla en mi vida laboral.

Sin embargo, debe estar familiarizado con ese concepto y aplicarlo de manera intuitiva cada vez que diseñe un algoritmo.

La regla es:

Debe estar lo suficientemente familiarizado con la notación O para poder determinar, para una tarea determinada, si es necesario calcularla formalmente, o si es suficiente para evaluarla intuitivamente, o si puede omitirla por completo. Al igual que muchos otros conceptos matemáticos básicos.

Bueno, quizás una pequeña historia te aclare por qué ES DEFINITIVAMENTE necesario:

En un proyecto en el que he estado trabajando, había un programa responsable de imprimir todo tipo de documentos (etiquetas, listas de selección, etc.). Este programa constaba de dos partes, una que leía todos los datos necesarios de la base de datos y los escribía en un archivo de estilo .ini, y otra parte que lee esos archivos y los completa en las plantillas. Esto funcionó razonablemente bien para etiquetas y listas pequeñas (con solo unos pocos campos) pero funcionó durante casi 10 minutos cuando tuvo que imprimir una lista "grande" de ~ 20 páginas. Debido a que el acceso a estos archivos ini dio como resultado tiempos de acceso O (n²), n es el número de campos para imprimir.

Si los programadores originales de este programa hubieran entendido la notación O, nunca lo habrían hecho de esa manera. Reemplazar esa estupidez con una tabla hash lo hizo muuuucho más rápido.

El rendimiento de Big-O es importante, pero se ha internalizado en gran medida.

El rendimiento Big-O de ordenar y buscar no importa, porque las personas generalmente usan los suministrados por el sistema, y ​​serán tan buenos como puedan (dado que deben ser generalmente útiles). Existen estructuras de datos que son más eficientes para diferentes cosas, pero por lo general se pueden seleccionar según principios generales (y generalmente están integrados en lenguajes modernos). Hay una cierta sensación de algoritmos que escalan o no.

El resultado es que los problemas formales rara vez surgen en la práctica, pero la práctica se basa en los mismos principios.

En mi humilde opinión, muchos programas informáticos dejan a muchos estudiantes vagando por la maleza. Estos programas nunca comunican el panorama general de qué se trata la ciencia de la computación. Los estudiantes ingresan a la industria, lidiando con la forma de aplicar los conceptos que han aprendido, con poca información sobre cómo se relacionan con el mundo real.

Yo diría que el corazón de la ciencia de la computación es la capacidad de razonar sobre la computación. Y aprende varios métodos y técnicas para hacer esto, y los aplica a problemas abstractos, que son primitivas prototípicas que se encuentran en muchos problemas del mundo real. El truco es detectar estas primitivas prototípicas en el mundo real, y luego razonar sobre cosas como la corrección, la complejidad, el tiempo, etc., que, puede estar de acuerdo, son cuestiones reales de las que debe preocuparse. Una idea de cómo se comportan las partes, con frecuencia le da una idea de cómo se comporta todo. Y los mismos métodos y técnicas generales también se pueden aplicar al conjunto, solo que no con la misma rigurosidad que se otorga a partes más pequeñas, bien abstractas y bien definidas. Pero al final, la ciencia de la computación, le otorga la capacidad de hacer razonables decisiones sobre cómo organizar su cálculo, con una visión real de cómo se comportará bajo diversas condiciones.

Memo to self !:

Yo y muchos otros nos hacemos esta pregunta regularmente.

Creo que la verdadera razón por la que preguntamos esto es porque nos hemos vuelto perezosos.

Este conocimiento nunca tendrá fecha ni se volverá obsoleto. No puede aplicarlo directamente en el día a día, pero lo usará inconscientemente y tendrá un efecto positivo en sus decisiones de diseño. Un día puede ahorrarle a usted u otros horas y días de codificación.

A medida que las bibliotecas y herramientas de terceros encapsulan más problemas y están disponibles para más y más desarrolladores, necesitará conocer este conocimiento para distinguirse de los demás y ayudar a resolver nuevos problemas.

Realmente no. Básicamente, la única vez que lo pienso es cuando accedo a la base de datos. Por lo general, miro el código y digo "Eso es hacer n + 1 consultas, deberías cambiarlo para hacer solo 1 o 2"

Debido a que todos mis datos se leen de una base de datos y se muestran al usuario, trato de minimizar la cantidad de datos con los que estoy trabajando hasta el punto en que la diferencia entre un algoritmo lineal y un algoritmo O (n ^ 2) es bastante despreciable.

Si hay un problema, lo perfilaremos y lo repararemos más tarde.

Tres preguntas que pones y creo que las respuestas cortas podrían ayudar a los argumentos más largos dados hasta ahora.

¿Qué tan relevante es esta prueba para el desarrollo en la industria?

Depende de la industria.

En cualquier lugar donde la velocidad del código o el espacio del código es un problema, es completamente relevante para la industria involucrada. A menudo, necesita saber cuánto tiempo llevará una rutina o cuánta memoria (en línea / fuera de línea) requerirá.

¿Con qué frecuencia lo usa con frecuencia?

Depende de la industria.

Si el rendimiento y la escala son de poca importancia para el trabajo en cuestión, rara vez, solo cuando hay un grave déficit de rendimiento. Si usted es ingeniero para un sistema crítico altamente utilizado, probablemente todos los días.

¿Qué tan necesario es tener una mentalidad perfeccionada para el problema?

Completamente necesario.

Puede que tenga que usarlo todos los días, o solo en circunstancias extremas; pero a veces será necesario. Preferiblemente durante el diseño antes de que llegue un problema, que perfilar desesperadamente un sistema de asfixia.

Yo diría que es muy frecuente. Por lo general, no demostramos que algo tenga una gran O particular, pero hemos internalizado la idea y memorizado / familiarizado con las garantías de la gran O para estructuras de datos y algoritmos particulares, y elegimos los más rápidos para un uso particular. Es útil tener una biblioteca que esté llena de todas las opciones, como la biblioteca de colecciones de Java o el STL de C ++. Usted utiliza implícita y naturalmente big-O todos los días cuando elige usar una java.util.HashMap( O(1)búsqueda) en lugar de una java.util.TreeMap( O(lg n)búsqueda) y, ciertamente, elige no ejecutar una búsqueda lineal en una java.util.LinkedList( O(n)búsqueda) para algo en lo que no necesita acceso ordenado.

Cuando alguien elige una implementación subóptima y alguien que conoce mejor aparece y ve su código, es parte de nuestro vocabulario corregirlos "su implementación lleva tiempo cuadrático, pero podemos reducirlo al tiempo n-log-n al hacerlo de esta manera en su lugar "tan natural y automáticamente como usaríamos el idioma inglés para pedir una pizza.

si

Es posible que no tenga que hacer análisis formales, pero al menos una comprensión profunda del orden de la complejidad del algoritmo, y cómo comparar dos algoritmos en torno a eso, es fundamental si desea hacer un trabajo no trivial y hacer que salga bien.

He trabajado en dos sistemas diferentes que parecían estar bien en el desarrollo inicial, pero que pusieron el hardware de rodillas en las pruebas de producción, porque alguien usó un algoritmo O (n ^ 2). Y en ambos casos, la solución fue un cambio trivial a un algoritmo O (n).

Probablemente se usa en lugares donde están desarrollando API para consumo. El C ++ STL es una de las pocas API que tiene restricciones de complejidad impuestas en sus algoritmos. Pero para el programador que trabaja todos los días / programador senior / diseñador / arquitecto no se les pasa por la cabeza demasiado.

No me ha parecido tan importante, excepto para comunicar ideas, y trabajo en campos críticos para el rendimiento (trazado de rayos, procesamiento de imágenes y mallas, sistemas de partículas, motores de física, etc.) y he tenido que idear muchos algoritmos y estructuras de datos patentados cuando se trabaja en I + D. En estas áreas, a menudo un puñado de estructuras de datos y algoritmos muy eficientes pueden generar productos innovadores completamente nuevos, mientras que los algoritmos de ayer hacen que los productos existentes queden obsoletos, por lo que siempre se busca hacer las cosas de manera más eficiente. Sin embargo, como advertencia, nunca he publicado ningún documento sobre los algoritmos que ideé. Todos eran propietarios. Si lo hiciera, necesitaría la ayuda de un matemático para formular pruebas, etc.

Sin embargo, en mi opinión, la cantidad de trabajo computacional por iteración es a menudo de interés más inmediato que la escalabilidad del algoritmo a menos que el algoritmo escale realmente mal. Si a alguien se le ocurre una técnica de vanguardia para el trazado de rayos, me interesan más las técnicas computacionales, como la forma en que representan y acceden a los datos, que la complejidad algorítmica porque la escalabilidad razonable ya es un hecho en este escenario competitivo e innovador. No puedes ser competitivo creando algoritmos que no se escalen.

Por supuesto, si está comparando la complejidad cuadrática con la linealidad lineal, esa es una gran diferencia. Pero la mayoría de las personas en mi campo son lo suficientemente competentes como para evitar aplicar un algoritmo de complejidad cuadrática en una entrada épica. Por lo tanto, la escalabilidad a menudo está profundamente implícita, y las preguntas más significativas e interesantes se convierten en: "¿Usó GPGPU? ¿SIMD? ¿Se ejecuta en paralelo? ¿Cómo representó los datos? ¿Lo reorganizó para patrones de acceso amigables para la caché? ¿Cómo? ¿Cuánta memoria toma? ¿Puede manejar este caso con firmeza? ¿Está aplazando cierto procesamiento o lo está haciendo todo de una vez? "

Incluso un algoritmo lineal puede superar a un algoritmo de tiempo lineal si el primero accede a la memoria en un patrón más óptimo, por ejemplo, o es más adecuado para el subprocesamiento múltiple y / o SIMD. A veces, incluso un algoritmo lineal puede superar a un algoritmo logarítmico por estas razones, y los algoritmos de tiempo lineal, naturalmente, superan a los algoritmos logarítmicos para entradas pequeñas.

Entonces, para mí, lo que más importa es lo que algunas personas podrían llamar "microoptimizaciones", como representaciones de datos (diseños de memoria, patrones de acceso con división de campo caliente / frío, etc.), subprocesamiento múltiple, SIMD y, ocasionalmente, GPGPU. En un campo donde todos ya son lo suficientemente competentes como para usar algoritmos decentes y de vanguardia para todo, con nuevos artículos que se publican todo el tiempo, su ventaja competitiva para vencer a los asistentes algorítmicos no proviene de mejoras en la complejidad algorítmica, sino más directa eficiencia computacional.

Mi campo está dominado por matemáticos brillantes, pero no siempre aquellos que conocen el costo computacional de lo que están haciendo o muchos de los trucos de nivel inferior para acelerar el código. Esa suele ser mi ventaja sobre ellos al diseñar algoritmos y estructuras de datos más rápidos y ajustados a pesar de que el mío es mucho menos sofisticado. Estoy jugando a lo que le gusta al hardware, a bits y bytes y haciendo que cada iteración de trabajo sea mucho más barata, incluso si estoy haciendo algunas iteraciones de trabajo más que el algoritmo realmente sofisticado: el trabajo en mi caso es drásticamente más barato. El código que escribo también tiende a ser mucho más simple. Si las personas piensan que las versiones micro optimizadas de algoritmos y estructuras de datos simples son difíciles de entender y mantener,

Como ejemplo básico, se me ocurrió una estructura de cuadrícula simple que terminó superando a un árbol KD en nuestra empresa para la detección de colisiones y la eliminación de puntos redundantes. Mi estúpida cuadrícula cruda era mucho menos sofisticada algorítmicamente y soy mucho más tonto matemáticamente y algorítmicamente que el tipo que implementó el árbol KD con su novedosa forma de encontrar el punto medio, pero simplemente ajusté el uso de memoria de mi cuadrícula y los patrones de acceso y eso fue suficiente para superar algo mucho más sofisticado.

Otra ventaja que tengo que me permite sobrevivir en un campo dominado por personas mucho más inteligentes que yo es comprender realmente cómo funciona el usuario, ya que utilizo el software que desarrollo de la misma manera. Eso me da ideas para algoritmos que realmente se alinean de manera muy inmediata con los intereses del usuario. Como un ejemplo básico allí, la mayoría de las personas intenta acelerar cosas como la detección de colisiones mediante indexación espacial. Hace casi un par de décadas, realicé una simple observación de formación de carrera para modelos orgánicos que, por ejemplo, si un personaje pone sus manos sobre su rostro, una estructura de indexación espacial querría tener que dividir nodos y hacer actualizaciones costosas si el personaje Luego se quitó la mano de la cara. Si, en cambio, particiona en función de los datos de conectividad en lugar de las posiciones de vértice, puede terminar con una estructura jerárquica estable que se actualiza muy rápidamente y nunca necesita dividir o reequilibrar el árbol (solo tiene que actualizar los cuadros delimitadores en cada cuadro de animación) ... cosas como esta: algoritmos de un niño sin una gran base matemática podría surgir si solo entendieran el concepto básico, pero los que eludieron a los matemáticos ya que no pensaban en las cosas de una manera tan cercana a cómo trabajaban los usuarios y pensaban demasiado en las propiedades de la geometría y no en cómo la geometría fue de uso común. Me llevo bastante bien apoyándome más en el conocimiento computacional general y el conocimiento del usuario final que en la magia algorítmica. De todos modos, realmente no me ha parecido tan importante centrarme en la complejidad algorítmica.

Sí, la complejidad importa en la industria. Si termina diseñando algo donde una vía crítica se escala como N al cuadrado (duplicando el número de algo hace que el sistema sea cuatro veces más cargado), alcanzará su cuello de botella de escala mucho más rápido que si tiene algo que escala en N.

Sin embargo, generalmente no se hace como una prueba adecuada y formal de que algo tiene una complejidad dada, por lo que tener una buena intuición de qué complejidad tiene un patrón de operaciones es un buen comienzo.

Nunca pienso en la gran O en una perspectiva matemática, nunca pienso en la gran O, a menos que me lo pidan. Solo veo un algoritmo en mi cabeza, y puedo decir si es malo porque realiza múltiples bucles a través de la memoria para cada N, o si se divide y vence o algo así. Si es necesario, puedo traducir eso a la notación O grande en pocos segundos, pero es más fácil para mí saber cómo funciona el algoritmo / contenedor con la memoria, que pensar en la perspectiva matemática.

Las preguntas que se hacen en las entrevistas están ahí para averiguar si puede explicar las cosas y pensar de manera lógica . El entrevistador también está tratando de averiguar si puede emplear lo que sabe para resolver un problema relacionado .

Todos los que hayan hecho algún estudio valioso de ingeniería de software se habrán topado con "Big O", también para responder una buena pregunta sobre "Big O", también deben comprender algo de las estructuras de datos y algoritmos estándar.

Al entrevistar a un miembro del personal, está buscando a alguien que pueda aprender el trabajo rápidamente, no alguien que ya conozca un conjunto dado de habilidades detalladas, por lo que puede ser muy difícil elegir preguntas que el entrevistador y el entrevistado tengan un entendimiento común. de.

Por lo tanto, las preguntas sobre la "gran O" pueden ser muy relevantes para el proceso de entrevista.

Al menos cada año, durante mi largo tiempo como programador de computadoras, he tenido que arreglar el código que era lento debido a que alguien no entendía las estructuras de datos y algoritmos correctos para usar, pero puede resolver estos problemas sin tener una comprensión detallada de Big O. Sin embargo, las personas que entienden Big O tent no evitan estos problemas en primer lugar.