Big O realmente importa?

Na pior das hipóteses, o Big O é ensinado sobre todo o resto. Comparado à complexidade do espaço, análise de caso normal, simplicidade sobre complexidade, etc.

Em particular na programação e na indústria de jogos, o que realmente importa mais e por quê?

Referências seriam muito úteis.

Como em todas as outras perguntas sobre "qual é o único caminho verdadeiro", essas são todas as ferramentas da sua caixa de ferramentas e há casos em que o big-O supera tudo e lugares onde isso não importa (tm).

Você "nunca" escreveria um solucionador de física sem se preocupar com o grande O. Você não implementaria um algoritmo de classificação (apenas para o menor dos conjuntos de dados) sem se preocupar com isso. Se você estiver escrevendo um jogo em rede, ficará preocupado com a forma como o desempenho e o tráfego de rede são escalados por usuário.

Você pode não estar tão preocupado com o big-O quando, bem, eu realmente não consigo pensar em um tempo, mas tenho certeza que existem alguns. :) Felizmente, a maioria das coisas que fazemos nos jogos é escalada linearmente; você quer ler um arquivo fora do disco? Levará um tempo linear proporcional ao tamanho do arquivo (descontando o fator constante de busca e possíveis ramificações do tamanho do setor).

No entanto, e se você quiser encontrar uma entidade específica na lista de entidades? Essa é uma pesquisa linear sempre que você faz. Se você precisar encontrar o jogador uma vez para todas as entidades do mundo, essa abordagem o matará por todos os jogos, exceto os mais triviais, e mesmo assim provavelmente vale a pena "otimizar" essa pesquisa para ser constante (por exemplo, armazene o índice ou um ponteiro para o player em algum lugar), dando a você mais tempo para fazer outras coisas que são realmente visíveis para o player.

Acho que isso resume tudo; sempre que o processador está fazendo algo que não é diretamente representável ao jogador, está perdendo tempo. Maximizar a quantidade de tempo que o processador está computando os dados que serão mostrados ao player está maximizando o WOW! você está dando ao jogador.

Minha regra geral é que, a menos que você seja O (assustador), seus outros problemas são mais pertinentes.

Minha outra regra é que os dados são rei. A menos que você crie um perfil do seu código com um conjunto de dados realista, você está apenas tentando adivinhar.

Edit: Para entrar um pouco mais detalhadamente, seu grande O não é tão importante, pois (pelo menos na minha experiência) a maioria dos seus conjuntos de dados é relativamente pequena. Você provavelmente não se importa com seu limite superior de desempenho ao trabalhar com uma estrutura de dados com menos de algumas centenas de elementos. E se suas listas tiverem mais de 100k elementos, você realmente precisará considerar todos os aspectos de seus algoritmos. Isso e da minha experiência a memória é mais um fator limitante do que a velocidade da CPU. Um algoritmo de consumo de memória mais rápido pode não ser tão bom quanto um mais enxuto, mas mais lento, dependendo dos casos de uso.

Big O é importante na maioria das vezes, mas às vezes um algoritmo aparentemente "pior" em teoria acaba sendo muito mais rápido na prática.

Confira um ótimo exemplo de Tony Albrecht: http://seven-degrees-of-freedom.blogspot.com/2010/07/question-of-sorts.html

Você encontra isso em todo o lugar no desenvolvimento de jogos, onde o número de itens na operação é tão grande que um algoritmo muito diferente é mais rápido, ou tão pequeno que um algoritmo mais burro é suficiente (ou se encaixa no cache tão bem que anula a eficiência do melhor algoritmo).

O problema com o Big O é que é uma designação genérica da complexidade da tarefa e não leva em consideração a complexidade do hardware de destino moderno, nem oferece uma visão sobre o tempo de configuração adicional.

Em muitos casos, a melhor solução ideal é duas etapas. Na prática, os desenvolvedores de jogos tendem a tender para algoritmos de baixo O, mas equilibrados com o custo no tempo em desenvolvimento ou depuração. Depois de ter uma solução razoável, você sempre deve observar como o hardware está lidando com a tarefa e como permitir que o hardware faça mais em menos tempo.

Quando eu estou codificação in-motor, eu estou muitas vezes apenas em causa com um fixo n: Eu já tenho uma partição espacial limitando o número de objetos de receber update(), physics()e render()para aproximadamente aqueles na tela e áreas circundantes. O tamanho máximo do lote é geralmente bem definido por jogo, embora invariavelmente seja um pouco maior do que você planejou.

Nesse caso, não estou tão preocupado com o grande O quanto com o multiplicador constante de fatores e termos de ordem inferior. Para uma função com tempo de execução como a*n^2 + b*n + c(o que é O(n^2)), geralmente estou muito mais preocupado em reduzir ae possivelmente eliminar c. Um custo de instalação ou desmontagem cpode se tornar proporcionalmente grande versus um pequeno n.

No entanto, isso não significa que big-O (ou mais particularmente big-theta ) seja um ótimo indicador de cheiro de código. Veja um momento O(n^4)geográfico em algum lugar, ou pior ainda O(k^n), e é hora de verificar se você está considerando outras opções.

Em geral, estou muito mais preocupado com a otimização do big O e pulando através de argolas para encontrar algoritmos com big O menor quando estou lidando com ferramentas de criação de dados. Enquanto o número de objetos em um determinado nível / área de streaming geralmente é bem definido, o número total de objetos / objetos de arte / arquivos de configuração / etc em um jogo inteiro pode não ser. Também é um número muito maior. Mesmo executando uma produção de dados paralela, ainda esperamos cerca de um minuto (eu sei, lamentar - a produção de dados para consoles pode levar horas - somos na maioria pequenos jogos portáteis) para passar por um jam data-clean && jam dataciclo.

Para dar um exemplo específico: isso ficou realmente fora de controle com um algoritmo de fluxo de blocos de segundo plano que transmite blocos de 256 cores 8x8. É útil compartilhar buffers de streaming entre "camadas" de segundo plano, e podemos ter até 6 deles em um determinado nível compartilhando o mesmo buffer. O problema é que estimar o tamanho do buffer necessário é baseado nas posições possíveis de todas as 6 camadas - e se elas são uma taxa de largura / altura / rolagem de número principal, você rapidamente começa a fazer uma pesquisa exaustiva - que começa a se aproximarO(6^numTiles)- que está na categoria "mais longo que o universo estará" em muitos casos. Felizmente, a maioria dos casos tem apenas 2-3 camadas, mas, mesmo assim, temos mais de meia hora de duração. No momento, amostramos um subconjunto muito pequeno dessas possibilidades, aumentando a granularidade até que um determinado período de tempo tenha passado (ou concluímos a tarefa, o que pode acontecer em pequenas configurações de camada dupla). Aumentamos essa estimativa um pouco com base em estatísticas anteriores de quantas vezes provamos que estamos errados e, em seguida, adicionamos um pouco de preenchimento extra.

Outro exemplo divertido: em um jogo para PC, há algum tempo, o engenheiro-chefe experimentou por um tempo as listas de pulos . A sobrecarga de memória acaba causando mais efeitos de cache, o que adiciona uma espécie de multiplicador não constante a todo o caso - para que não sejam realmente boas escolhas para os pequenos n. Porém, para listas classificadas maiores, onde as pesquisas são frequentes, elas fornecem um benefício.

(Muitas vezes, acho que o ingênuo algoritmo é maior, O maior, mais rápido em conjuntos de dados menores e mais fáceis de entender; os mais interessantes / complexos (por exemplo, patricia trie) são mais difíceis para as pessoas entenderem e manterem, mas maior desempenho em maior conjuntos de dados.)

Pode ser útil, mas também pode ser irrelevante. Tomemos, por exemplo, o meu jogo mais recente, que é um clone do Smash TV. Jogo de cima para baixo, monstros se espalham pelos lados, você atira neles.

Agora, existem muitas maneiras inteligentes de determinar colisões. Você pode usar o KDtrees para particionar o espaço para não testar balas contra monstros que eles não poderiam atingir. E, com certeza, eu poderia ter sido inteligente e poderia ter feito isso.

Mas eu estava com preguiça, então comparei cada bala contra cada monstro. Mesmo nas situações mais agitadas, o código de colisão estava usando muito menos de 10% da CPU do jogo a 60fps. Big-O: sem importância.

Da mesma forma, eu tinha um jogo no estilo 4x em que você construía cidades em ilhas e, às vezes, as cidades eram destruídas. Eu poderia ter sido inteligente e tentar subtrair a renda da cidade destruída das variáveis ​​de renda. Mas eu não fiz. Acabei de limpar a renda e recalculá-la do zero toda vez que algo mudava. Totalmente irrelevante em termos de CPU.

O Big-O é tão importante nos jogos quanto em todo o resto: ou seja, sem importância, até que se torne crítico.

Vá escrever um código. Se estiver muito lento, faça o perfil.

A análise Big-O é importante, mas não é a primeira coisa a se pensar no desenvolvimento de jogos. Como criar jogos envolvia muitos códigos complicados, eu sempre recomendaria o Code Simplicity como o primeiro critério para um algoritmo. Algoritmos com contabilidade complicada apenas desperdiçam seu tempo.

Eu acho que é realmente importante que seu jogo sempre funcione a 60 qps durante o desenvolvimento. Quando você mergulha abaixo disso, a primeira coisa a fazer é executar um criador de perfil. Depois de encontrar o gargalo, você o ataca. Na maioria das vezes, você precisa fazer coisas que não são de codificação, como dizer aos projetistas de nível para colocar menos coisas em uma área (e fornecer a eles ferramentas para isso).

Às vezes, você realmente identifica algum código que precisa ser acelerado. Acho isso divertido de engenharia! Eu gostaria de ter mais oportunidades para fazer isso. E é claro que você deseja repetir a alteração de uma coisa de cada vez e a medição do desempenho. Os problemas típicos que encontro são:

1. Verifique se você não está chamando novo ou malloc cada quadro (esse é sempre o problema nº 1)
2. Reduza o trabalho: menos projeções de raios, menos indivíduos etc.
3. Problemas do tipo de algoritmo Big-O
4. Coerência do cache: coloque coisas em matrizes em vez de memória dispersa
5. Não use STL no modo de depuração. (e você sempre deseja que o modo de depuração funcione)

A notação Big-O é, por definição, complexidade assintótica - isto é, mostra como o tempo aumenta quando N (ou quaisquer variáveis ​​que você possui) fica "muito" grande. Para reiterar o comentário de Tetrad (que eu levantei) "os dados são rei". Se N é "muito grande" em sua situação específica, isso importa, se N é "muito pequeno", não importa. Experiência e prática lhe darão uma idéia de como quantificar "muito grande" e "muito pequeno".

Obviamente, sempre perfil primeiro e otimize por último (a menos que você esteja fazendo um estudo de viabilidade de recursos).

A importância do Big-O no seu software é O (N ² ). À medida que N cresce, a importância de ter o algoritmo correto aumenta ainda mais. :)

Big-O é apenas uma diretriz - algo que indica o desempenho aproximado que você pode esperar de um algoritmo - e como você deve esperar que o desempenho seja escalado à medida que aumenta o tamanho do conjunto de dados . Você deve se lembrar de duas coisas principais em relação ao Big-O:

1) Se você tem dois algoritmos que geralmente fazem a mesma coisa, mas um tem um O melhor, você provavelmente deve optar por esse (obviamente)

2) Big O está preocupado com a análise assintótica . Big-O só entra em jogo quando n é grande . Por exemplo, um algoritmo O (n) pode ser muito semelhante no desempenho a um algoritmo O (n ^ 2) .. para n pequeno . Se você está falando de um algoritmo que requer n ^ 2 operações por vértice, mas n = 2 ou n = 3, então não há muita diferença entre um algoritmo O (n ^ 2) (fazendo 4 e 9 ops resp) e um O (n) um (2 e 3 ops resp.). No entanto, se n = 9, de repente você está falando de 81 operações para o algoritmo O (n ^ 2) e apenas 9 para o O (n) - uma diferença maior - e se n = 100, então você está falando de 100 ops vs 10000 - uma diferença muito maior.

Portanto, você deve sempre considerar Big-O sob essa luz: ele pretende comparar algoritmos que fazem a mesma coisa com base no pior desempenho possível, quando n fica grande . As diferenças entre os algoritmos podem ser desprezíveis quando n é muito pequeno.

Não tenho referências, mas o Big O é pelo menos útil para estar ciente ao analisar um problema e uma discussão. Por outro lado, é claro, se a versão O (log n) tem muito mais O envolvido do que a versão O (n), é uma comparação controversa. E, como em tudo, sempre há uma troca. A complexidade do espaço pode ser um problema, embora isso também possa ser expresso em O em geral. Análise de caso normal ... menos ainda, pois você também não deseja que os outliers aumentem. Simplicidade sobre complexidade, na minha opinião, é relativamente inútil no desenvolvimento de jogos, pois a velocidade quase sempre é um problema, portanto, a menos que a simplicidade leve a acelerações (mas isso significa que seu caso complexo estava errado pelas razões erradas), a simplicidade terá que desaparecer. fora da janela em favor da velocidade. Mas Big O é definitivamente útil,

Quando você protótipo uma função jogo ou um aspecto de um jogo, você não deve se preocupar sobre como otimizar-lo em tudo .

Durante o processo de criação de um protótipo e o aprendizado sobre as idiossincrasias dessa funcionalidade, as otimizações necessárias se tornarão óbvias e levarão em consideração o design final, como a 2ª natureza ... na maioria das vezes.

Não se preocupe.

Não deve ser o tudo e o fim de tudo. Mas ajuda a resolver problemas óbvios que podem causar problemas no desempenho; por que usar algo no tempo O (n ^ 2), quando você pode fazer o mesmo no tempo O (log n)?

Eu acho que se aplica aos jogos mais do que a maioria das outras indústrias, já que o mercado é quem mais notaria problemas de velocidade. Alguém usando um processador de texto não se importará se houver um atraso de meio segundo para executar a ação X, mas os jogadores provavelmente irão 'omg omg omg game Y é tão lento que leva anos para executar a ação Z'.

No desenvolvimento de jogos (e na maioria dos outros), estamos reclamando de uma operação extra realizada por loop:

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

vs.

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

A maioria dos jogos modernos tem física, e você encontrará o problema da simulação de n corpos . Em um algoritmo ingênuo, é O (n ^ 2), mas há uma otimização que o torna O (n log n) (mas sacrifica alguma precisão).

Pode-se dizer que você não está programando interações entre gravidade e partículas, mas e o comportamento da equipe de um exército (de zumbis) para onde eles se movem dependendo de outros locais (em uma palavra mais específica: enxame)?

Em um algoritmo convencional de detecção de colisões, a complexidade do tempo é O (n ^ 2), como o corpo n. No entanto, existe uma maneira melhor: separe o mundo em várias partes pequenas, para que apenas objetos dentro da mesma peça sejam detectados por colisão. Consulte http://www.videotutorialsrock.com/opengl_tutorial/collision_detection/text.php .

Se o seu jogo for programável, NÃO faça o roteirista escrever algoritmos de triagem de números O (n ^ 2) (e acima) no script, como procurar na bolsa do usuário. Crie uma função interna no código.

No mundo real, apenas o desempenho bruto conta. Agora, o Big-O de um algoritmo pode servir como uma primeira indicação do que usar, mas, dependendo do hardware, a implementação pode ser terrivelmente ineficiente. Por exemplo, fazer uma pesquisa linear pode ser mais rápido que uma pesquisa binária, porque você obtém acesso linear à memória e não possui ramificações.

Além disso, devido à direção atual em plataformas e arquiteturas multithread, o Big-O está perdendo muito significado, pois considera apenas a escalabilidade vertical da memória ou toques de dados por operação, em vez de também levar em consideração como o algoritmo escalas com um número maior de threads.