Big O realmente importa?

17

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.

David Young
fonte
Big-O = Otimização. Demorei um pouco para descobrir o que era 0 grande.
AttackingHobo
12
Big-O não é "otimização". Big-O é uma forma de análise que mostra como os diferentes algoritmos se comportarão, em termos de eficiência, à medida que o número de elementos agidos aumenta. Veja en.wikipedia.org/wiki/Big_O_notation para mais detalhes.
precisa saber é o seguinte
2
Posso garantir que as pessoas que criaram octrees e BSP / PVS sabiam tudo sobre big-O. No final, a única coisa que importa é o desempenho do aplicativo. Mas para chegar lá, é necessário considerar todo tipo de coisas, incluindo a complexidade assintótica dos algoritmos que lidam com muitos dados.
Drxzcl 31/08/10
1
Lembre-se da regra de quando otimizar: 1) Não faça isso. 2) (somente para especialistas) Não faça isso ainda.
Zaratustra
Bem, antes de tudo, o Big O pode ser usado para complexidade espacial ou computacional; portanto, "acima de tudo" não é exatamente verdade. Segundo, o Big O geralmente é muito mais simples de calcular do que a análise de caso normal e seria usado como uma verificação mental rápida para saber se você está fazendo algo errado. Se desenhar um sprite leva tempo O (2 ^ n), você provavelmente deve escolher um algoritmo diferente. Se você deseja uma abordagem mais prática ao design de software, observe as práticas de SE em vez de CS. O CS é de natureza teórica, enquanto o SE é mais baseado na indústria.
Deleter

Respostas:

25

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.

traço-tom-bang
fonte
8
Este. É importante entender as características de desempenho do seu código. Você nunca sabe quando um designer usará algo que você adicionou de uma maneira que você não esperava e, de repente, o pouco de código que você pensou que só precisaria lidar com 5 itens agora está lidando com 5000 e sendo pingado 100 vezes por quadro. Você otimiza isso? Você pode? Quanto é realmente razoável? Um perfil apenas informa o quão lento é, não o porquê. Conhecer a complexidade informará se você precisa otimizar o código ou substituí-lo por algo diferente.
JasonD
3
Acordado. As universidades ensinam o 'Big-O' porque ele lida com muitos dos problemas que você enfrentará. Quando você é perguntado 'oh, podemos tornar esse infinito em vez de apenas 5? os testadores odeiam a limitação 'é quando o treinamento compensa. Você não deveria apenas dizer 'não, não posso'. É vital ser capaz de resolver problemas com isso e dizer 'sim, eu posso'. Seu jogo precisa de uma galáxia pesquisável? 'Sem problemas'. Esses milhões de unidades precisam ser encomendados? 'Sem problemas'. 'Não estudou o suficiente' simplesmente não serve.
Rushyo 31/08/10
"Você pode não estar tão preocupado com o big-O quando ..." processando chaves de entrada. Eu herdei um sistema de entrada que fazia todo o possível para resolver os mapeamentos de chave-> ação em tempo constante, usando uma tabela de pesquisa. Mudar para uma pesquisa linear de uma matriz de pares (chave, ação) economizou memória e não teve impacto no desempenho, pois os usuários raramente pressionam mais do que algumas teclas por quadro, e a matriz geralmente possui apenas 20 a 30 itens. Também vamos adicionar (tecla, tecla, ação) aos acordes.
Joe, claro, embora esse seja um tipo diferente de preocupação. Deseja O (1) onde o fator constante é alto ou O (n) com um pequeno 'n' e um baixo fator constante? Conhecer big-O nesse caso não é um problema, mas pode ajudá-lo a descobrir se a solução faz ou não sentido para as circunstâncias em que será usada.
traço-tom-bang
13

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.

Tetrad
fonte
8

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.

Richard Fabian
fonte
"O problema com o Big O" é que as pessoas parecem esquecer que é a complexidade algorítmica do desempenho em relação aos tamanhos de conjuntos de dados grandes. Nos jogos (geralmente) não atingimos esses valores de N, precisamos nos preocupar com as outras peças do quebra-cabeça. Eu suspeito que o tipo de bolha sempre terá um desempenho superior ao quicksort quando você tiver uma lista de dois elementos.
dash-tom-bang
7

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.)

leander
fonte
4

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.

ZorbaTHut
fonte
3

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)
Tod
fonte
2

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).

Crowley9
fonte
1

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

Kylotan
fonte
Isso não depende de quantas vezes esse algoritmo é chamado ..?
bobobobo
Até certo ponto. Mas se levar três dias para ser executado, provavelmente não importa se você chamar apenas uma vez. :)
Kylotan
1

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 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.

bobobobo
fonte
0

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,

Kaj
fonte
0

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.

Steve H
fonte
"Quando você protótipo de uma função ou de um aspecto de um jogo, não deve se preocupar em otimizá-la." Isso é verdade às vezes, mas nem sempre. Certos jogos, como Dead Rising, contam com uma execução rápida para viabilizar o mecanismo principal do jogo - centenas de zumbis em tempo real.
Qual porcentagem de desenvolvimento de jogos é prototipagem? Eventualmente, você deseja enviar algo , certo?
-10-dash-tom-bang
0

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'.

O Pato Comunista
fonte
0

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.

Ming-Tang
fonte
1
Os dois exemplos de código são O (n). As discussões do Big-O não têm nada a ver com "uma operação extra por loop", mas com "uma pesquisa extra em tudo por iteração do loop sobre tudo".
dash-tom-bang
-2

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.

Jasper Bekkers
fonte
3
Isso está incorreto, a notação Big O é usada para mostrar os limites superiores dos algoritmos paralelos da mesma forma que os algoritmos lineares. O grande pode ser usado para leitura simultânea de gravação / concorrente arquiteturas etc. Você mesmo pode fazer coisas loucas como a ordenação em O (1) com N ^ 2 processadores hah
David Young
David, você tem exemplos da vida real? Quero dizer, também posso aumentar o número de maçãs que um grupo de pessoas pode carregar, mas isso não significa que seja usado ou útil. De acordo com minha experiência, na maioria das vezes os gamedev escolhem seus algoritmos (paralelos) com base no desempenho bruto, não nas funções de crescimento.
Jasper Bekkers
3
"classificando O (1) com n ^ 2 processadores" Geralmente, acho que esse uso de O é enganoso, pois o uso de recursos ainda é O (n ^ 2), independentemente da maneira como você elimina o problema. Um número maior de threads não significa apenas um número maior de ciclos de CPU por segundo.
Richard Fabian
Classificar O (1) com n ^ 2 processadores não é o melhor exemplo, esse tipo de notação Big-O é provavelmente mais frequentemente visto na academia. Algo como esse cs.bu.edu/~best/crs/cs551/homeworks/hw1/pram.html Algoritmos paralelos mais realistas podem usar processadores de log (n). Esse tipo de material é mais adequado para sobrecarregar o processamento da GPU ou a supercomputação, onde existem centenas de núcleos disponíveis.
David Young
err, eu quis dizer descarregar, não sobrecarregar. Não é mais possível editar meu comentário original.
David Young