performance - little - ¿Utiliza la evaluación de la complejidad de Big-O en el "mundo real"?
big-o notation examples (11)
En la medida en que sé que tres anidados for -loops son probablemente peores que uno anidado for -loop. En otras palabras, lo uso como una referencia de la tripa.
Nunca he calculado un Big-O de un algoritmo fuera de la academia. Si tengo dos formas de abordar un determinado problema, si mi intuición me dice que una tendrá un Big-O más bajo que la otra, probablemente tomaré la más pequeña por instinto, sin más análisis.
Por otro lado, si sé con certeza el tamaño de n que entra en mi algoritmo, y con seguridad sé que es relativamente pequeño (digamos, por debajo de 100 elementos), puedo tomar el más legible (me gusta saber lo que hace mi código, incluso un mes después de que se haya escrito). Después de todo, la diferencia entre las ejecuciones de 100 ^ 2 y 100 ^ 3 es apenas perceptible por el usuario con las computadoras de hoy (hasta que se demuestre lo contrario).
Pero, como otros han señalado, el generador de perfiles tiene la última y definitiva palabra: si el código que escribo se ejecuta lentamente, confío en el generador de perfiles más que en cualquier regla teórica, y corríjalo en consecuencia.
Recientemente, en una entrevista, me hicieron varias preguntas relacionadas con el Big-O de varios algoritmos que surgieron en el curso de las preguntas técnicas. No creo que lo haya hecho muy bien en esto ... En los diez años desde que tomé cursos de programación en los que nos pidieron que calculamos el Big-O de los algoritmos, no tengo una discusión sobre el ''Big-O'' de nada. He trabajado o diseñado. He participado en muchas discusiones con otros miembros del equipo y con los arquitectos con los que he trabajado sobre la complejidad y la velocidad del código, pero nunca formé parte de un equipo que realmente utilizó los cálculos de Big-O en un proyecto real. Las discusiones siempre son "¿existe una forma mejor o más eficiente de hacerlo, dada nuestra comprensión de los datos?" Nunca "¿Cuál es la complejidad de este algoritmo"?
Me preguntaba si la gente realmente tiene discusiones sobre el "Big-O" de su código en la palabra real.
Intento suspender las optimizaciones hasta que los datos de perfil demuestren que son necesarios. Por supuesto, a menos que sea obvio en el momento del diseño, un algoritmo será más eficiente que las otras opciones (sin agregar demasiada complejidad al proyecto).
La notación Big-O es más bien teórica, mientras que en la práctica, está más interesado en los resultados de perfiles reales que le dan un número difícil de cómo es su rendimiento.
Es posible que tenga dos algoritmos de clasificación que, según el libro, tengan los límites superiores O(n^2) y O(nlogn) , pero los resultados de la creación de perfiles pueden mostrar que el más eficiente podría tener cierta sobrecarga (que no se refleja en el límite teórico que encontró) para ello) y para el conjunto de problemas específicos con los que está tratando, puede elegir el algoritmo de clasificación teóricamente menos eficiente.
Conclusión: en la vida real, los resultados de perfilado generalmente tienen prioridad sobre los límites teóricos del tiempo de ejecución.
La respuesta de mi experiencia personal es: No. Probablemente la razón es que solo uso algoritmos y estructuras de datos simples y bien entendidos. Su análisis de complejidad ya está hecho y publicado, hace décadas. Rob Pike explica mejor por qué debemos evitar los algoritmos sofisticados. En resumen, un practicante casi nunca tiene que inventar nuevos algoritmos y, como consecuencia, casi nunca tiene que usar Big-O.
Bueno, eso no significa que no debas dominar Big-O. Un proyecto puede exigir el diseño y análisis de un algoritmo completamente nuevo. Para algunos ejemplos del mundo real, lea las "historias de guerra" en el Manual de diseño de algoritmos de Skiena.
Lo hago todo el tiempo. Cuando tiene que lidiar con números "grandes", generalmente en mi caso: usuarios, filas en la base de datos, códigos de promoción, etc., debe conocer y tener en cuenta el Big-O de sus algoritmos.
Por ejemplo, un algoritmo que genera códigos de promoción aleatorios para la distribución podría utilizarse para generar miles de millones de códigos ... El uso de un algoritmo O (N ^ 2) para generar códigos únicos significa semanas de tiempo de CPU, mientras que una O (N) significa horas .
Otro ejemplo típico son las consultas en código (¡mal!). La gente busca una tabla y luego realiza una consulta para cada fila ... esto lleva el orden a N ^ 2. Por lo general, puede cambiar el código para usar SQL correctamente y obtener órdenes de N o NlogN.
Por lo tanto, en mi experiencia, la creación de perfiles es útil SOLAMENTE DESPUÉS de que se use la clase correcta de algoritmos. Utilizo el perfilado para detectar malos comportamientos, como entender por qué una aplicación "pequeña" vinculada a un número tiene un bajo rendimiento.
No es tanto usarlo, es más que entender las implicaciones.
Hay programadores que no se dan cuenta de las consecuencias de usar un algoritmo de clasificación O (N ^ 2).
Dudo que muchos, aparte de los que trabajan en la academia, usarían el análisis de complejidad Big-O en la ira día a día.
No. No uso la complejidad de Big-O en situaciones del "mundo real".
Mi punto de vista sobre el tema en general es este (quizás esté mal ... pero es solo mi opinión).
La complejidad de Big-O es, en última instancia, comprender cuán eficiente es un algoritmo. Si por experiencia o por otros medios, usted comprende los algoritmos con los que está tratando y puede usar el algoritmo correcto en el lugar correcto, eso es todo lo que importa.
Si conoces este material de Big-O y eres capaz de usarlo correctamente, bien y bien.
Si no sabe hablar de los algos y sus eficiencias de forma matemática (cosas de Big-O), pero sabe lo que realmente importa: el mejor algo para usar en una situación, eso es perfectamente correcto.
Si tampoco lo sabes, es malo.
Sí, lo uso. Y no, a menudo no se "discute", como no discutimos a menudo si "orderCount" o "xyz" es un nombre de variable mejor.
Por lo general, no se sienta ni lo analiza , sino que desarrolla una sensación visceral basada en lo que sabe y, en la mayoría de los casos, puede estimar la complejidad de O sobre la marcha.
Por lo general, pienso por un momento cuando tengo que realizar muchas operaciones de lista. ¿Estoy haciendo algo innecesario de complejidad O(n^2) , que podría haberse hecho en tiempo lineal? ¿Cuántos pases estoy haciendo sobre la lista? No es algo que necesite hacer un análisis formal, pero sin el conocimiento de la notación de gran O, es mucho más difícil de hacer con precisión.
Si desea que su software tenga un rendimiento aceptable en tamaños de entrada más grandes, debe considerar la complejidad de la O grande de sus algoritmos, formal o informalmente. La creación de perfiles es excelente para decirle cómo funciona el programa ahora , pero si está utilizando un algoritmo O(2^n) , su generador de perfiles le dirá que todo está bien siempre que el tamaño de entrada sea pequeño. Y luego su tamaño de entrada crece, y el tiempo de ejecución explota.
La gente suele descartar la notación big-O como "teórica", "inútil" o "menos importante que perfilar". Lo que solo indica que no entienden para qué sirve la complejidad de la O grande. Resuelve un problema diferente que un perfilador. Ambos son esenciales en la escritura de software con buen rendimiento. Pero perfilar es en última instancia una herramienta reactiva . Le indica dónde está su problema, una vez que el problema existe .
La complejidad Big-O le dice de manera proactiva qué partes de su código explotarán si lo ejecuta en entradas más grandes. Un perfilador no puede decirte eso.
Sí, para el código del lado del servidor, un cuello de botella puede significar que no puede escalar, porque obtiene rendimientos decrecientes sin importar cuánto hardware lance un problema.
Dicho esto, a menudo hay otras razones para los problemas de escalabilidad, como el bloqueo en el acceso a archivos y redes, que son mucho más lentos que cualquier computación interna que verá, por lo que la creación de perfiles es más importante que BigO.
Si bien rara vez necesita hacer un análisis profundo de una parte del código, es importante saber qué significa y poder evaluar rápidamente la complejidad del código que está escribiendo y las consecuencias que podría tener.
En el momento del desarrollo, a menudo sientes que es "lo suficientemente bueno". Eh, nadie va a poner más de 100 elementos en esta matriz, ¿verdad? Luego, un día, alguien colocará 1000 elementos en la matriz (confíe en los usuarios: si el código lo permite, uno de ellos lo hará). Y ese algoritmo n ^ 2 que era lo suficientemente bueno ahora es un gran problema de rendimiento.
A veces es útil al revés: si sabe que funcionalmente tiene que realizar n ^ 2 operaciones y la complejidad de su algoritmo es n ^ 3, puede haber algo que pueda hacer para hacerlo n ^ 2. Una vez que sea n ^ 2, tendrás que trabajar en optimizaciones más pequeñas.
Por el contrario, si acaba de escribir un algoritmo de clasificación y descubre que tiene una complejidad lineal, puede estar seguro de que hay un problema con él. (Por supuesto, en la vida real, las ocasiones en las que tiene que escribir su propio algoritmo de clasificación son raras, pero una vez vi a alguien en una entrevista que estaba claramente satisfecho con su algoritmo de clasificación de bucles).
No hace falta n-cuadrado
En mi experiencia, no tienes muchas discusiones al respecto, porque no es necesario discutirlas. En la práctica, en mi experiencia, todo lo que sucede es que descubres que algo es lento y ves que es O (n ^ 2) cuando en realidad podría ser O (n log n) u O (n), y luego vas y cambialo. No hay otra discusión que no sea "eso es n cuadrado, ve a arreglarlo".
Así que sí, en mi experiencia, lo usas con bastante frecuencia, pero solo en el sentido más básico de "disminuir el orden del polinomio", y no en un análisis altamente optimizado de "sí, pero si cambiamos a este algoritmo loco, Incrementaré desde logN hasta el inverso de la función de Ackerman "o alguna de esas tonterías. Cualquier cosa menos que un polinomio, y la teoría sale por la ventana y usted cambia al perfil (por ejemplo, incluso para decidir entre O (n) y O (n log n), medir datos reales).