O algoritmo é mais importante que a linguagem de programação?

35

Durante o atual (2013) Jam do Google Code , houve um problema que levou as pessoas de C ++ e Java a mais de 200 linhas de código em comparação com as pessoas do Python que resolveram o mesmo problema usando apenas 40 linhas de código.

O Python não é diretamente comparável com o C ++ e o Java, mas a diferença de verbosidade que pensei talvez pudesse influenciar a eficiência do algoritmo.

Qual a importância de conhecer o algoritmo correto em comparação com a escolha da linguagem? Poderia um programa Python implementado de maneira excelente ser implementado em C ++ ou Java de uma maneira melhor (usando o mesmo algoritmo) e isso tem alguma relação com a verbosidade natural de certas linguagens de programação?

    
por superspacemarines 25.04.2013 / 06:14
fonte

9 respostas

73

Obviamente, se você considerar essa questão no contexto de algo como o Google Code Jam, então o pensamento algorítmico é claramente mais importante ao resolver problemas algorítmicos.

No dia-a-dia, no entanto, cerca de um milhão de outros fatores também devem ser considerados, o que torna a questão muito menos negra contra branca.

Apenas um contra-exemplo: se você precisar de mais 200 linhas em Java, mas todos na sua empresa conhecem Java, isso não é grande coisa. Se você pudesse escrevê-lo em 5 linhas de Python ou qualquer outra linguagem, mas você seria o único na empresa a conhecer essa linguagem - é um grande negócio. De fato, um negócio tão grande que você nem poderá fazer isso e, em vez disso, terá que escrevê-lo em Java.

Do ponto de vista de um artesão, sempre tentamos nos aproximar com a ferramenta certa para o trabalho, mas a palavra direita é tão complicada que é possível errar facilmente.

Pelo contrário, acho que o pensamento algorítmico nas empresas está quase ausente. Apenas poucas pessoas selecionadas o possuem, enquanto o joe comum geralmente já tem problemas ao estimar complexidades em tempo de execução de loops, pesquisas, etc.

Em termos de competições algorítmicas, no entanto, minha experiência pessoal de competir nelas por vários anos, claramente me diz que você deve se ater a um idioma. A velocidade é um fator importante e você simplesmente não pode se dar ao luxo de perder tempo com suas ferramentas, quando deve dedicar isso para resolver os problemas dentro do limite de tempo. Considere também que escrever 200 linhas de código Java sem pensar ainda é muito mais rápido do que criar manualmente 50 linhas de código Python complicado, exigindo muito raciocínio, mas ambos resolvendo mais ou menos o mesmo problema.

Ah, e finalmente, certifique-se de entender as principais diferenças entre o código de competição algorítmica e o código de produção da empresa. Vi codificadores algorítmicos fantásticos, que escreveram códigos horríveis que eu jamais aceitaria em um produto.

    
por 25.04.2013 / 07:18
fonte
17

Eu diria que, mesmo fora das competições, o pensamento algorítmico é mais importante do que conhecer todos os truques para um idioma específico.

É claro que você quer conhecer o idioma com o qual você trabalha da melhor forma possível, mas as linguagens vêm e vão, enquanto a capacidade de pensar abstratamente em termos de algoritmos é uma habilidade altamente transferível.

Caso em questão: se bem me lembro, houve um post aqui sobre os programadores há algum tempo em que alguém reclamou da falha do FizzBuzz em uma entrevista e culpou sua falta de conhecimento sobre o operador de módulo do Java para ele. Esta conclusão está errada - a falta de conhecimento sobre como o módulo funciona o fez incapaz de pensar algoritmicamente sobre o problema e resolvê-lo, mesmo na ausência de um operador de módulo dedicado. Indo mais longe: Java tem uma classe Tree - e se, no futuro, você tiver que trabalhar com uma linguagem que não implemente essa classe? Mais uma vez, a capacidade de pensar sobre o problema supera os detalhes específicos da linguagem.

Admito que os exemplos são simplistas, mas ajudam a mostrar o ponto.

    
por 25.04.2013 / 10:04
fonte
14

Idioma é importante.

A DARPA e a Marinha dos EUA fizeram um experimento tiroteio quase 20 anos atrás. O vencedor fugitivo foi Haskell. Ada e C ++ foram ambos representados; Java não foi.

Por volta da mesma época, Pratt & A Whitney realizou um estudo de mineração de dados em projetos de controladores de motores a jato, analisando os dados do cronômetro e do rastreador de bugs. Eles descobriram que Ada dava o dobro da produtividade do programador e 1/4 da densidade de defeitos de qualquer outra linguagem que eles estivessem usando.

A Atari costumava usar o FORTH para desenvolver videogames, e o fato de eles estarem usando o FORTH era considerado extremamente proprietário.

Os comentários de Paul Graham sobre o uso de LISP são bem conhecidos. Os comentários de Erann Gat no LISP no JPL são igualmente convincentes, embora não tão bem conhecidos.

O software Avionics Boeing 777 é praticamente todo Ada. Sua experiência foi muito boa, apesar de um grande subcontratado ter de recomeçar em meados de junho.

Idioma é importante.

    
por 25.04.2013 / 19:46
fonte
7

Alguns pontos:

  • As posições principais tendem a ser C ++ / C / Java, independentemente de quantas linhas de código a diferença esteja entre essa e alguma outra linguagem. Isso pode ser mais que os principais codificadores tendem a escolher essas linguagens em detrimento de outras, provavelmente por causa de sua velocidade bruta.
    Infelizmente você não pode ver facilmente a linguagem de programação no Google Code Jam, mas eu baixei alguns dos principais e, pelo que me lembro, estes são principalmente C / C ++. O TopCoder (um popular site de hospedagem de concursos de programação on-line) geralmente tem resultados semelhantes.

  • Como eles são de nível muito baixo, tenho certeza de que você não vai superar facilmente o C / C ++ em termos de tempo de execução bruto (e o Java também não segue muito atrás). Pela minha experiência, as linguagens tipadas dinamicamente tendem a ser significativamente mais lentas do que as linguagens com tipagem estática. A solução ideal pode não ser rápida o suficiente em alguns idiomas, mas isso não deveria ser uma regra geral.

  • O algoritmo correto é vital. Se você soubesse como resolver todos os problemas (com grande detalhe) desde o começo, e você é um bom codificador rápido, você provavelmente ganhará, independentemente do idioma em que você codificar (assumindo a solução ideal naquele idioma) é rápido o suficiente).

  • Número direto de linhas não é tão importante. Depois de obter experiência de programação suficiente, você saberá que pode gastar 10 minutos programando 10 linhas ou 200 linhas, tudo depende da complexidade das linhas. Além disso, se você codificou um código semelhante centenas de vezes, poderá fazê-lo rapidamente. Também não menciono todas as macros que os principais codificadores C / C ++ costumam usar para otimizar seu tempo de codificação.

  • Frank faz um bom argumento - (fora das competições de programação) você não pode codificar em Python para sua empresa se a base de código inteira é em C ou qualquer outra coisa, você precisa estar em conformidade com o idioma deles. / p>

  • É razoavelmente fácil alternar entre idiomas, não é fácil acumular anos de conhecimento de pensamento algorítmico. Estou disposto a apostar que quase qualquer programador excelente pode mudar para outra linguagem (vagamente similar) em, digamos, uma semana. Talvez ele / ela não seja bom o suficiente para ganhar competições de programação nesse idioma (dê mais 2 semanas), mas terá os princípios básicos.

por 25.04.2013 / 11:05
fonte
5

A mesma lógica pode ser implementada melhor em C ++? Claro que pode, se por melhor você quer dizer mais rápido e mais eficiente de memória. O problema é que a quantidade de esforço necessária para isso é significativamente maior. Além disso, teoricamente, você poderia ir ainda mais abaixo e implementá-lo em C puro ou mesmo em ASM, o que levaria ainda mais tempo, mas você poderia ter um código ainda mais otimizado.

É claro que, no caso de competições como o Code Jam ou o TopCoder, não é nada demais, já que são apenas 40 linhas contra 200 linhas. Por outro lado, neste tipo de competição, o que mais importa é a complexidade de tempo / espaço do algoritmo. Enquanto na aplicação da vida real, YMMV, nestes tipos de competições O (n) algoritmo escrito nas línguas mais lentas sempre irá bater O (n²) escrito no mais rápido dos idiomas. Especialmente que haverá vários testes que são o pior cenário possível.

Mas além das competições, se estamos falando de grandes projetos da vida real, então não são mais 40 linhas contra 200 linhas. Em grandes projetos, a enorme base de código começa a ser um problema. Em que ponto você consegue:

C ++ vs Python?

OPurePythonélento.ÉporissoqueointerpretadorPythonpadrão(CPython)éescritoemC.PraticamentetodoscomfunçõesinternasescritascomoaltamenteotimizadasC.OPythontambémpodeserfacilmenteusadoemconjuntocombibliotecasC(viactypes ou como módulos cpython nativos ) e com bibliotecas C ++ através do Boost :: Python . Dessa forma, você pode escrever sua lógica de alto nível em Python, uma linguagem flexível, que permite uma rápida criação de protótipos e adaptação (o que significa que você pode passar mais tempo aprimorando e aprimorando seu algoritmo). OTOH, você pode escrever suas funções de biblioteca de nível inferior no módulo C ou C ++. Um ótimo exemplo de tal abordagem é o SciPy, que é uma biblioteca Python, mas, ainda assim, usa bibliotecas numéricas altamente otimizadas, como o ATLAS, o LAPACK, o Intels MKL ou o ACML da AMD.

    
por 25.04.2013 / 12:27
fonte
4

Na minha opinião, o que as pessoas consideram coloquialmente como "linguagens de programação" são, na verdade, três coisas separadas:

  1. Tipo de idioma e sintaxe
  2. IDE de Idiomas
  3. Bibliotecas disponíveis para um idioma

Por exemplo, quando alguém traz o C # em uma discussão, você pode pensar que ele está falando sobre a sintaxe da linguagem (1), mas tem 95% de certeza que a discussão envolverá o framework .Net (3). Se você não está projetando um novo idioma, é difícil e geralmente inútil isolar (1) e ignorar (2) e (3). Isso porque o IDE e a biblioteca padrão são "fatores de conforto", coisas que afetam diretamente a experiência de usar uma determinada ferramenta.

Nos últimos anos, também participei do Google Code Jam. A primeira vez que optei por C ++ porque tem um bom suporte para ler a entrada. Por exemplo, ler três inteiros de uma entrada padrão em C ++ se parece com isto:

int n, h, w;
cin >> n >> h >> w;

Enquanto em C #, o mesmo seria assim:

int n, h, w;
string[] tokens = Console.ReadLine().Split(' ');
n = int.Parse(tokens[0]);
h = int.Parse(tokens[1]);
w = int.Parse(tokens[2]);

Isso é muito mais sobrecarga mental para uma funcionalidade simples. As coisas ficam ainda mais complicadas em C # com entrada de múltiplas linhas. Talvez eu simplesmente não tenha descoberto um caminho melhor naquela época. De qualquer forma, não consegui passar na primeira rodada porque tive um bug que não consegui corrigir antes do final da rodada. Ironicamente, o método de leitura de entrada ofuscou o bug. O problema era simples, a entrada continha um número que era muito grande para um inteiro de 32 bits. Em C # int.Parse(string) lançaria uma exceção, mas em C ++ o fluxo de entrada do arquivo configuraria um determinado sinalizador de erro e falharia silenciosamente fazendo com que o desenvolvedor desavisado não tivesse conhecimento de um problema.

Ambos os exemplos demonstram como a biblioteca foi usada em vez da sintaxe da linguagem. O primeiro demonstra a verbosidade e o outro demonstra a confiabilidade. Muitas bibliotecas são portadas para múltiplos idiomas e algumas linguagens podem usar bibliotecas que não são especificamente construídas para elas (veja a resposta do @ vartec sobre o Python com bibliotecas C).

Para finalizar, saber o algoritmo certo ajuda. Em competições de codificação é crucial, especialmente quando recursos como tempo de execução e memória são propositadamente limitados. No desenvolvimento de aplicativos, é bem-vindo, mas geralmente não é crucial. A manutenção é mais importante lá. Isso pode ser alcançado aplicando-se padrões de design corretos, com boa arquitetura, código legível e documentação relevante, e todos esses métodos dependem muito de bibliotecas internas e de terceiros. Então, eu acho mais importante saber que tipo de rodas já foram inventadas e como elas se encaixam, então como fazer as minhas próprias.

    
por 26.04.2013 / 15:05
fonte
2

Se você quiser competir em competições de programação cronometrada, você deve aprender o idioma mais expressivo permitido na competição. Perl provavelmente seria o melhor, seguido por Ruby ou Python. Você ainda vai precisar de boa facilidade com algoritmos, mas pelo menos você não vai se atrapalhar escrevendo algo como

Integer prev = b.get(k)
if (prev == null) prev = 0
Integer v = a.get(k);
if (v == null) v = 0;
b.put(prev + v);

em vez de

b[k] += a[k]

Não se preocupe em aprender várias bibliotecas. Eles são todos muito parecidos e a documentação está online. Tornar-se fluente em idiomas mais expressivos fará de você um programador melhor (mas possivelmente frustrado) em idiomas menos expressivos. O oposto não é verdadeiro.

N.B.

A diferença entre 200 linhas de código e 40 linhas de código é enorme, e é ainda maior quando é a diferença entre um programa de 200.000 linhas e um programa de 40.000 linhas. Então, é a diferença entre uma equipe de cinco pessoas, mais um gerente e uma equipe de um ou dois.

    
por 25.04.2013 / 09:51
fonte
2

Qualquer algoritmo pode ser implementado em qualquer linguagem de programação. Afinal, não é a sintaxe que importa. Mas usar uma linguagem de alto nível como o Python tem suas próprias vantagens. Menos trabalho e menos quantidade de codificação. Então, para implementar um algoritmo em Python, você precisará de menos linhas do que o necessário em uma linguagem de baixo nível, como C.

O Python tem a maioria das estruturas de dados construídas em sua biblioteca. Mas em C, precisamos começar do zero e usar uma estrutura para criar tudo. Certamente existem diferenças entre a linguagem de alto nível e de baixo nível, mas a linguagem não deve impedi-lo de implementar qualquer algoritmo.

    
por 13.05.2013 / 13:37
fonte
2

Embora extrapolar o exemplo "40 LoC vs 200 LoC", dizendo "bem, apenas um quinto do LoC total é obviamente mais rápido para escrever, então deve ser melhor" pode parecer tentador, eu realmente acho que há pouca verdade a ser encontrado lá.

A otimização para o menor número de LoC quase nunca é uma boa ideia na minha opinião. Sim, todo LoC escrito é um potencial para erros, e você nunca precisa depurar o que você nunca escreveu etcetc. O ponto é otimizar a legibilidade e desacoplamento. Não importa se você resolve um problema usando um regex grande de 20 linhas, ao invés de escrever um módulo de 1k LoC. O regex será uma parede opaca, extremamente propensa a bugs, difícil de entender, um pesadelo para alterar sem alterar seu comportamento de maneiras não documentáveis, etc.

Livrar-se do clichê e da verbosidade que não agrega qualquer valor é bom, mas, por outro lado, usar algo como Java ou C #, ter conhecimento sobre padrões de projeto e ferramentas como resharper permite TANTA flexibilidade em refatorando o código, limpando-o ao longo do tempo, quebrando as coisas, etc., isso seria simplesmente MUITO mais difícil se você o tivesse escrito como um script Python muito menor ou um aplicativo Ruby.

Uma comparação muito reveladora: Eu preferiria ter 100k LoC de código C # desacoplado e coberto por teste, preenchido com material "overkill" como padrão de estratégia, fábricas etc, em vez de um aplicativo python 20k que "faz as coisas acontecerem". 5 vezes mais código ou não, a arquitetura ganha todos os dias.

Concordo plenamente que alguns tipos de trabalho são mais fáceis e convenientes em alguns idiomas, mas acredito mais em escolher seu idioma com base em quais ferramentas você precisa e quais são os requisitos (e podem estar em um futuro próximo).

    
por 26.01.2016 / 08:44
fonte