Quão importante é para um programador saber como implementar um algoritmo QuickSort / MergeSort da memória? [fechadas]

57

Eu estava revendo minhas anotações e deparei com a implementação de diferentes algoritmos de classificação.

Enquanto tentava entender a implementação do QuickSort e do MergeSort, ocorreu-me que, embora eu faça programação para ganhar a vida e me considere decente naquilo que faço, não tenho nem a memória fotográfica nem a inteligência para implementar esses algoritmos sem depender de minhas anotações. Tudo que lembrei é que alguns desses algoritmos são estáveis e outros não. Alguns levam O (nlog (n)) ou O (n ^ 2) tempo para completar. Alguns usam mais memória que outros ...

Eu sinto que não mereço esse tipo de trabalho se não fosse porque minha posição não exige que eu use qualquer algoritmo de classificação diferente dos encontrados em APIs padrão. Quero dizer, quantos de vocês têm uma posição de programação na qual é essencial que você se lembre ou invente esse tipo de coisa por conta própria?

    
por John Smith 07.10.2012 / 00:38
fonte

7 respostas

117

Vamos perguntar ao Albert e ver o que ele tem a dizer sobre o assunto:

“I don't need to know everything, I just need to know where to find it, when I need it”

-- Albert Einstein, paraphrased

Amém, irmão Albert, Amém.

Depois de fazer um bom levantamento dos algoritmos essenciais em qualquer disciplina específica (classificar, pesquisar, o que quer que seja), você pode esquecer os detalhes da implementação até precisar do algoritmo, caso em que você procura ou use um lib preexistente. Há 25 anos, construí um sistema de pesquisa principal usando árvores B *, mas hoje precisaria de RTFM para usá-las bem.

    
por 07.10.2012 / 04:21
fonte
48
  1. Não é realmente uma questão de memorização. É uma questão de entender profundamente as classes gerais de algoritmos como dividir e conquistar. Se você realmente entende dividir e conquistar, então você não precisa memorizar o quicksort. Você pode recodificá-lo no local, conforme necessário. Além disso, o retorno real não é nem mesmo ser capaz de redimensionar o quicksort por conta própria, é que você pode reconhecer quando um problema novo é passível de dividir e conquistar a solução.

  2. Nem todos os trabalhos de programação são iguais. Alguns trabalhos precisam de um profundo conhecimento de algoritmos, alguns precisam de pessoas que entendam a teoria dos tipos, e alguns precisam apenas de pessoas que possam coletar dados de um formulário da web e movê-los para um banco de dados. Alguns trabalhos até precisam de toda essa habilidade de uma só vez. Em que tipo de trabalho você quer trabalhar?

por 07.10.2012 / 03:16
fonte
10

Acho que a única vez que você precisa se lembrar de tudo é quando se candidata a um emprego quando precisa encontrar respostas no local e não tem recursos externos.

Alguns colegas de trabalho reescreveram quicksort e outros, mas eu continuo dizendo para eles voltarem a usar as funções internas de classificação que estão na linguagem. Eu sei que, dependendo do tipo de projeto em que trabalhamos, temos que nos lembrar de outros algoritmos, já que eles não são normalmente incluídos em bibliotecas padrão, mas a classificação não é uma que aparece, já que geralmente é embutida na linguagem.

No entanto, quando precisamos nos lembrar desses algoritmos, geralmente consultamos o Google ou um livro, e geralmente não estamos procurando uma implementação específica, mas qual seria a melhor implementação para o nosso problema.

    
por 07.10.2012 / 01:02
fonte
6

Basta lembrar qual algoritmo é útil em quais cenários, seria mais que suficiente para ajudar durante o seu trabalho. Na verdade, a maioria dos trabalhos de programação não requer a memorização da abordagem, ao contrário, eles estão interessados na sua maneira de reconhecer o padrão algorítmico quando confrontados com o problema .

Na verdade, há abundância de informações na maioria dos blogs / artigos de programação sobre tópicos de algoritmo. Assim, memorizar a implementação exata não tem importância. A informação mais valiosa seria obter uma ideia básica sobre que tipo de algoritmo está disponível, e qual é o problema específico que eles têm de bom na solução . Pesquisar a implementação exata assim que você souber o que está procurando é muito rápido.

Em resumo, é sempre melhor saber o que você procura e onde estão as referências - que o guiarão até a origem.

    
por 07.10.2012 / 00:57
fonte
5

A implementação exata não é muito importante. Mas o princípio por trás do mergesort / quicksort - recursão, particionamento, etc, é muito básico, e todo programador deve entender. Estes algoritmos são realmente muito simples de descrever em palavras, uma vez que você entenda.

Não é realmente um problema se você pode consultá-lo ou se você pode pesquisar no Google, é se o programador entende essas técnicas de solução de problemas e é capaz de se aplicar a outras situações.

    
por 12.10.2012 / 18:25
fonte
3

Eu sou de duas mentes sobre este assunto. Eu conheço muitos programadores que não sabem o que é um algoritmo de classificação, mas fazem o seu trabalho razoavelmente bem. Eu também acredito em entender princípios para realmente entender o domínio.

É difícil para mim ter uma resposta imparcial sobre este assunto, já que tenho programado por tanto tempo que provavelmente já esqueci mais algoritmos que conheço atualmente - mas ainda conheço os triagens mencionados nesta questão. Eu acho que os líderes em Agile (por exemplo, Ron Jeffries, Alistair Cockburn) têm algumas boas ideias perto desta ideia (por exemplo, Shu-Ha-Ri).

Em resumo, para esta resposta desconexa: Definitivamente, use a API (NIH é um sinal de imaturidade do desenvolvedor), mas sempre entenda os princípios subjacentes. Espero que isso ajude.

    
por 07.10.2012 / 17:27
fonte
2

Classificar e pesquisar é incrivelmente importante, quer você seja um fã de Donald Knuth ou queira ser o próximo Larry Page. Dependendo do negócio em que você está e do nível de competição que você pode comandar entre seus candidatos, recomendo que inclua alguns dos conceitos a seguir na entrevista.

Classificando

  • Esboço de algum tipo de algoritmo de classificação.
  • Relacione alguns exemplos de algoritmos de classificação.
  • Compare / contraste dois tipos com diferentes características de desempenho.
  • Se eles não mencionarem o uso da memória, pergunte sobre isso.

Pesquisando

  • Nomeie quantos algoritmos de pesquisa você puder.
  • Compare / contraste dois algoritmos de pesquisa.
  • Faça o croqui de qualquer pesquisa que não seja de pesquisa linear.

Alguns podem dizer que exigir o código para esses algoritmos é um exagero, a menos que o trabalho esteja em uma ilha deserta sem conexão com a Internet. Outra consideração é que, se você tiver 30 minutos, e quiser perguntar sobre qualquer outra coisa, para muitos candidatos, implementar o tipo pode levar uma boa parte do seu tempo.

    
por 07.10.2012 / 04:35
fonte

Tags