O big-O é realmente relevante quando se trabalha na indústria?

Em todas as entrevistas em que participei, fui questionado sobre a análise matemática da complexidade, incluindo a notação O-grande.

Qual a relevância da análise big-O para o desenvolvimento na indústria? Com que frequência você realmente o utiliza e qual a necessidade de ter uma mentalidade aprimorada para o problema?

Minha pergunta é: qual a relevância desse teste para o desenvolvimento na indústria?

Um entendimento sólido da teoria da complexidade computacional (por exemplo, grande notação O) é essencial para projetar algoritmos, aplicativos e sistemas escaláveis. Como a escalabilidade é altamente relevante para a computação na indústria, a grande notação O também é.

Com que frequência você o utiliza de verdade e como é necessário ter uma mentalidade aprimorada para o problema?

Depende do que você quer dizer com "reeeally use it". Por um lado, nunca faço provas formais de complexidade computacional para o software que escrevo. Por outro lado, na maioria dos dias tenho que lidar com aplicativos em que a escalabilidade é uma preocupação em potencial, e as decisões de design incluem a seleção de (por exemplo) tipos de coleção apropriados com base em suas características de complexidade.

(Não sei se é possível implementar sistemas escalonáveis ​​de maneira consistente sem uma sólida compreensão da teoria da complexidade. Eu estaria inclinado a pensar que não é.)

A razão para isso é porque indica escalabilidade .

Um processo que é O (n ^ 2) será escalado pior que o que é O (n log n), mas melhor que um em O (n ^ 3) ou mesmo O (n!).

Se você não souber as diferenças e quando elas se aplicarem, será menos adequado para escolher as implementações corretas de funcionalidade, além de extrapolar o desempenho do teste para o desempenho da produção.

EDIT: Uma comparação de 48n com n ^ 3 de http://www.codinghorror.com/blog/2007/09/everything-is-fast-for-small-n.html (que por sua vez é de Programming Pearls)

Depende do que você está fazendo.

Para desenvolvedores web (como eu), isso geralmente importa muito. Você deseja que os aplicativos da Web sejam dimensionados. Se seu aplicativo tiver um gargalo que seja escalonado com O (n ^ 2), e você achar que isso é bom, porque seu servidor pode lidar com 1.000 usuários simultâneos, parece que você não precisa se importar. O problema é que, para lidar com apenas o dobro (o que é razoavelmente provável de acontecer logo durante a noite), você precisará de quatro vezes a potência computacional. Idealmente, você deseja que os aplicativos da Web sejam redimensionados em O (n), porque o hardware é barato a uma proporção sensata de usuário / servidor constante.

Geralmente em aplicativos, onde você tem 100000s de objetos, o grande O virá e o comerá. Você é imensamente vulnerável a picos. Por exemplo, atualmente estou trabalhando em um jogo em 3D, que é um aplicativo que lida com muitos dados. Além da renderização, você tem verificação de colisão, navegação etc. Você não pode se dar ao luxo de seguir o caminho óbvio. Você precisa de algoritmos eficazes, precisa de muito armazenamento em cache para que os menos eficientes sejam amortizados. E assim por diante.

Obviamente, se o que você faz é algo como criar um aplicativo móvel reunindo uma GUI em um designer de interface, conecte alguns serviços da Web e pronto, nunca haverá problemas com a complexidade. Porque os serviços da web que você chama já cuidam disso.

Na verdade, nunca apliquei formalmente a regra na minha vida profissional.

No entanto, você deve estar familiarizado com esse conceito e aplicá-lo de maneira intuitiva sempre que criar um algoritmo.

A regra é:

Você deve estar familiarizado o suficiente com a notação O para poder determinar, para uma determinada tarefa, se é necessário calculá-la formalmente ou se é apenas o suficiente para avaliá-la intuitivamente, ou se você pode simplesmente ignorá-la completamente. Assim como muitos outros conceitos matemáticos básicos.

Bem, talvez uma pequena história explique por que DEFINITIVAMENTE é necessário:

Em um projeto em que estou trabalhando, havia um programa responsável por imprimir todos os tipos de documentos (etiquetas, listas de picking etc.) Esse programa consistia em duas partes, uma lendo todos os dados necessários do banco de dados e gravando-os em um arquivo .ini e outra parte que leu esses arquivos e os preencheu nos modelos. Isso funcionou razoavelmente bem para etiquetas e pequenas listas (com apenas alguns campos), mas durou quase 10 minutos quando foi necessário imprimir uma lista "grande" de ~ 20 páginas. Como o acesso a esses arquivos ini resultou em tempos de acesso de O (n²), n sendo o número de campos a serem impressos.

Se os programadores originais desse programa tivessem entendido a notação O, nunca teriam feito dessa maneira. Substituir essa estupidez por uma hashtable tornou muuuuuuuuito mais rápido.

O desempenho do Big-O é importante, mas foi amplamente internalizado.

O desempenho do Big-O de classificação e pesquisa não importa, porque as pessoas geralmente usam as fornecidas pelo sistema e elas serão tão boas quanto possível (uma vez que precisam ser úteis em geral). Existem estruturas de dados que são mais eficientes para coisas diferentes, mas essas geralmente podem ser selecionadas com base em princípios gerais (e geralmente são incorporadas às linguagens modernas). Há algum senso de algoritmos que escalam ou não.

O resultado é que as questões formais raramente surgem na prática, mas a prática é construída com os mesmos princípios.

IMHO muitos programas de ciência da computação deixam muitos estudantes vagando lá embaixo no mato. Esses programas nunca comunicam muito bem o que é a ciência da computação. Os alunos entram no setor, tentando entender como aplicar os conceitos que aprenderam, com poucas informações sobre como eles se relacionam com o mundo real.

Eu diria que o coração da ciência da computação é a capacidade de raciocinar sobre a computação. E você aprende vários métodos e técnicas para fazer isso e os aplica a problemas abstratos, que são primitivos prototípicos encontrados em muitos problemas do mundo real. O truque é identificar essas primitivas prototípicas no mundo real e argumentar sobre coisas como correção, complexidade, tempo etc., as quais, você pode concordar, são questões reais com as quais você precisa se preocupar. A percepção de como as partes se comportam frequentemente fornece informações sobre como o todo se comporta. E os mesmos métodos e técnicas gerais também podem ser aplicados ao todo, mas não com o mesmo rigor que é oferecido às partes menores, bem abstratas e bem definidas. Mas, no final, a ciência da computação lhe confere a capacidade de tornar razoável decisões sobre como organizar seu cálculo, com informações reais sobre como ele se comportará sob várias condições.

Memorando para si !:

Eu e muitos outros nos fazemos essa pergunta regularmente.

Eu acho que a verdadeira razão pela qual pedimos isso é porque nos tornamos preguiçosos.

Esse conhecimento nunca será datado ou se tornará obsoleto. Você não pode aplicá-lo diretamente no dia a dia, mas o usará inconscientemente e isso afetará positivamente suas decisões de design. Um dia, você ou outras pessoas podem economizar horas e dias de codificação.

À medida que mais problemas são encapsulados por bibliotecas e ferramentas de terceiros e estão disponíveis para mais e mais desenvolvedores, você precisará conhecer esse conhecimento para se diferenciar dos outros e ajudar a resolver novos problemas.

Na verdade não. Basicamente, a única vez em que penso nisso é ao acessar o banco de dados. Normalmente, vou olhar o código e dizer "Isso está fazendo n + 1 consultas, você deve alterá-lo para fazer apenas 1 ou 2"

Como todos os meus dados estão sendo lidos em um banco de dados e mostrados ao usuário, tento minimizar a quantidade de dados com os quais estou trabalhando até o ponto em que a diferença entre um algoritmo linear e um algoritmo O (n ^ 2) é bastante insignificante.

Se houver algum problema, analisaremos e corrigiremos mais tarde.

Três perguntas que você coloca e acho que respostas curtas podem ajudar nos argumentos mais longos dados até agora.

Quão relevante é esse teste para o desenvolvimento na indústria?

Depende da indústria.

Em qualquer lugar em que a velocidade ou o espaço do código sejam um problema, é totalmente relevante para o setor envolvido. Geralmente, você precisa saber quanto tempo uma rotina levará ou quanta memória (on / offline) será necessária.

Com que frequência você o usa de verdade?

Depende da indústria.

Se o desempenho e o dimensionamento são de pouca preocupação para o trabalho em questão, raramente, apenas quando há um sério déficit de desempenho. Se você é um engenheiro de um sistema crítico altamente usado, provavelmente todos os dias.

Quão necessário é ter uma mentalidade aprimorada para o problema?

Inteiramente necessário.

Você pode ter que usá-lo todos os dias, ou apenas em circunstâncias terríveis; mas às vezes será necessário. De preferência, durante o design antes da ocorrência de um problema, do que criar um perfil desesperado de um sistema de asfixia.

Eu diria que é muito frequente. Geralmente, não provamos que algo tenha um big-O específico, mas internalizamos a idéia e memorizamos / familiarizamos-nos com as garantias do big O para estruturas e algoritmos de dados específicos e escolhemos os mais rápidos para um uso específico. Ajuda a ter uma biblioteca cheia de todas as opções, como a biblioteca de coleções Java ou o C ++ STL. Você implícita e naturalmente usa big-O todos os dias quando escolhe usar uma java.util.HashMap( O(1)pesquisa) em vez de uma java.util.TreeMap( O(lg n)pesquisa) e certamente escolhe não executar uma pesquisa linear em uma java.util.LinkedList( O(n)pesquisa) por algo em que não precisa de acesso classificado.

Quando alguém escolhe uma implementação abaixo do ideal e alguém que conhece melhor aparece e vê seu código, faz parte do nosso vocabulário corrigi-lo "sua implementação leva tempo quadrático, mas podemos reduzir esse tempo até o tempo n-log-n ao fazê-lo dessa maneira "de maneira tão natural e automática quanto usaríamos o idioma inglês para pedir uma pizza.

sim

Talvez você não precise fazer análises formais, mas pelo menos uma compreensão profunda da ordem da complexidade do algoritmo - e como comparar dois algoritmos em torno disso - é fundamental se você deseja fazer um trabalho não trivial e ter bom desempenho.

Eu trabalhei em dois sistemas diferentes que pareciam bons no desenvolvimento inicial, mas levaram o hardware aos joelhos nos testes de produção, porque alguém usava um algoritmo O (n ^ 2). E em ambos os casos, a correção foi uma alteração trivial em um algoritmo O (n).

Provavelmente é usado em locais onde eles estão desenvolvendo APIs para consumo. O C ++ STL é uma das poucas APIs que têm restrições de complexidade impostas aos seus algoritmos. Mas para o programador que trabalha todos os dias / programador sênior / designer / arquiteto, isso não passa pela cabeça deles.

Eu não achei isso importante, exceto para comunicar idéias, e trabalho em campos críticos de desempenho (rastreamento de raios, processamento de imagem e malha, sistemas de partículas, mecanismos de física etc.) e tive que criar muitos algoritmos e estruturas de dados proprietários ao trabalhar em P&D. Nessas áreas, muitas vezes um punhado de estruturas e algoritmos de dados muito eficientes pode gerar novos produtos de ponta, enquanto os algoritmos de ontem tornam obsoletos os produtos existentes, por isso há sempre a busca de fazer as coisas com mais eficiência. Como uma ressalva, nunca publiquei nenhum artigo sobre os algoritmos que criei. Eles eram todos proprietários. Se o fizesse, precisaria da ajuda de um matemático para formular provas e assim por diante.

No entanto, na minha opinião, a quantidade de trabalho computacional por iteração costuma ser de interesse mais imediato do que a escalabilidade do algoritmo, a menos que o algoritmo seja muito pouco dimensionado. Se alguém inventa uma técnica de ponta para o traçado de raios, estou mais interessado em técnicas computacionais, como como elas representam e acessam dados, do que a complexidade algorítmica, porque a escalabilidade razoável já é um dado neste cenário competitivo e inovador. Você não pode ser competitivo criando algoritmos que não escalam.

Obviamente, se você estiver comparando complexidade quadrática com linearitmica, é uma enorme diferença. Mas a maioria das pessoas na minha área é competente o suficiente para evitar a aplicação de um algoritmo de complexidade quadrática em uma entrada épica. Portanto, a escalabilidade geralmente está profundamente implícita e as perguntas mais significativas e interessantes se tornam: "Você usou o GPGPU? SIMD? Ele roda em paralelo? Como você representa os dados? Você o reorganizou para padrões de acesso compatíveis com o cache?" muita memória é necessária? Ele pode lidar com esse caso de forma robusta? Você está adiando um determinado processamento ou fazendo tudo de uma só vez? "

Mesmo um algoritmo linearitmico pode superar um algoritmo de tempo linear se o primeiro acessar a memória em um padrão mais ideal, por exemplo, ou for mais adequado para multithreading e / ou SIMD. Às vezes, mesmo um algoritmo linear pode superar um algoritmo logarítmico por esses motivos, e naturalmente os algoritmos de tempo linear superam os algoritmos logarítmicos para entradas menores.

Então, para mim, o que importa mais é o que algumas pessoas chamam de "micro-otimizações", como representações de dados (layouts de memória, padrões de acesso com divisão de campos quentes / frios, etc.), multithreading, SIMD e, ocasionalmente, GPGPU. Em um campo em que todos já são competentes o suficiente para usar algoritmos decentes e avançados para tudo, com novos trabalhos sendo publicados o tempo todo, sua vantagem competitiva em vencer os assistentes algorítmicos não provém de melhorias na complexidade algorítmica, mas também de maneira mais direta. eficiência computacional.

Meu campo é dominado por matemáticos brilhantes, mas nem sempre aqueles que sabem o custo computacional do que estão fazendo ou muitos truques de nível inferior para acelerar o código. Essa é geralmente a minha vantagem sobre eles na criação de algoritmos e estruturas de dados mais rápidos e mais rigorosos, apesar de os meus serem muito menos sofisticados. Estou brincando com o que o hardware gosta, em direção a bits e bytes e tornando cada iteração de trabalho muito mais barata, mesmo que eu esteja fazendo mais algumas iterações de trabalho do que o algoritmo realmente sofisticado - o trabalho no meu caso é drasticamente mais barato. O código que escrevo também tende a ser muito mais simples. Se as pessoas acharem que versões micro-otimizadas de algoritmos diretos e estruturas de dados são difíceis de entender e manter,

Como exemplo básico, criei uma estrutura de grade simples que acabou superando uma árvore KD em nossa empresa para detecção de colisões e remoção de pontos redundantes. Minha grade estúpida e bruta era muito menos sofisticada algoritmicamente e sou muito mais matematicamente e algorítmica do que o cara que implementou a árvore KD com sua nova maneira de encontrar o ponto médio, mas apenas ajustei os padrões de uso e acesso à memória da minha grade e isso foi suficiente para superar algo muito mais sofisticado.

Outra vantagem que tenho que me permite sobreviver em um campo dominado por pessoas muito mais inteligentes do que eu é realmente entender como o usuário trabalha, já que eu uso o software que desenvolvo da mesma maneira. Isso me dá idéias para algoritmos que realmente se alinham muito imediatamente aos interesses do usuário. Como exemplo básico, a maioria das pessoas tenta acelerar coisas como a detecção de colisões usando indexação espacial. Fiz uma observação simples de modelagem de carreira há quase duas décadas para modelos orgânicos que, por exemplo, se um personagem coloca as mãos no rosto, uma estrutura de indexação espacial gostaria de dividir nós e fazer atualizações caras se o personagem depois tirou a mão do rosto. Se, em vez disso, você particionar com base nos dados de conectividade, e não nas posições de vértice, você pode acabar com uma estrutura hierárquica estável que é atualizada rapidamente e nunca precisa dividir ou reequilibrar a árvore (só é necessário atualizar caixas delimitadoras a cada quadro de animação) ... coisas assim: algoritmos que uma criança sem formação matemática pesada poderiam surgir se eles apenas entendessem o conceito básico, mas aqueles que iludiam os matemáticos porque não pensavam nas coisas de uma maneira tão próxima de como os usuários trabalhavam e pensavam demais apenas nas propriedades da geometria e não na geometria foi comumente usado. Eu me dou bem bastante, apoiando-me mais no conhecimento geral da computação e no conhecimento do usuário do que na magia algorítmica. De qualquer forma, eu realmente não achei tão importante focar na complexidade algorítmica.

Sim, a complexidade é importante no setor. Se você acabar projetando algo em que um caminho crítico é escalado como N ao quadrado (dobrar o número de algo que torna o sistema quatro vezes mais carregado), você atingirá seu gargalo de escala muito mais rápido do que se tivesse algo que fosse escalado em N.

No entanto, geralmente não é uma prova formal e adequada de que algo está em uma dada complexidade; portanto, ter uma boa intuição sobre a complexidade de um padrão de operações é um bom começo.

Nunca penso em O grande em uma perspectiva matemática, nunca penso em O grande, a menos que seja solicitado. Acabei de ver um algoritmo na minha cabeça e posso dizer se é ruim, porque faz vários loops na memória para cada N, ou se divide e conquista ou algo assim. Se necessário, posso traduzir isso para a notação O grande em poucos segundos, mas é mais fácil saber como o algoritmo / contêiner funciona com a memória do que pensar na perspectiva matemática.

As perguntas que são feitas nas entrevistas existem para descobrir se você pode explicar as coisas e pensar de uma maneira lógica . O entrevistador também está tentando descobrir se você pode empregar o que sabe para resolver um problema relacionado .

Todo mundo que fez algum estudo interessante de engenharia de software encontrou o "Big O", também para responder a uma boa pergunta sobre o "Big O", você também deve ter alguma compreensão das estruturas e algoritmos de dados padrão.

Ao entrevistar um membro da equipe, você está procurando alguém que possa aprender rapidamente o trabalho e não alguém que já conheça um determinado conjunto de habilidades detalhadas; portanto, pode ser muito difícil escolher perguntas que o entrevistador e o entrevistado tenham um entendimento comum. do.

Portanto, perguntas sobre "grande O" podem ser muito relevantes para o processo de entrevista.

Pelo menos todos os anos, durante o meu longo período como programador de computador, tive que corrigir um código lento devido a alguém que não entendia as estruturas de dados e algoritmos corretos para usar, mas você pode resolver esses problemas sem ter um entendimento detalhado do Big O. No entanto, as pessoas que entendem o Big O tent não evitam esses problemas em primeiro lugar.