Eu acho que em Habré existem fãs da série do Vale do Silício . Nesta semana, pela primeira vez em todas as seis temporadas, eles mostraram um código grande - é claro, eu quero discutir imediatamente aqui.
Querendo humilhar o personagem principal Richard Hendrix, seu ex-chefe mostra em uma reunião um fragmento de seu antigo código. Lá, uma pesquisa linear é aplicada aos dados já classificados - para que a tarefa seja concluída, mas parece muito ineficiente.
O próprio Richard não argumenta que o código é ruim. No entanto, entre os espectadores da série, sua decisão encontrou repentinamente defensores, e agora me pergunto o que Habr pensa sobre a posição deles.
O fragmento de código conhecido de Richard tem a seguinte aparência:
int index = 0; while (!element.equals(sortedList.get(index)) && sortedList.size() > ++index); return index < sortedList.size() ? index : -1;
Aqui, uma pesquisa linear se alterna para cada elemento de uma lista classificada, até chegar à correta. Como regra, eles preferem a pesquisa binária em dados classificados, que cada vez divide o conjunto pela metade, descartando a metade inadequada como um todo (porque, com um aumento no volume de dados, o número de iterações no linear aumenta muito mais rapidamente que no binário). Mas no subreddit / r / SiliconValleyHBO, o seguinte comentário apareceu:
"Quero estudar um pouco e apontar que o" erro "de Richard em usar a pesquisa linear em vez da pesquisa binária em dados classificados acaba sendo mais produtivo em muitos casos. Com conjuntos de dados gigantes (acho que o limite está em milhões de elementos), a pesquisa binária é mais rápida. Mas, em geral, se seu conjunto de dados não for gigantesco, uma pesquisa linear será mais bem armazenada em cache pelo processador, mais adequada para o preditor de ramificação, e seu algoritmo também poderá ser vetorizado. As pesquisas lineares exigem mais iterações, mas cada uma é incrivelmente mais rápida que uma iteração de pesquisa binária. Isso é contra-intuitivo e contradiz tudo o que você aprendeu na universidade, mas é.
Este relatório é muito interessante e mostra alguns resultados surpreendentes de medições reais de desempenho. ”
E outros membros do segmento apoiaram o comentarista: sim, em teoria, todas as iterações são equivalentes, mas no hardware real com otimizações reais, tudo é completamente diferente. Como, o criador da série, Mike Judge, trabalhou no Vale nos anos 80, quando todos esses caches L1 e previsão de ramificação ainda não eram particularmente pronunciados, então o comportamento da CPU estava muito mais próximo do modelo ideal - este é o exemplo da série.
Para mim, como diz o comentário, tudo soa contra-intuitivo, mas tornou-se interessante descobrir se Richard poderia estar certo. Obviamente, isso interfere no fato de que nem todo o contexto é fornecido na série: por exemplo, não temos idéia de quantos dados foram repetidos. Por um lado, Richard trabalhou para o gigante da Internet Hooli, onde provavelmente teve que lidar com milhões de registros, mas, por outro, foi seu primeiro dia útil e não pôde ser imediatamente despejado em milhões. Colocamos a questão da seguinte maneira: mesmo que a pesquisa binária seja claramente melhor para a maioria das tarefas em Hooli, é provável que Richard tenha tomado a decisão certa por suas condições e outros personagens rirem dele em vão, sem conhecer o contexto?
Para entender, abri um relatório citado pelo Reddit. Como prometido, acabou sendo interessante (não é surpreendente, já que este é um relatório de Andrei Alexandrescu ), mas depois de analisar uma parte e clicar no restante, não vi medições comparativas de pesquisa binária e linear por lá.
Mas lembrei que em nossa conferência DotNext, o mesmo Alexandrescu também falou sobre desempenho. Abri a versão em texto de seu relatório, que criamos para Habr, e procurei a palavra "linear". Descobriu-se, entre outras coisas, apenas deu um exemplo de um cenário curioso no qual essa pesquisa seria muito mais eficaz que uma binária (pesquisando elementos correspondentes de dois conjuntos no caso em que esses conjuntos são idênticos) - mas esse é um caso muito específico, para o qual não há conclusão geral " a pesquisa linear está subestimada ".
Pesquisou o que a Internet moderna diz sobre isso - mas basicamente encontrou respostas para o Stack Overflow, onde eles simplesmente escrevem "use binário, menos iterações". Também houve casos em que eles tentaram fazer benchmarks, mas também não pareciam muito convincentes para mim.
Aqui, é claro, a opção implora "você precisa se comparar para ver tudo em hardware real".
Mas se durante todas as minhas visitas ao DotNext eu aprendi algo com dois Andreevs preocupados com o desempenho (Alexandrescu e Akinshina ), é uma percepção da frequência com que as pessoas avaliam incorretamente e o quanto não levam em consideração. Portanto, tenho pouca confiança em postagens aleatórias da Internet com valores de referência, mas para mim mesmo mais baixo.
Felizmente, existem pessoas em Habr que entendem muito mais do que eu (por exemplo, o mesmo Andrey DreamWalker Akinshin, que escreveu um livro inteiro sobre benchmarking). Portanto, se você entende o tópico - por favor, diga-nos nos comentários como tudo realmente é. Para que tamanho de dados uma abordagem linear ainda pode ser uma boa escolha? Qual a probabilidade de Richard ter feito tudo certo, mesmo que ele próprio não esteja pronto para defendê-lo?
E se não houver comentaristas com conhecimento, terei de conectar o Akinshin à bateria no próximo DotNext e fazer a referência.