Quando 'código de otimização' == 'estruturação de dados'?

Um artigo recente de ycombinator lista um comentário com os princípios de um grande programador.

#7. Bom programador: eu otimizo o código. Melhor programador: eu estruturo dados. Melhor programador: qual a diferença?

Reconhecendo conceitos subjetivos e controversos - alguém tem uma posição sobre o que isso significa? Sim, mas gostaria de editar esta pergunta mais tarde com meus pensamentos, para não predispor as respostas.

Nove em cada dez vezes, quando você estrutura bem seu código / modelos, a otimização se torna óbvia. Quantas vezes você viu um ninho de vespas e o achou totalmente subótimo, onde, após a reestruturação, muitos redundâncias se tornaram extremamente óbvias.

Um designer sabe que alcançou a perfeição não quando não há mais nada a acrescentar, mas quando não há mais nada a ser levado. - Antoine de Saint-Exupéry

Um sistema bem estruturado terá uma natureza mínima e, devido à sua natureza mínima, ele será otimizado porque o pouco que existe nele se relaciona diretamente com o pouco que faz para atingir seu objetivo.

Editar: para expor sobre o ponto que outros se afastaram disso, também é completamente preciso ver a declaração como identificando a relação entre código e dados. Essa relação é assim: Se você alterar a estrutura de seus dados, precisará alterar seu código para respeitar a estrutura alterada. Se você deseja otimizar seu código, é provável que precise alterar a estrutura dos seus dados para torná-lo capaz de lidar com os dados da melhor maneira possível.

Dito isso, há uma possibilidade totalmente separada que estava sendo evitada aqui, e seria que esse sujeito que tenha relações com o YCombinator possa estar se referindo aos dados do código AS na tradição de homoiconicidade do LISP. É muito difícil supor isso como o significado em minha mente, mas é o YCombinator, então eu não descartaria que a citação esteja simplesmente dizendo que os LISPers são os "Melhores Programadores".

Eu acho que o autor está sugerindo que qualquer reestruturação dos dados leva à reestruturação do código. Portanto, a reestruturação dos dados com o objetivo de otimizar seu sistema também forçará você a otimizar seu código, solicitando "qual é a diferença?" resposta.

Observe que um "programador super excelente" pode responder a "qual é a diferença?" que ainda existe alguma diferença: depois de se aventurar em otimizar para melhorar o uso do cache da CPU, você pode manter o layout de suas estruturas de dados iguais, mas alterar a ordem na qual você as acessa pode fazer uma grande diferença. diferença.

Considere o exemplo mais óbvio disso - "a pesquisa de dados do usuário é muito lenta!"

Se os dados do usuário não estiverem indexados ou, pelo menos, classificados, a reestruturação dos dados resultará rapidamente em um melhor desempenho do código. Se os dados estiverem estruturados corretamente e você estiver apenas repetindo a coleção (em vez de usar os índices ou fazer algo como uma pesquisa binária), a modificação do código resultará em maior desempenho do código.

Programadores são solucionadores de problemas. Embora seja útil distinguir entre algoritmos e estruturas de dados, eles geralmente não podem existir isoladamente. Os melhores programadores sabem disso e não se isolam desnecessariamente.

Não concordo com a afirmação mencionada acima, pelo menos sem explicação. Vejo que a codificação é a atividade que envolve a utilização de algumas estruturas de dados. As estruturas de dados geralmente influenciam a codificação. Portanto, há uma diferença entre os dois na minha opinião.

Eu acho que o autor deveria ter escrito a última parte como "Melhor programador: eu otimizo ambos".

Há um ótimo livro (pelo menos era o que foi publicado) chamado: Algoritmos + Estruturas de Dados = Programas .

Às vezes, a otimização do código pode melhorar a velocidade em um fator de dois e, ocasionalmente, em um fator de dez ou até vinte, mas é isso. Isso pode parecer muito, e se 75% do tempo de execução de um programa for gasto em uma rotina de cinco linhas cuja velocidade possa ser facilmente duplicada, vale a pena fazer essa otimização. Por outro lado, a seleção de estruturas de dados pode afetar a velocidade de execução em várias ordens de magnitude. Um processador multiencadeado hiper otimizado moderno executando código super otimizado para procurar dados por chave em uma lista vinculada linear de 10.000.000 itens armazenada na RAM seria mais lento que um processador muito mais lento executando uma tabela de hash aninhada de codificação simples. De fato, se alguém tivesse os dados dispostos adequadamente, mesmo uma década de 1980 '

Dito isto, projetar estruturas de dados eficientes geralmente exige trocas mais complexas do que otimizar o código. Por exemplo, em muitos casos, as estruturas de dados que permitem o acesso mais eficiente aos dados são menos eficientes de atualizar (às vezes por ordens de magnitude) do que aquelas que permitem atualizações rápidas e aquelas que permitem atualizações mais rápidas podem permitir o acesso mais lento. Além disso, em muitos casos, as estruturas de dados ideais para grandes conjuntos de dados podem ser comparativamente ineficientes em relação aos pequenos. Um bom programador deve procurar equilibrar esses fatores concorrentes com a quantidade de tempo necessária para implementar e manter várias estruturas de dados e ser capaz de encontrar um equilíbrio decente entre eles.

As estruturas de dados geram muitas coisas em relação ao desempenho. Penso que podemos analisar os problemas duramente e por muito tempo com uma ideia preconcebida sobre a estrutura de dados ideal e, nesse contexto de pensamento, até criar provas (geralmente por indução) de otimização. Por exemplo, se colocarmos uma lista classificada em uma matriz e avaliarmos coisas como o custo para inserir um elemento, poderemos decidir, em média, que precisamos mudar 1/2 da matriz para cada inserção. Para cada pesquisa binária , podemos encontrar um item correspondente (ou não) nas etapas do log n.

Como alternativa, se adiarmos nossa decisão sobre a estrutura de dados (evitar a otimização prematura ) e estudar os dados recebidos e o contexto em que os usaremos, qual o tamanho, quais latências ocorrem e quais são importantes para os usuários, quanta memória temos vs. usaria com representações de dados que conhecemos ou podemos conceber.

Em uma área como classificação e pesquisa, há muito o que saber. Grandes programadores trabalham nisso há muito tempo. Compreender bem esses problemas é útil, e é ótimo se você conhece mais métodos do que quando terminou a graduação de estruturas de dados. Árvores binárias podem fornecer desempenho superior para inserções em troca de maior uso de memória. As tabelas de hash fornecem melhorias ainda maiores, mas ainda mais memória. Uma árvore de raiz e uma classificação de raiz podem levar a melhorias ainda mais.

A estruturação criativa dos dados pode ajudar a reformular um problema e abrir a porta para novos algoritmos que tornam os aplicativos difíceis mais rápidos e às vezes impossíveis tarefas.

Para articular meu melhor palpite sobre o significado do artigo, assumo um subtexto tácito (que parece estar ausente no artigo) que qualquer programador deve entender sobre otimização:

• a otimização ocorre somente depois que você instala o programa corretamente:
  • fazê-lo funcionar corretamente e, em seguida , rápido
  • esse princípio é o ponto da máxima de Knuth, "a otimização prematura é a raiz de todo mal"
• se e quando você determinar que a otimização não é prematura, você deve medi-la corretamente primeiro para determinar o que realmente precisa ser otimizado e novamente durante a otimização, para saber quais efeitos suas tentativas de otimização estão tendo.
  • se o seu código for executado em desenvolvimento, o criador de perfil é seu amigo nisso.
  • se o seu código for executado em produção, você deverá instrumentá-lo e, em vez disso, fazer amizade com seu sistema de registro.

Agora, então: suas medidas lhe dirão onde, no seu código, a máquina está queimando mais ciclos. Um programador "bom" se concentrará em otimizar essas partes do código, em vez de perder tempo otimizando as partes irrelevantes.

No entanto, é possível obter ganhos maiores observando o sistema como um todo e encontrando uma maneira de permitir que a máquina faça menos trabalho. Freqüentemente, essas alterações exigem uma reformulação da organização dos seus dados; assim, um programador "melhor" se encontrará estruturando dados com mais frequência do que nunca.

O "melhor programador" terá um modelo mental completo de como a máquina funciona, uma boa base no design de algoritmos e um entendimento prático de como eles interagem. Isso permite que ele considere o sistema como um todo integrado - ele não verá diferença entre otimizar o código e os dados, porque os avalia em nível arquitetural.

Melhor programador: qual a diferença?

Melhor programador? Não. Programador péssimo. Estou assumindo que a palavra "otimização" significa aquelas coisas que os programadores geralmente tentam otimizar, memória ou tempo de CPU. Nesse sentido, a otimização vai contra a maioria das métricas de software. Compreensibilidade, capacidade de manutenção, capacidade de teste, etc .: tudo isso é pouco quando a meta é otimizar - a menos que o que se está tentando otimizar seja a capacidade de compreensão humana, a capacidade de manutenção, a testabilidade, etc. Sem mencionar o custo. Escrever um algoritmo ideal de velocidade / espaço custa consideravelmente mais em termos de tempo do desenvolvedor do que codificar ingenuamente o algoritmo, conforme apresentado em algum texto ou diário. Um programador ruim não sabe a diferença. Um bom faz. O melhor programador sabe como determinar exatamente o que precisa ser otimizado e o faz criteriosamente.