¿Big O realmente importa?

17

En la academia, el peor de los casos Big O se enseña sobre todo lo demás. En comparación con la complejidad espacial, el análisis de casos normales, la simplicidad sobre la complejidad, etc.

En particular para la programación de juegos y la industria, ¿qué es lo que realmente importa más y por qué?

Las referencias serían muy útiles.

David Young
fuente
Big-O = Optimización. Me llevó un poco descubrir qué era big-0.
AttackingHobo
12
Big-O no es "optimización". Big-O es una forma de análisis que le dice cómo se comportarán los diferentes algoritmos, en términos de eficiencia, a medida que aumenta el número de elementos que actúan. Ver en.wikipedia.org/wiki/Big_O_notation para más detalles.
ZorbaTHut
2
Les puedo asegurar que las personas que crearon octrees y BSP / PVS sabían todo sobre big-O. Al final, lo único que importa es el rendimiento de la aplicación. Pero para llegar allí debe considerar todo tipo de cosas, incluida la complejidad asintótica de los algoritmos que manejan una gran cantidad de datos.
drxzcl
1
Recuerde la regla de cuándo optimizar: 1) No lo haga. 2) (solo expertos) No lo hagas todavía.
zaratustra
Bueno, en primer lugar, Big O puede usarse para espacio o complejidad computacional, por lo que "sobre todo lo demás" no es exactamente cierto. En segundo lugar, Big O suele ser mucho más simple de calcular para algo que el análisis de casos normal, y se usaría como una comprobación mental rápida de si está haciendo algo mal. Si dibujar un sprite toma O (2 ^ n) tiempo, probablemente deberías elegir un algoritmo diferente. Si desea un enfoque más práctico para el diseño de software, busque prácticas SE en lugar de CS. CS es de naturaleza teórica, mientras que SE se basa más en la industria.
Deleter

Respuestas:

25

Al igual que con cualquier otra pregunta sobre "cuál es el único camino verdadero", estas son todas las herramientas en su caja de herramientas y hay casos en los que big-O supera todo y lugares donde no importa (tm).

"Nunca" escribiría un solucionador de física sin preocuparse por big-O. No implementaría un algoritmo de ordenación (para cualquiera de los conjuntos de datos más pequeños) sin preocuparse por ello. Si está escribiendo un juego en red, le preocupará la forma en que el rendimiento y el tráfico de red escalan por usuario.

Puede que no estés tan preocupado por Big-O cuando, bueno, realmente no puedo pensar en un momento, pero estoy seguro de que hay algunos. :) Afortunadamente, la mayoría de las cosas que hacemos en los juegos se escalan linealmente; quieres leer un archivo del disco? Tomará una cantidad de tiempo linealmente proporcional al tamaño del archivo (descontando el factor constante de búsqueda y las posibles ramificaciones del tamaño del sector).

Sin embargo, ¿qué sucede si desea encontrar una entidad específica en la lista de entidades? Esa es una búsqueda lineal cada vez que lo haces. Si necesita encontrar al jugador una vez para cada entidad en el mundo, este enfoque lo matará por todos los juegos menos por los más triviales, e incluso entonces probablemente valga la pena "optimizar" esta búsqueda para que sea un tiempo constante (por ejemplo, almacenar fuera del índice o un puntero al jugador en alguna parte), que le da más tiempo para hacer otras cosas que en realidad son visibles para el jugador.

Sin embargo, supongo que eso lo resume; cada vez que el procesador está haciendo algo que no es directamente representable para el jugador, está perdiendo el tiempo. Maximizar la cantidad de tiempo que el procesador está calculando los datos que se mostrarán al jugador es maximizar el ¡GUAU!Le estás dando al jugador.

dash-tom-bang
fuente
8
Esta. Es importante comprender las características de rendimiento de su código. Nunca se sabe cuándo un diseñador usará algo que haya agregado de una manera que no esperaba, y de repente el fragmento de código que pensó que solo tendría que manejar 5 elementos ahora maneja 5000 y se fija 100 veces por cuadro. ¿Optimizas eso? ¿Puedes? ¿Cuántos son realmente razonables? Un perfil solo le dirá qué tan lento es, no por qué. Conocer la complejidad le dirá si necesita optimizar el código o reemplazarlo con algo diferente.
JasonD
3
Convenido. Las universidades te enseñan el 'Big-O' porque maneja muchos de los problemas que enfrentarás. Cuando te preguntan 'oh, ¿podemos hacer que esto sea infinito en lugar de solo 5? los evaluadores odian la limitación 'es cuando el entrenamiento vale la pena. No deberías decir simplemente 'no, no puedo'. Es vital poder resolver el problema y decir 'sí, puedo'. ¿Tu juego necesita una galaxia de búsqueda? 'No hay problema'. Esos millones de unidades necesitan ser ordenadas? 'No hay problema'. "No estudié lo suficiente" simplemente no es suficiente.
Rushyo
"Puede que no te preocupes tanto por Big-O cuando ..." procesando las teclas de entrada. Heredé un sistema de entrada que tomó medidas para resolver asignaciones de teclas-> acciones en tiempo constante, usando una tabla de búsqueda. Pasarlo a una búsqueda lineal de una matriz de pares (clave, acción) ahorró memoria y no tuvo impacto en el rendimiento, ya que los usuarios rara vez presionan más que unas pocas teclas por cuadro, y la matriz generalmente tiene solo 20-30 elementos de longitud. También nos permite agregar (clave, clave, acción) para acordes.
Joe, claro, aunque esa es una preocupación diferente. ¿Desea O (1) donde el factor constante es alto u O (n) con una 'n' pequeña y un factor constante bajo? Conocer big-O en este caso no es un problema, pero puede ayudarlo a determinar si la solución tiene sentido o no para las circunstancias en las que se utilizará.
dash-tom-bang
13

Mi regla general es que, a menos que seas O (aterrador), tus otros problemas son más pertinentes.

Mi otra regla general es que los datos son el rey. A menos que perfiles tu código con un conjunto de datos realista, solo estás haciendo conjeturas.

Editar: para entrar en un poco más de detalle, su gran O no es tan importante ya que (al menos en mi experiencia) la mayoría de sus conjuntos de datos son relativamente pequeños. Probablemente no le importe su límite superior de rendimiento cuando trabaja con una estructura de datos con menos de unos pocos cientos de elementos. Y si sus listas tienen más de 100k elementos, entonces realmente necesita considerar todos los aspectos de sus algoritmos. Eso, y según mi experiencia, la memoria es más un factor limitante que la velocidad de la CPU. Un algoritmo de acaparamiento de memoria más rápido podría no ser tan bueno como uno más ágil pero más lento dependiendo de sus casos de uso.

Tétrada
fuente
8

Big O importa la mayor parte del tiempo, pero a veces un algoritmo aparentemente "peor" en teoría resulta ser mucho más rápido en la práctica.

Mira un gran ejemplo de Tony Albrecht: http://seven-degrees-of-freedom.blogspot.com/2010/07/question-of-sorts.html

Lo encuentras por todas partes en el desarrollo de juegos donde el número de elementos en la operación es tan grande que un algoritmo muy diferente es más rápido o tan pequeño que un algoritmo más tonto es suficiente (o cabe en el caché tan bien que anula la eficiencia de los mejores algoritmo).

El problema con Big O es que es una designación genérica de complejidad de la tarea y no tiene en cuenta la complejidad del hardware de destino moderno, ni ofrece ninguna idea sobre la sobrecarga del tiempo de configuración.

En muchos casos, la mejor solución óptima es dos pasos. En la práctica, los desarrolladores de juegos tienden a tener algoritmos de O bajos pero equilibrados con el costo en tiempo de desarrollo o depuración. Una vez que tenga una solución razonable, siempre debe observar cómo el hardware maneja la tarea y cómo dejar que el hardware haga más en menos tiempo.

Richard Fabian
fuente
"El problema con Big O" es que las personas parecen olvidar que se trata de una complejidad algorítmica con respecto al rendimiento del wrt en relación con grandes tamaños de conjuntos de datos. En los juegos no (generalmente) alcanzamos esos valores de N, por lo que debemos preocuparnos por las otras piezas del rompecabezas. Sospecho que el ordenamiento de burbujas siempre superará a la clasificación rápida cuando tenga una lista de dos elementos.
dash-tom-bang
7

Cuando estoy de codificación en el motor, estoy a menudo sólo se refiere a un fijo n: Ya tengo una partición espacial limitar el número de objetos que recibe update(), physics()yrender() aproximadamente a las de la pantalla y las áreas circundantes. El tamaño máximo de lote generalmente está bastante bien definido por juego, aunque invariablemente es un poco más grande de lo que has planeado.

En este caso, no estoy tan interesado en big-O como en el multiplicador de factor constante y los términos de orden inferior. Para una función con tiempo de ejecución como a*n^2 + b*n + c(que es O(n^2)), a menudo estoy mucho más preocupado por reducir ay posiblemente eliminar c. Un costo de instalación o desmontaje cpuede ser proporcionalmente grande frente a uno pequeño n.

Sin embargo, esto no quiere decir que big-O (o más particularmente big-theta ) es un gran indicador de olor de código. Vea un O(n^4)lugar, o peor aún, un O(k^n)tiempo geométrico, y es hora de asegurarse de que está considerando otras opciones.

En general, estoy mucho más preocupado por la optimización de Big-O y saltar a través de aros para encontrar algoritmos con Big-O más bajo cuando se trata de herramientas de creación de datos. Si bien el número de objetos en un nivel / área de transmisión en general generalmente está bien definido, el número total de objetos / activos de arte / archivos de configuración / etc. en un juego completo puede no estarlo. También es un número mucho mayor. Incluso ejecutando una marca de datos paralela, seguimos esperando el orden de un minuto (lo sé, quejarse, la creación de datos para consolas puede llevar horas, en su mayoría son pequeños juegos portátiles) para pasar por un jam data-clean && jam dataciclo.

Para dar un ejemplo específico: esto realmente se salió de control con un algoritmo de transmisión de mosaicos de fondo que transmite mosaicos de 8x8 de 256 colores. Es útil compartir búferes de transmisión entre "capas" de fondo, y podríamos tener hasta 6 de ellos en un nivel dado que compartan el mismo búfer. El problema es que estimar el tamaño del búfer necesario se basa en las posibles posiciones de las 6 capas, y si son un ancho / alto / velocidad de desplazamiento del número primo, rápidamente comienza a realizar una búsqueda exhaustiva, que comienza a acercarseO(6^numTiles)- que se encuentra en la categoría "más largo que el universo estará alrededor" en muchos casos. Afortunadamente, la mayoría de los casos son solo de 2 a 3 capas, pero aun así, superamos la media hora de tiempo de ejecución. Por el momento, tomamos muestras de un subconjunto muy pequeño de estas posibilidades, aumentando la granularidad hasta que haya transcurrido una cantidad de tiempo establecida (o hayamos completado la tarea, lo que puede suceder para configuraciones pequeñas de doble capa). Aumentamos un poco esta estimación en función de las estadísticas anteriores de la frecuencia con la que hemos demostrado que estamos equivocados, y luego agregamos un poco de relleno adicional para una buena medida.

Otro ejemplo divertido: en un juego de PC hace un tiempo, el ingeniero principal experimentó durante un tiempo con listas de omisión . La sobrecarga de memoria termina causando más efectos de caché, lo que agrega una especie de multiplicador no constante a todo el asunto, por lo que realmente no son una buena opción para los pequeños n. Pero para listas ordenadas más grandes donde las búsquedas son frecuentes, proporcionan un beneficio.

(A menudo encuentro que el algoritmo ingenuo es mayor-O grande, más rápido en conjuntos de datos más pequeños y más fácil de entender; los más interesantes / complejos (por ejemplo, patricia trie) son más difíciles de entender y mantener para las personas, pero un mayor rendimiento en grandes conjuntos de datos).

leander
fuente
4

Puede ser útil, pero también puede ser irrelevante. Tomemos, por ejemplo, mi juego más reciente, que es una especie de clon de Smash TV. Juego de arriba hacia abajo, los monstruos llegan desde los lados, los disparas.

Ahora hay muchas formas inteligentes de determinar colisiones. Puede usar KDtrees para dividir el espacio para que no esté probando balas contra monstruos que posiblemente no podrían golpear. Y, claro, podría haber sido inteligente, y podría haberlo hecho.

Pero me sentía flojo, así que comparé cada bala con cada monstruo. Incluso en las situaciones más agitadas, el código de colisión estaba usando mucho menos del 10% de la CPU del juego a 60 fps. Big-O: sin importancia.

Del mismo modo, tuve un juego de estilo 4x donde construiste ciudades en islas, y a veces las ciudades se destruían. Podría haber sido inteligente e intentar restar los ingresos de la ciudad destruida de las variables de ingresos. Pero no lo hice. Simplemente borré los ingresos y los volví a calcular desde cero cada vez que algo cambiaba. Totalmente irrelevante en términos de CPU.

Big-O es tan importante en los juegos como lo es en todo lo demás: es decir, completamente sin importancia, hasta que se vuelve crítico.

Ve a escribir un código. Si es demasiado lento, entonces perfílelo.

ZorbaTHut
fuente
3

El análisis Big-O es importante, pero no es lo primero en lo que pensar en el desarrollo de juegos. Como la creación de juegos implicaba mucho código complicado, siempre recomendaría Code Simplicity como primer criterio para un algoritmo. Algoritmos con contabilidad complicada solo te hacen perder el tiempo.

Creo que es muy importante que tu juego siempre se ejecute a 60 fps durante el desarrollo. Cuando te sumerges por debajo de eso, lo primero que haces es ejecutar un generador de perfiles. Una vez que encuentras el cuello de botella, lo atacas. La mayor parte del tiempo necesita hacer cosas que no sean de codificación, como decirle a los diseñadores de niveles que coloquen menos cosas en un área (y les den herramientas para eso).

A veces, en realidad, identifica algún código que debe acelerarse. ¡Esto me parece una ingeniería divertida! Desearía tener más oportunidades para hacer esto. Y, por supuesto, desea iterar cambiando una cosa a la vez y midiendo el rendimiento. Los problemas típicos que encuentro son:

  1. Asegúrese de no llamar a new o malloc cada fotograma (este siempre es el problema n. ° 1)
  2. Reduce el trabajo: menos rayos, menos hombres, etc.
  3. Problemas de tipo de algoritmo Big-O
  4. Coherencia de caché: coloque cosas en matrices en lugar de memoria dispersa
  5. No use STL en modo de depuración. (y siempre quieres que funcione el modo de depuración)
Tod
fuente
2

La notación Big-O es, por definición, complejidad asintótica, es decir, muestra cómo el tiempo escala cuando N (o cualquier variable que tenga) se vuelve "muy" grande. Para repetir el comentario de Tetrad (que subí) "los datos son el rey". Si N es "muy grande" en su situación específica, es importante, si N es "muy pequeño", no importa. La experiencia y la práctica le darán una idea de cómo cuantificar "muy grande" y "muy pequeño".

Obviamente, siempre perfile primero y optimice el último (a menos que esté haciendo un estudio de factibilidad de características).

Crowley9
fuente
1

La importancia de Big-O en su software es O (N 2 ). A medida que N crece, la importancia de tener el algoritmo correcto crece aún más. :)

Kylotan
fuente
¿Eso no depende de la frecuencia con la que se llama ese algoritmo ...?
bobobobo
Hasta cierto grado. Pero si tarda 3 días en ejecutarse, probablemente no importe si solo lo llama una vez. :)
Kylotan
1

Big-O es solo una guía, algo que le dice el rendimiento aproximado que puede esperar de un algoritmo, y cómo debe esperar que el rendimiento se amplíe a medida que aumenta el tamaño del conjunto de datos . Debe recordar dos cosas principales con respecto a Big-O:

1) Si tiene dos algoritmos que en su mayoría hacen lo mismo pero uno tiene una mejor O, probablemente debería elegir ese (obviamente)

2) Big O se preocupa por el análisis asintótico . Big-O solo entra en juego cuando n es grande . Por ejemplo, un algoritmo O (n) puede ser muy similar en rendimiento a uno O (n ^ 2) ... para n pequeño . Si está hablando de un algoritmo que requiere n ^ 2 operaciones por vértice, pero n = 2 o n = 3, entonces no hay mucha diferencia entre un algoritmo O (n ^ 2) (tomando 4 y 9 ops resp) y un O (n) uno (2 y 3 ops resp.). Sin embargo, si n = 9, de repente estás hablando de 81 operaciones para el algoritmo O (n ^ 2) y solo 9 para el O (n) uno, una diferencia más grande, y si n = 100, entonces estás hablando de 100 operaciones frente a 10000, una diferencia mucho mayor.

Por lo tanto, siempre debe considerar Big-O desde ese punto de vista: está destinado a comparar algoritmos que hacen lo mismo en función del rendimiento del peor de los casos a medida que n crece . Las diferencias entre los algoritmos pueden ser prácticamente insignificantes cuando n es muy pequeño.

bobobobo
fuente
0

No tengo referencias, pero Big O es al menos útil para tener en cuenta al analizar un problema y una discusión. Por otro lado, por supuesto, si la versión O (log n) tiene una O más involucrada que la versión O (n), es una comparación discutible. Y como con todo, siempre hay una compensación. La complejidad del espacio podría ser un problema, aunque también podría expresarse en O en general. Análisis de caso normal ... menos, ya que tampoco desea que los valores atípicos aumenten. La simplicidad sobre la complejidad, en mi opinión, es relativamente inútil en el desarrollo del juego, ya que la velocidad es casi siempre un problema, por lo que a menos que la simplicidad conduzca a aceleraciones (pero luego significa que su caso complejo fue incorrecto por las razones equivocadas) la simplicidad tendrá que desaparecer fuera de la ventana a favor de la velocidad. Pero Big O es definitivamente útil,

Kaj
fuente
0

Cuando creas un prototipo de una función de juego o un aspecto de un juego, no debes preocuparte por optimizarlo en absoluto .

En el curso de la creación de prototipos y el aprendizaje de las idiosincrasias de esa funcionalidad, las optimizaciones necesarias serán obvias y tendrán en cuenta el diseño final como la segunda naturaleza ... la mayor parte del tiempo.

No te preocupes.

Steve H
fuente
"Cuando creas un prototipo de una función de juego o un aspecto de un juego, no debes preocuparte por optimizarlo en absoluto". Esto es cierto a veces pero no siempre. Ciertos juegos, como Dead Rising, se basan en una ejecución rápida para hacer posible la mecánica principal del juego, cientos de zombis en tiempo real.
¿Qué porcentaje del desarrollo del juego es la creación de prototipos? Eventualmente quieres enviar algo , ¿verdad?
dash-tom-bang
0

No debería ser el todo y el fin de todo. Pero sí ayuda a resolver problemas obvios que podrían causar problemas de rendimiento; ¿Por qué usar algo en el tiempo O (n ^ 2), cuando puedes hacer lo mismo en el tiempo O (log n)?

Creo que se aplica a los juegos más que la mayoría de las otras industrias, ya que el mercado es el que más notará los problemas de velocidad. A alguien que use un procesador de texto no le importará si hay un retraso de medio segundo para realizar la acción X, pero los jugadores probablemente irán "omg omg game Y es tan lento que lleva años hacer la acción Z".

El pato comunista
fuente
0

En el desarrollo de juegos (y la mayoría de los demás), nos estamos quejando de una operación adicional realizada por ciclo:

for (int i = 0; i < array.length; i ++) { /* ... */ }

vs.

for (int i = 0, l = array.length; i < l; i ++) { /* ... */ }

La mayoría de los juegos modernos tienen física, y encontrarás el problema de simulación de n cuerpos . En un algoritmo ingenuo, es O (n ^ 2), pero hay una optimización que lo hace O (n log n) (pero sacrifica algo de precisión).

Se podría decir que no está programando interacciones de gravedad y partículas, pero ¿qué pasa con el comportamiento del equipo de un ejército (de zombis) donde se mueven dependiendo de otras ubicaciones (en una palabra más específica: enjambre)?

En un algoritmo de detección de colisión convencional, la complejidad del tiempo es O (n ^ 2), como el cuerpo n. Sin embargo, hay una mejor manera: separe el mundo en muchas partes pequeñas para que solo se detecten colisiones dentro de la misma parte. Ver http://www.videotutorialsrock.com/opengl_tutorial/collision_detection/text.php .

Si su juego es programable, NO haga que el guionista escriba O (n ^ 2) (y más) algoritmos de descifrado de números en el guión, como buscar en la bolsa del usuario. Realice una función incorporada en el código en su lugar.

Ming-Tang
fuente
1
Ambos ejemplos de código son O (n). Las discusiones Big-O no tienen nada que ver con "una operación adicional por ciclo", sino más bien "una búsqueda adicional a través de todo por iteración del ciclo sobre todo".
dash-tom-bang
-2

En el mundo real, solo cuenta el rendimiento bruto. Ahora, el Big-O de un algoritmo puede servir como una primera indicación de qué usar, pero dependiendo del hardware, la implementación puede ser terriblemente ineficiente. Por ejemplo, hacer una búsqueda lineal a menudo puede ser más rápido que una búsqueda binaria porque obtienes acceso lineal a la memoria y no ramificaciones.

Además, debido a la dirección actual en plataformas y arquitecturas de subprocesos múltiples, Big-O está perdiendo mucha importancia, ya que solo tiene en cuenta la escalabilidad vertical de la memoria o los toques de datos por operación en lugar de tener en cuenta también cómo el algoritmo escalas con un mayor número de hilos.

Jasper Bekkers
fuente
3
Esto es incorrecto, la notación Big O se usa para mostrar los límites superiores de los algoritmos paralelos de la misma manera que los algoritmos lineales. Big O puede usarse para arquitecturas de lectura / escritura concurrentes, etc. Incluso puede hacer cosas locas como ordenar en O (1) con n ^ 2 procesadores hah
David Young
David, ¿tienes ejemplos de la vida real? Quiero decir, también puedo hacer Big-O con la cantidad de manzanas que puede llevar un grupo de personas, pero eso no significa que se use o sea útil. Según mi experiencia, la mayoría de las veces gamedev elige sus algoritmos (paralelos) basados ​​en el rendimiento bruto, no en sus funciones de crecimiento.
Jasper Bekkers
3
"ordenar en O (1) con n ^ 2 procesadores" En general, siento que este uso de O es engañoso ya que el uso de recursos sigue siendo O (n ^ 2) sin importar la forma en que divida el problema. Un mayor número de subprocesos no solo significa un mayor número de ciclos de CPU por segundo.
Richard Fabian
Ordenar en O (1) con n ^ 2 procesadores no es el mejor ejemplo, este tipo de notación Big-O probablemente se ve con mayor frecuencia en la academia. Algo así cs.bu.edu/~best/crs/cs551/homeworks/hw1/pram.html Algoritmos paralelos más realistas pueden usar procesadores log (n). Este tipo de cosas es más adecuado para sobrecargar el procesamiento de GPU o la supercomputación donde hay cientos de núcleos disponibles.
David Young
err quise decir descargar, no sobrecargar. Ya no puedo editar mi comentario original.
David Young el