É um problema ser um programador sem conhecimento sobre complexidade computacional?

30

Fui designado para um exercício na minha universidade. Levei para casa e tentei programar um algoritmo para resolvê-lo, era algo relacionado a gráficos, encontrando componentes conectados, eu acho.

Então eu fiz a coisa mais trivial que me veio à mente e depois mostrei ao meu professor. Após uma breve observação, ele percebeu que a complexidade do tempo de execução da minha solução era inviável e mostrou algo mais eficiente. E há uma tradição de programadores que não têm idéia do que é complexidade computacional (eu era um deles), então é um problema se um programador não tem idéia do que é complexidade computacional?

Billy Rubina
fonte
3
Aviso ao moderador : não use comentários para discussões prolongadas ou para postar respostas expressivas. Você pode usar a sala de bate - papo para discutir esta questão; comentários anteriores foram movidos para lá.
Gilles 'SO- stop be evil'
4
Seu título diz programador, mas sua pergunta diz aluno. Geralmente 'programador' implica 'programador profissional' - então você está perguntando se é um problema ser um programador profissional sem o conhecimento da complexidade computacional? Ou se está tudo bem para um estudante de programação não ter esse conhecimento? As duas são perguntas diferentes, mesmo que elas tenham a mesma resposta.
corsiKa

Respostas:

42

Sim, eu diria que conhecer algo sobre complexidade computacional é uma obrigação para qualquer programador sério. Contanto que você não esteja lidando com grandes conjuntos de dados, você não terá problemas com a complexidade, mas se quiser escrever um programa que lide com problemas sérios, será necessário.

No seu caso específico, seu exemplo de localização de componentes conectados pode ter funcionado para gráficos de até nós. No entanto, se você tentasse um gráfico com nós, o algoritmo de seu professor provavelmente conseguiria isso em 1 segundo, enquanto seu algoritmo teria (dependendo de quão ruim era a complexidade) levado 1 hora, 1 dia ou talvez até 1 eternidade.100.000100100.000

Um erro bastante comum que os alunos cometem em nosso curso de algoritmos é iterar em uma matriz como esta:

while array not empty
    examine first element of array
    remove first element from array

Esse pode não ser o código mais bonito, mas em um programa complicado algo assim pode aparecer sem que o programador esteja ciente disso. Agora, qual é o problema com este programa?

Suponha que o executemos em um conjunto de dados de elementos. Comparado com o programa a seguir, o programa anterior executará mais lentamente.50.000100.00050.000

while array not empty
    examine last element of array
    remove last element from array

Espero que você concorde que ter o conhecimento necessário para executar seu programa vezes mais rápido é provavelmente uma coisa importante para um programador. Compreender a diferença entre os dois programas requer algum conhecimento básico sobre a teoria da complexidade e algum conhecimento sobre os detalhes da linguagem em que você está programando.50.000

Na minha linguagem de pseudocódigo, "remover um elemento de uma matriz" desloca todos os elementos à direita do elemento, sendo removida uma posição da esquerda. Isso torna a remoção do último elemento uma operação , pois, para isso, precisamos interagir apenas com 1 elemento. A remoção do primeiro elemento é pois para remover o primeiro elemento, precisamos mudar todos os outros elementos uma posição para a esquerda também.O ( n ) n - 1O(1)O(n)n1

Um exercício muito básico de complexidade é provar que o primeiro programa fará operações enquanto o segundo programa usa apenas operações. Se você conectar , verá que um programa é drasticamente mais eficiente que o outro.nn=100.00012n2nn=100.000

Este é apenas um exemplo de brinquedo, mas já requer um entendimento básico da complexidade para diferenciar os dois programas. Se você estiver realmente tentando depurar / otimizar um programa mais complicado que possua esse erro, é necessário um entendimento ainda maior para encontrar onde está o erro. Porque um erro como remover um elemento de uma matriz dessa maneira pode ser muito bem oculto por abstrações no código.

Ter um bom entendimento da complexidade também ajuda na comparação de duas abordagens para resolver um problema. Suponha que você tenha apresentado duas abordagens diferentes para resolver o problema dos componentes conectados por conta própria: para decidir entre eles, seria muito útil se você pudesse (rapidamente) estimar sua complexidade e escolher a melhor.

Tom van der Zanden
fonte
10
"So long as you are not dealing with huge data sets you will be fine not knowing complexity"Isso geralmente é verdade, mas nem sempre é assim. Por exemplo, um O(n!)algoritmo não será viável, mesmo para conjuntos de dados relativamente pequenos. Se você usar um O(n!)algoritmo em que você poderia ter usado, O(n^2)seu programa levará 36.288 vezes mais para ser executado em um tamanho de dados 10 . Em um tamanho de dados de 20, você está olhando para 2,4 quintilhões de operações.
reirab 13/02/2015
1
Acho que o exemplo do @ reirab deve ser incluído na resposta. É mais dramático e prova seu ponto de forma mais decisiva. E eu pessoalmente fui mordido por esses algoritmos, antes de aprender a complexidade computacional.
Siyuan Ren
2
Eu acho que há um problema maior em jogo. Se você simplesmente não sabe, seleciona tarefas onde isso não é necessário. Então você pode dizer quase todas as perguntas que eu preciso saber que o X acaba, pode ser útil. Portanto, independentemente de ser crítico, ainda é bom saber ou pode acabar mordendo a sua no final.
Joojaa
"Compreender a diferença entre os dois programas requer algum conhecimento básico sobre a teoria da complexidade" - acho que, para este exemplo em particular, não. Você pode criar um perfil, observar que o tempo todo é gasto em "remover elemento", saber (sem entender a teoria da complexidade) que remover o último elemento é mais rápido que remover o primeiro, fazer a alteração e, portanto, acelerar o programa. A vantagem de entender a teoria da complexidade é que ela permite quantificar livremente esses problemas sem criar um perfil deles, para que você possa "prematuramente" otimizar.
21715 Steve Jobs (
.. e, em geral, suspeito que todos ou quase todos os exemplos práticos possam ser resolvidos, um por um, sem referência à teoria da complexidade. Nesse caso, saber que copiar muitos dados é mais lento do que não fazê-lo, não é "teoria da complexidade". Mas é claro que ainda é útil na programação (e em qualquer profissão) ter um bom modelo mental de princípios que geralmente surgem, porque você pode analisar, discutir e resolver esses problemas rotineiramente por princípio, em vez de um de cada vez por meios ad hoc.
Steve Jessop
26

Esta é uma refutação da resposta de Tom van der Zanden , que afirma que isso é essencial.

O problema é que, na maioria das vezes, 50.000 vezes mais devagar não é relevante (a menos que você trabalhe no Google, é claro).

Se a operação que você fizer demorar um microssegundo ou se o seu N nunca estiver acima de um certo limite (uma grande parte da codificação feita atualmente), NUNCA importará. Nesses casos, pensar em complexidade computacional fará com que você perca tempo (e provavelmente dinheiro).

A complexidade computacional é uma ferramenta para entender por que algo pode estar lento ou com uma escala ruim e como melhorá-lo, mas na maioria das vezes é um exagero total.

Sou programador profissional há mais de cinco anos e nunca encontrei a necessidade de pensar em complexidade computacional ao fazer um loop dentro de um loop O (M * N), porque sempre a operação é realmente rápida ou M e N são tão pequeno.

Há coisas muito mais importantes, geralmente usadas e mais difíceis de entender para qualquer pessoa que faça trabalhos de programação (encadeamento e criação de perfil são bons exemplos na área de desempenho).

Obviamente, há algumas coisas que você nunca poderá fazer sem entender a complexidade computacional (por exemplo: encontrar anagramas em um dicionário), mas na maioria das vezes você não precisa disso.

claudio495h
fonte
3
Para expandir seu argumento, há casos em que muita ênfase na complexidade computacional pode levar você a se desviar. Por exemplo, pode haver situações em que o algoritmo "melhor" seja realmente mais lento para pequenas entradas. O criador de perfil é a fonte última da verdade.
Kevin Krumwiede
2
@Kevin Krumwiede, concordo plenamente com você que otimizar uma classificação para um conjunto de dados triviais é um exagero. Mas também ilustra que ter pelo menos uma compreensão da complexidade ainda é importante. O entendimento é o que o levará a tomar a decisão de que uma classificação de bolha é apropriada, em oposição a algum outro algoritmo mais complexo.
Kent A.
4
Quando você sabe que o conjunto de dados é pequeno em todos os casos, você pode se safar desse tipo de coisa. Você precisa ter muito cuidado com a complexidade excessiva em itens chamados dentro de loops - há pouco tempo, reduzi um tempo de execução de um minuto para um segundo dessa maneira. Também encontrei um problema de O (n ^ 8) uma vez (validação de dados). Muitos cuidados reduziram para 12 horas.
Loren Pechtel
7
Eu nunca encontrei a necessidade de pensar em complexidade computacional ao fazer um loop dentro de um loop O (M * N), porque sempre a operação é realmente rápida ou M e N são tão pequenas. - Ironicamente, o argumento que você dá mostra que você pensou em complexidade computacional. Você decidiu que não é um problema relevante para o que está fazendo e, possivelmente, por isso, mas ainda está ciente da existência desse problema e, se algum dia representar um problema, você poderá reagir a ele antes que sérias conseqüências ocorram no sistema. nível de usuário.
Wrzlprmft 15/02
4
A otimização prematura é a raiz de todo mal, mas a pessimização prematura é a raiz de pelo menos uma boa quantidade de usuários irritados. Pode não ser necessário resolver uma relação de recorrência, mas se você é, no mínimo, incapaz de diferenciar O (1), O (N) e O (N ^ 2), especialmente quando Ao aninhar loops, alguém terá que limpar a bagunça mais tarde. Fonte: as bagunças que tive que limpar mais tarde. Um fator 50.000 é tão grande que é melhor você saber se ainda pode pagar depois , quando seus insumos crescerem.
Jeroen Mostert
14

Desenvolvo software há cerca de trinta anos, trabalhando como contratada e como funcionário, e tenho tido muito sucesso nisso. Meu primeiro idioma era o BASIC, mas rapidamente aprendi a linguagem de máquina para obter uma velocidade decente da minha caixa de baixa potência. Passei muito tempo em criadores de perfil ao longo dos anos e aprendi muito sobre a produção rápida de código otimizado e eficiente em memória.

Independentemente de dizer, eu sou autodidata. Eu nunca encontrei a notação O até começar a entrevistar alguns anos atrás. Nunca aparece no meu trabalho profissional, EXCETO durante as entrevistas. Então, eu tive que aprender o básico apenas para lidar com essa questão em entrevistas.

Eu me sinto como o músico de jazz que não sabe ler partituras. Ainda posso jogar muito bem. Eu sei sobre hashtables (diabos, eu inventei hashtables antes de aprender que elas já haviam sido inventadas) e outras estruturas importantes de dados, e talvez até conheça alguns truques que eles não ensinam na escola. Mas acho que a verdade é que, se você quiser ter sucesso nessa profissão, precisará indie ou aprenderá as respostas para as perguntas que eles farão durante as entrevistas.

Aliás, recentemente entrevistei para uma função de desenvolvedor web front-end. Eles me fizeram uma pergunta em que a resposta exigia conhecimento de complexidade computacional e logaritmos. Consegui me lembrar de matemática suficiente de vinte anos atrás para respondê-la mais ou menos corretamente, mas foi um pouco chocante. Eu nunca tive que usar logaritmos em nenhum desenvolvimento de front-end.

Boa sorte para você!

Scott Schafer
fonte
2
Então, sua resposta é "sim"?
Raphael
6
TL; DR: "sim". No entanto, na minha experiência, você não estará falando sobre complexidade computacional na maioria dos trabalhos depois de ser contratado. Sim, conheça suas estruturas de dados e seu desempenho, mas apenas saiba que um algoritmo é O (n) ou o que não é um bom programador. É muito melhor se concentrar em escrever um bom código rapidamente e depois otimizar os pontos de acesso mais tarde. A legibilidade e a manutenção são geralmente mais importantes para a maioria dos códigos do que para o desempenho.
Scott Schafer
3
Eu acho que pode acontecer que a complexidade apareça em um ambiente corporativo, mas a primeira preocupação real das empresas é o envio : se funcionar, é bom o suficiente, até que haja orçamento disponível para melhorar o aplicativo ou um cliente volte para reclamar de problemas performances. Em situações B2B para projetos ad-hoc, provavelmente é bastante incomum. No b2c, ou em mercados altamente competitivos (produtos de prateleira), provavelmente surgiria com mais frequência, com o efeito direto de aumentar a barra de entrada para novos contratados.
didierc
4
@didierc "Bom o suficiente" é também o que quebra as coisas o tempo todo.
Raphael
1
@didierc 1) Bem, as pessoas com sólida formação em CS que (espero) tem uma boa intuição para o que é correto eo que não é, enquanto solucionadores de problemas ad-hoc podem cometer erros "simples". Garantir que a execução após compilações de múltiplas é exatamente o que foi especificado é altamente não trivial e, portanto, um problema não resolvido. 2) Não .
Raphael
9

A pergunta é bastante subjetiva, então acho que a resposta é que depende .

Não importa muito se você trabalha com pequenas quantidades de dados. Nesses casos, geralmente é bom usar o que quer que seja, por exemplo, a biblioteca padrão do seu idioma.

No entanto, quando você lida com grandes quantidades de dados ou, por algum outro motivo, insiste que seu programa é rápido, é necessário entender a complexidade computacional. Se não, como você sabe como um problema deve ser resolvido ou com que rapidez é possível resolvê-lo? Mas entender apenas a teoria não é suficiente para ser um bom programador. Para produzir código extremamente rápido, acredito, você também precisa entender como, por exemplo, sua máquina funciona (caches, layout de memória, conjunto de instruções) e o que o seu compilador faz (os compiladores fazem o melhor possível, mas não são perfeitos).

Em suma, acho que entender a complexidade claramente faz de você um programador melhor.

Juho
fonte
1
Eu acho que você geralmente tem a idéia certa, mas "subjetivo" não descreve esse problema adequadamente; "circunstancial" seria uma palavra melhor. Além disso, é possível escrever programas muito lentos que não operam com muitos dados. Recentemente, respondi a uma pergunta no math.se sobre representação / armazenamento polinomial. Isso geralmente envolve uma quantidade muito pequena de dados, por exemplo, ~ polinômios de 1000 termos são típicos; no entanto, existem enormes diferenças no desempenho no mundo real (centenas ou milhares de segundos vs. alguns segundos para uma multiplicação), dependendo da implementação.
Fizz
4

Certamente é um problema se alguém que está desenvolvendo algoritmos significativos não entende a complexidade do algoritmo. Os usuários de um algoritmo geralmente confiam em uma boa qualidade de implementação que possui boas características de desempenho. Embora a complexidade não seja a única colaboradora das características de desempenho de um algoritmo, é significativa. Alguém que não entende a complexidade do algoritmo tem menos probabilidade de desenvolver algoritmos com características úteis de desempenho.

É menos problemático para os usuários de um algoritmo, supondo que os algoritmos disponíveis sejam de boa qualidade. Isso é verdade para desenvolvedores que usam linguagens que possuem uma biblioteca padrão significativa e bem especificada - eles só precisam saber como escolher um algoritmo que atenda às necessidades. O problema ocorre quando existem vários algoritmos de algum tipo (digamos, classificação) disponíveis em uma biblioteca, porque a complexidade é frequentemente um dos critérios para escolher entre eles. Um desenvolvedor que não entende a complexidade não pode entender a base para escolher um algoritmo eficaz para a tarefa em questão.

Depois, há desenvolvedores que se concentram em (por falta de uma descrição melhor) preocupações não algorítmicas. Por exemplo, eles podem se concentrar no desenvolvimento de interfaces de usuário intuitivas. Esses desenvolvedores geralmente não precisam se preocupar com a complexidade do algoritmo, embora, novamente, possam contar com bibliotecas ou outro código sendo desenvolvido com alta qualidade.

Roubar
fonte
3

Depende, mas não da quantidade de dados com que você está trabalhando, mas do tipo de trabalho que você faz, dos programas que você desenvolve.

Vamos chamar programador que não conhece a complexidade conceitual noobish programmer.

O programador noobish pode fazer:

  • desenvolver bancos de dados de big data - ele não precisa saber como funciona por dentro, tudo o que precisa saber são regras sobre o desenvolvimento de bancos de dados. Ele sabe coisas como: o que deve ser indexado, ... onde é melhor fazer redundância nos dados, onde não é ...
  • criar jogos - ele apenas precisa estudar como funciona algum mecanismo de jogo e seguir seus paradigmas, jogos e gráficos de computador, que são um grande problema de dados. Considere 1920 * 1080 * 32 bits = cca 7,9 MB para uma única imagem / quadro ... a 60 FPS é pelo menos 475 MB / s. Considere que apenas uma cópia desnecessária da imagem em tela cheia desperdiçaria cerca de 500 MB de taxa de transferência de memória por segundo. Mas ele não precisa se preocupar com isso, porque ele só usa motor!

O programador noobish não deve fazer:

  • desenvolva programas complexos usados ​​com muita freqüência, independentemente do tamanho dos dados com os quais trabalha, ... por exemplo, dados pequenos não causarão um impacto perceptível em soluções impróprias durante o desenvolvimento, porque serão mais lentas que o tempo de compilação etc. segundos para um programa simples não são muito do ponto de vista de programadores noobish. Bem, considere o servidor servidor, que executa esse programa vinte vezes por segundo. Seria necessário 10cores para sustentar essa carga!
  • desenvolver programas para dispositivos embarcados. Os dispositivos incorporados funcionam com pequenos dados, mas precisam ser o mais eficientes possível, porque operações redundantes consomem energia desnecessariamente

Portanto, o programador noobish está bem, quando você quer apenas usar tecnologias. Então, quando se trata de desenvolvimento de novas soluções, tecnologias personalizadas, etc. Então é melhor contratar um programador não noobish.

No entanto, se a empresa não desenvolve novas tecnologias, apenas usa as já fabricadas. Seria desperdício de talento contratar programadores qualificados e talentosos. O mesmo se aplica: se você não deseja trabalhar em novas tecnologias e está bem em colocar idéias de clientes em projetos e programas usando estruturas já criadas, então é perda de tempo aprender algo que você nunca precisará, exceto se é seu hobby e você gosta de desafios lógicos.

kravemir
fonte
1
Essa resposta poderia ser melhorada se ela usasse um rótulo mais neutro ou nenhum rótulo, como a outra resposta que usava o termo "programador incompetente".
Moby Disk
1
Não sei o que você quer dizer com "complexidade conceitual". Minha experiência é que pessoas que não sabem o suficiente sobre árvores ou hashtables não podem tomar decisões inteligentes sobre como indexar (partes de) um grande banco de dados.
Fizz
3

Estou um pouco hesitante em escrever uma resposta aqui, mas desde que me encontrei falando sobre vários outros [alguns dos meus comentários foram movidos para o bate-papo], eis como eu o vejo ...

Existem níveis / graus de conhecimento em muitas coisas na computação (e, com esse termo, quero dizer mais ou menos a união da ciência da computação com a tecnologia da informação). A complexidade da computação certamente é um campo vasto (você sabe o que é OptP? Ou o que o teorema de Abiteboul-Vianu diz?) E também admite muita profundidade: a maioria das pessoas com um diploma em CS não pode produzir as provas de especialistas que são pesquisadas publicações em complexidade computacional.

O nível de conhecimento e habilidade / competência exigidos em tais assuntos depende muito do que se trabalha. A classificação O ( ) completamente sem noção às vezes é considerada uma das principais causas de programas lentos [citação necessário] , mas um artigo do SIGCSE de 2003 observou "A classificação por inserção é usada para classificar pequenas (sub) matrizes em bibliotecas padrão Java e C ++. " Por outro lado, a otimização prematura vinda de alguém que não entende o que significa assintótico (a complexidade computacional é uma medida) às vezes é um problema na prática de programação. No entanto, o ponto de saber pelo menos quando a complexidade computacional é importante é por que você precisa ter alguma pista sobre isso, pelo menos no nível de graduação.n2

Eu honestamente ousaria comparar a situação de saber quando aplicar os conceitos de complexidade computacional (e saber quando você pode ignorá-los com segurança) com a prática um pouco comum (fora do mundo Java) de implementar algum código sensível ao desempenho em C e o que não faz sentido coisas em Python etc. (como um aparte, isso foi chamado em uma palestra de Julia como "compromisso padrão" .) Saber quando você não precisa pensar em desempenho economiza tempo de programação, o que também é uma mercadoria bastante valiosa.

E mais um ponto é que conhecer a complexidade computacional não o tornará automaticamente bom em otimizar programas; você precisa entender mais coisas relacionadas à arquitetura, como localidade do cache, [algumas vezes] pipelining e hoje em dia também a programação paralela / multinúcleo; o último também possui sua própria teoria da complexidade e considerações práticas; uma amostra do último de um artigo do SOSP de 2013 "Todo esquema de bloqueio tem seus quinze minutos de fama. Nenhum dos nove esquemas de bloqueio que consideramos supera consistentemente qualquer outro, em todas as arquiteturas ou cargas de trabalho de destino. Estritamente falando, para buscar a otimização, um O algoritmo de bloqueio deve, portanto, ser selecionado com base na plataforma de hardware e na carga de trabalho esperada ".

Fizz
fonte
1
A longo prazo, desenvolver ou encontrar um algoritmo melhor geralmente é mais benéfico do que alterar a linguagem de programação para os bits sensíveis ao desempenho. Concordo com você que existe uma forte associação entre a falta de compreensão da complexidade e a otimização prematura - porque elas geralmente têm como alvo os bits menos sensíveis ao desempenho para otimização.
Rob
1
Na prática, os algoritmos de Schlemiel, o Pintor (inadvertidos) , são muito mais frequentes que a classificação O (n ^ 2).
Peter Mortensen
-1

Se você não conhece o big-O, deve aprender. Não é difícil e é realmente útil. Comece com a pesquisa e classificação.

Percebo que muitas respostas e comentários recomendam criação de perfil , e quase sempre significam usar uma ferramenta de criação de perfil .

O problema é que as ferramentas de criação de perfil estão espalhadas por todo o mapa em termos de quão eficazes são para encontrar o que você precisa para acelerar. Aqui, listei e expliquei os equívocos dos quais os criadores de perfil sofrem.

O resultado é que os programas, se forem maiores que um exercício acadêmico, podem conter gigantes adormecidos , que nem mesmo o melhor criador de perfil automático pode expor. Esta postagem mostra alguns exemplos de como problemas de desempenho podem ocultar dos criadores de perfil.

Mas eles não podem se esconder dessa técnica.

Mike Dunlavey
fonte
Você alega que "Big-Oh" é útil, mas defende uma abordagem diferente. Além disso, não vejo como o aprendizado "Big-Oh" (matemática) pode "começar com a pesquisa e a classificação" (problemas do algoritmo).
Raphael
@ Rafael: Eu não defendo uma abordagem diferente - é ortogonal. O Big-O é um conhecimento básico para entender algoritmos, enquanto que encontrar problemas de desempenho em softwares que não são brinquedos é algo que você faz depois que o código é escrito e executado, não antes. (Às vezes, os acadêmicos não sabem disso, então continuam ensinando o gprof, fazendo mais mal do que bem.) Ao fazer isso, você pode ou não achar que o problema é o uso de um algoritmo O (n * n), portanto, você deve ser capaz de reconhecer isso. (E Big-O é apenas uma propriedade matematicamente definido de algoritmos, não é um assunto diferente.)
Mike Dunlavey
"E big-O é apenas uma propriedade matematicamente definida de algoritmos, não um assunto diferente." - isso está errado e perigosamente. "Big-Oh" define classes de funções ; por si só, não tem nada a ver com algoritmos.
Raphael