Um programador competente deve conseguir criar seu próprio algoritmo de caminho mais curto?

58

Estou sofrendo uma crise de confiança na minha capacidade como programador de computador.

Ontem tentei criar meu próprio algoritmo de caminho mais curto para um gráfico e depois de algumas horas simplesmente joguei a toalha e aprendi o algoritmo de Dijkstra.

É esse o tipo de coisa que um bom programador deve ser capaz de "reinventar" em algumas horas ou estou sendo realista?

Bem, pelo menos eu fui capaz de reinventar o tipo de bolha: D

Programador iniciante
fonte
7
Alguém que faz interface do usuário por 20 anos provavelmente terá dificuldade em encontrar uma solução para um problema de outro domínio, em um curto período de tempo.
Coder
38
Passar muito tempo nos sites da SE dá a todos uma crise de confiança, eu acho! (Não que isso seja ruim). Felicidade na vida é encontrar o equilíbrio perfeito entre a aceitação do que é e o desejo de mudá-lo.
TrojanName
2
Eu não poderia reinventá-lo, mas tento me lembrar de como isso funciona. certifique-se de entender esta animação: upload.wikimedia.org/wikipedia/commons/2/23/…
Job
6
@Brian Tragedy do gênio local. Você quase nunca pode ser o melhor em nada.
Rei Miyasaka
7
um bom computador cientista deveria, mas não necessariamente um engenheiro de programador de computador ou software
Neil McGuigan

Respostas:

118

Um bom programador deve perceber que um ótimo algoritmo já foi escrito para resolver um problema e não perde tempo reinventando as rodas.

Duvido que Dijkstra tenha inventado o algoritmo de caminho mais curto em poucas horas, de modo que parece um padrão realmente alto para determinar se alguém é um 'bom programador'

GSto
fonte
25
@Nakilon - Os programadores que ignoram as soluções existentes estão apenas perdendo tempo e, se não estão perdendo tempo, estão criando uma solução pior. Veja: Todo mundo fazendo seu próprio esquema de hash de senha vs bcrypt.
Reponha Monica
10
@GSto: Segundo a Wikipedia, Dijkstra veio com o algoritmo em menos de uma hora: 20 minutos, monitores segundo a primeira nota na wikipedia: en.wikipedia.org/wiki/Dijkstra%27s_algorithm
woliveirajr
9
É um algoritmo relativamente simples, mas Dijkstra era muito talentoso e havia sido treinado em física teórica e matemática avançada. Não há nada como alguns anos escrevendo provas para melhorar a capacidade de projetar algoritmos.
Kevin cline
19
@woliveirajr - Bem, tenho certeza que Newton levou a mesma quantidade de tempo para elaborar as leis do movimento. Depois de pensar nisso por 20 anos primeiro.
Rook
6
@ Nakilon - Sim, é por isso que todo mundo escreve tudo em C, porque, caso contrário, você é apenas um codificador, usando a linguagem de alto nível de outra pessoa. Ah, espere, quero dizer montagem, caso contrário, você está apenas usando a linguagem de baixo nível de outra pessoa. Ah, espere, quero dizer acionar interruptores para trocar os circuitos elétricos, caso contrário, você está apenas usando o conjunto de instruções de outra pessoa. Ou você sabe, você pode simplesmente usar o que já está lá e trabalhar para criar algo novo . Por que perder tempo reinventando o algoritmo de Dijkstra quando você pode inventar algo novo, como um programa que o usa?
Reinstale Monica
54

É esse o tipo de coisa que um bom programador deve ser capaz de "reinventar" em algumas horas ou estou sendo realista?

Primeiro, você talvez esteja confundindo programação com ciência da computação teórica. Um programador fantástico precisa de um bom fundamento em ciência da computação, mas não precisa ser fantástico. Dijkstra era fantástico em ciência da computação.

Em segundo lugar, eu esperaria que qualquer pessoa com uma boa compreensão dos gráficos desenvolvesse seu próprio percurso de gráficos após um pouco de reflexão. Mas não é um algoritmo de caminho mais curto. O algoritmo de Dijkstra, em particular, é altamente sofisticado. Depois de entender, é óbvio. Mas a maioria das coisas é assim.

Você provavelmente poderia derivar algum tipo de algoritmo de caminho mais curto depois de experimentar algumas coisas e dar à idéia algum tempo. Mas não fique desapontado se isso levar horas ou até alguns dias. Isso é completamente bom e normal.

(Advertência: bem, você deve conseguir forçar o problema com força bruta em algumas horas no máximo, mas isso não produziria um algoritmo funcional, mesmo em gráficos relativamente pequenos.)

Konrad Rudolph
fonte
56
Não se preocupe, se a força bruta não está funcionando, você simplesmente não está usando o suficiente.
Robbie
2
+1 para esconder a diferença entre CS teórico e programação. A programação é a solução de problemas do mundo real, e o CS teórico existe para apoiar a programação. No entanto, o CS teórico não é 100% essencial na programação diária da maioria das pessoas.
26511 Phil
17

É esse o tipo de coisa que um bom programador deve ser capaz de "reinventar" em algumas horas ou estou sendo realista?

Definitivamente irrealista. As pessoas não "inventam" algoritmos em poucas horas. É preciso muito esforço e trabalho. Para citar este blog:

Em Programming Pearls, Bentley, citando Donald Knuth, diz "Embora a primeira pesquisa binária tenha sido publicada em 1946, a primeira pesquisa binária que funciona corretamente para todos os valores de n não apareceu até 1962".

e a versão de Bentley também era problemática quando implementada para grandes conjuntos.

Além disso, um bom programador sabe quais ferramentas estão à sua disposição e quando usá-las. Você não ganha pontos extras por originalidade ou por fazer coisas diferentes - você quer que funcione e funcione bem.

BlackJack
fonte
1
BlackJack, eu tive que participar deste fórum para salientar que Bentley não disse o que você afirmou que ele disse: Knuth disse isso, e Bentley o citou. Quando li seu comentário, achei que você fez uma boa observação, mas gosto de verificar minhas fontes e nunca tinha ouvido falar em Bentley. No entanto, ouvi falar de Knuth e posso confiar no que ele diz. Por favor, verifique suas fontes melhor da próxima vez.
Richard
8
@ Richard - O comentário foi "Em Programming Pearls, diz Bentley .." Knuth foi o primeiro a dizê-lo, mas minha fonte é Programming Pearls, não TAoCP, então escrevi o que Bentley escreveu. Não afirmei que Bentley é o autor - apenas citei o que é dito no livro. Uma grande quantidade de material nos livros não foi inventada pelos próprios autores, então não vejo por que você o vê dessa maneira.
precisa
Ao atribuir a cotação exclusivamente à Bentley, você deixa de receber o crédito de Knuth e, se a declaração de "Bentley" estiver errada, você colocará a Bentley na posição de ter produzido informações incorretas, em vez de apenas ter divulgado. A rigor, você não disse o que Bentley disse: se tivesse, você teria dito ", Bentley disse que Knuth disse isso ...". A citação é bem usada aqui, mas é tirada do contexto em que foi dita.
Richard
3
@ Richard - A citação que listei é diretamente do blog, que cita diretamente do livro (literalmente, acho que é a página 57 da primeira edição). Se você tiver esse problema com a declaração, entre em contato com o autor do blog e peça que ele mude.
precisa saber é o seguinte
1
@ Richard e BlackJack: vocês dois estão corretos, mas a atribuição ao autor original adiciona credibilidade e contexto à declaração. Minha edição deve ser suficiente.
Steven Evers
9

É muito improvável que você consiga encontrar uma solução melhor do que a que você pode escolher.

Criar um algoritmo melhor do que o considerado "o melhor" (no seu caso, o mais curto) não é algo que todos possam fazer. Provavelmente nem é possível.

Um bom programador deve ser capaz de entender a lógica por trás do algoritmo e por que é melhor ou pior (ou simplesmente inadequado para esse problema em particular) do que outros algoritmos que tentam resolver o mesmo problema.

(s) Ele também deve saber se é realmente o melhor caminho a seguir para resolver esse problema específico.

De qualquer forma, se você deseja praticar, ainda pode tentar escrever sua implementação pessoal de um algoritmo, tentando resolver um problema usando sua mente. Pode não ser o melhor, mas é uma boa prática para a solução de problemas.

Jose Faeti
fonte
6

Isso me lembra algo que li sobre a diferença entre "engenharia de software" (o que eu chamaria de programação) e as outras disciplinas de engenharia. Pensando bem, acho que foi o livro original de Design Patterns. Tenho certeza de que alguém aqui pode citar isso em cima de sua cabeça.

De qualquer forma, o ponto (embora não exatamente voltado para o design de algoritmos) era que as disciplinas de engenharia são codificadas; é provável que nenhum engenheiro civil gaste tempo tentando reinventar o feixe em I, mas os programadores fazem isso o tempo todo. O problema (e percebo que estou apenas ecoando os sentimentos de muitos) é que esse comportamento é um desperdício e propenso a erros, e serve ao ego mais do que à solução.

A ciência da computação me levou à programação e eu amo os dois. No entanto, sou um programador muito melhor do que um cientista da computação. Eu nunca acusaria você de ser incompetente porque não conseguiu reinventar o algoritmo de Dijkstra em uma tarde. Eu questionaria sua competência como programador se você não pudesse reconhecer um problema que poderia ser resolvido por meio de um algoritmo gráfico de caminho mais curto.

Dito isso, acredito que pensar em algoritmos e tentar projetar e implementar novos é (potencialmente) divertido e (quase) sempre instrutivo. Eu apenas tento separar claramente meu tempo de CS do meu tempo de programação. Para os programadores, nosso tempo (especialmente pago) é mais bem gasto resolvendo problemas práticos, em vez de outros problemas. Além disso, o tempo de CS quase sempre esmaga minha confiança.

Keith Layne
fonte
Oh, a ironia ... agora que posso comentar em qualquer lugar, devo excluir a resposta que me valeu esse privilégio? Deveria haver um distintivo para isso.
Keith Layne
Existe - Disciplinado , no entanto, se sua reputação for recalculada, você voltará a 1. #
ChrisF
Sim, esse é exatamente o meu ponto ... Eu estaria acima e além da disciplina naquele momento da IMO. Se eu convertesse minha resposta em um comentário antes da exclusão, eu poderia ter tudo ... sugiro um novo emblema chamado UberDisciplined para qualquer exclusão que faça com que você retorne ao novo status de usuário. :)
Keith Layne
3

Você não vai notar as mesmas coisas que todo mundo faz. Eu acho que é apenas um fato da vida que temos que viver. Muito disso se resume ao seu aprendizado passivo e aos modelos mentais que você desenvolveu como resultado deles.

Conheço alguns programadores muito inteligentes e competentes que tiveram que aprender a lei de DeMorgan na escola antes que pudessem fazê-lo de forma consistente. Por acaso, eu descobri o algoritmo de Dijkstra por conta própria (e tenho que admitir que tenho um pouco de orgulho disso), mas demorei muito tempo até que eu pudesse entender o tipo de bolha.

Mais famoso, Einstein, que você pensaria que seria um especialista em teoria dos nós, não conseguiu amarrar seus próprios cadarços até os dez anos de idade.

As chances são boas de que você, sem saber, tenha reinventado muitas coisas que muitos outros nunca teriam descoberto se não fossem ensinamentos explícitos.

Rei Miyasaka
fonte
3

Eu imploro para diferir pelo que a maioria das respostas diz. Embora eu não esperasse que um programador de qualquer nível fosse capaz de aparecer sozinho no algoritmo de Dijkstra, eu definitivamente esperaria que ele tivesse alguma maneira (eficiente ou não) de resolver o problema.

Por exemplo, você disse como um comentário secundário que conseguiu criar o tipo de bolha por conta própria. Eu sei que é o algoritmo de classificação mais fedido, mas você encontrou uma maneira de resolver um problema, e é isso que eu espero que os programadores sejam capazes de: encontrar uma maneira de resolver problemas.

É claro que investigar e encontrar soluções feitas por outros também funciona, mas o extremo desse ponto é um cara que não pensa em si mesmo e cujos programas são um compêndio de pesquisas no Google.

Acho que estou parecendo mais severo do que realmente quero, mas o que quero dizer é: espero que um programador seja criativo o suficiente para encontrar uma solução para um problema, mesmo que a solução seja com erros ou com erros.


Então, voltando ao seu caso, não acho que você deva inventar o algoritmo de Dijkstra, mas se você tiver a capacidade de escrever um algoritmo para experimentar várias possibilidades e encontrar o caminho mais curto sem terminar em um loop infinito, então você tem minha aprovação.

(BTW, minha aprovação conta na mesma ordem de importância que um cupom de lavagem de carro gratuito.)

Alfa
fonte
3
Concordo que sim, um programador competente deve ser capaz de criar um tipo de bolha ou seu equivalente. Pode até ser um uso produtivo do tempo para realmente implementá-lo e testá-lo, talvez apenas para entender melhor o problema. Mas acho que é preciso dizer que nenhum programador competente continuaria e realmente o usaria no código de produção. É isso que faz com que seus clientes voltem no próximo ano e se queixem de que, agora que eles têm mais dados para processar, seu algoritmo O (n!) Levará o dobro da idade do universo para ser concluído ...
Thomas Padron-McCarthy
Quem se importa se você pode inventar algoritmos, se você não consegue nem reconhecer quando é uma porcaria? A autocrítica é tão importante para um programador quanto a criatividade. Prefiro trabalhar com um programador que admite rapidamente quando eles sabem que sua própria solução está demorando muito ou é improvável que seja a melhor do que com um programador que quer reinventar cada roda porque isso machuca o ego de fazer o contrário.
Rei Miyasaka
Concordo com os dois pontos, mas acho que estamos medindo duas coisas diferentes. Uma é a capacidade do programador de resolver problemas (algo que considero essencial). Outra é a autocrítica (eu considero isso essencial, mas não para a programação: para a vida toda) e a capacidade de julgar o código (altamente desejável). Eu também diria que soluções que levam uma eternidade não são realmente soluções, são? ;)
Alpha
2

Sim, ele / ela deveria.

Pode ser o equivalente moral do tipo de bolha, mas acho que um bom programador deve conseguir criar pelo menos algo que funcione, por mais ineficiente que seja.

Desnecessário dizer que, se esse problema em particular surgisse, um bom programador procuraria primeiro se existe uma biblioteca para fazer isso por ele ou quais algoritmos publicados fazem isso e são fáceis de implementar.

Obviamente, muitas tarefas de programação são muito menos difíceis e nem todos precisam ser capazes de lidar com problemas tão difíceis. Mas você quer ter alguém com uma mente assim em sua equipe, porque você pode ter alguns problemas específicos do projeto, complicados, nos quais não pode confiar em muitas pesquisas científicas anteriores.

Hans-Peter Störr
fonte
1

Não se preocupe

Como programador Perl, eu nunca pretendo reinventar a roda. Esse é o trabalho da CPAN. Se houver um algoritmo ou módulo simples e bem suportado, nós o usamos. Se não houver um bom módulo, então nós inventar a roda. Essa é uma das melhores coisas sobre Perl.

Então, o que estou dizendo é o seguinte:

  1. Eu não recomendo reinventar a roda, mas quando você faz ...
  2. Tente não reinventá-lo completamente e ...
  3. Não se preocupe se você não pode fazê-lo. É por isso que temos uma comunidade de programação :-).
Dinâmico
fonte
Não se trata de reinventar, mas de resolver problemas em geral. Se você não tentar inventar as coisas por conta própria, nunca melhorará.
Nils
0

A teoria dos grafos e os algoritmos que se aplicam a ela parecem simples na superfície, mas geralmente estão longe dela. Você pensaria que a formação de gráficos não cruzados (planares) é simples, por exemplo, à primeira vista. No ano passado, examinei extensivamente esse problema (planaridade através da eliminação dos subgráficos de Kuratowski). Posso dizer, a partir dessa experiência, que as pessoas que escrevem esses algoritmos normalmente passam a duração de seus estudos de doutorado fazendo isso, e às vezes essa pesquisa é feita em equipes. E, como pesquisadores , esse é seu único foco de trabalho durante esse período de tempo. Não é sensato pensar que nós, engenheiros de campo, podemos esperar o mesmo. Como alguém aqui disse corretamente, é cegamente óbvio quando a solução está à sua frente. Esse sempre parece ser o caso!

Engenheiro
fonte
0

É esse o tipo de coisa que um bom programador deve ser capaz de "reinventar" em algumas horas ou estou sendo realista?

Eu diria que, se você é capaz de inventar um algoritmo para um problema conhecido como o Shortest Path sozinho, está sendo um péssimo programador.

Isso significa que você está ignorando uma história bastante antiga sobre o problema do Caminho Mais Curto , passando de um algoritmo O (| V | ^ 4) publicado em 1955 para o algoritmo O (E + V log V) publicado em 1984 (que é o de Dijkstra). algoritmo com árvores de Fibonacci). É quase garantido que você se sai pior do que os algoritmos já criados. Pior ainda, há uma boa chance de seu algoritmo ter lacunas ou erros, tornando-o incorreto. Além disso, você certamente passará muito mais tempo pensando em seu algoritmo, implementando-o e testando-o do que o tempo necessário para reutilizar um algoritmo existente.

Deixe o design dos algoritmos para os designers de algoritmos. Programadores são consumidores de seus resultados. Os programadores combinam algoritmos e os colocam para trabalhar em tarefas do mundo real. Um policial não precisa reinventar a lei para poder trabalhar ou ser um bom policial.

Até o encorajo a usar implementações feitas por especialistas, em vez de implementar você mesmo os algoritmos para qualquer algoritmo moderadamente complicado. É mais provável que esteja correto, as chances são de que sejam mais rápidas do que você nunca e isso poupa muito tempo. Isso é particularmente verdadeiro para algoritmos criptográficos, porque você recebe uma demanda adicional de segurança, que geralmente apenas especialistas podem fornecer.

Alex ten Brink
fonte
Os algoritmos criptográficos são fáceis de verificar uma implementação de; os vetores de teste corretos conhecidos são dez centavos para qualquer algoritmo especificado publicamente e estão corretos ou não. (Você pode obter desempenho abaixo do ideal com uma implementação personalizada, mas se estiver correta, isso pode ser resolvido.) A parte mais difícil da criptografia são coisas como geração aleatória de números, manipulação adequada de chaves brutas e tabelas de expansão de chaves na memória, adequada manipulação de entradas do usuário (salga, etc.), armazenando algo para permitir que você descubra se os dados descriptografados são válidos e assim por diante.
um CVn
Eu estava pensando mais ao longo das linhas de ataques de tempo, etc, coisas que quase nenhum programador conhece. Nem sempre é um problema, mas importante, no entanto. Além disso, a combinação de primitivas criptográficas geralmente não funciona como se espera, isso também é uma parte difícil da segurança.
Alex10 Brink #
Embora ataques de tempo etc. sejam certamente uma preocupação válida (e não apenas em criptografia), eu argumentaria que a suscetibilidade de uma implementação a tal não tem impacto em sua correção . E há muitas, muitas maneiras de se sujar na criptografia muito mais do que apenas permitir ataques de tempo. Bruce Schneier costumava dirigir sua série Doghouse ; Não vi nada nele recentemente, mas há muitos exemplos de advertência por lá. google.com/search?q=site%3Aschneier.com+%22the+doghouse%22
um CVn