Você já se perguntou como seus agregadores de notícias sociais favoritos, como Reddit ou Hacker News, classificam seus links? Eles usam alguns algoritmos de classificação simples para mostrar as histórias e comentários mais interessantes no topo. Então vamos ver como eles funcionam para que você possa começar a usá-los em seus próprios projetos.
Quente
ATUALIZAÇÃO : O hot
algoritmo do reddit mudou em 12 de janeiro de 2014. Escrevi um extenso artigo sobre o impacto dessa mudança em meu blog.
Este é o tipo de algoritmo usado para a página inicial. É muito mais simples do que você imagina. Ele calcula uma pontuação para cada item com base no número de votos e subtrai pontos com base na idade do item.
Uma versão simples desse algoritmo poderia ser assim:
score = upvotes - downvotes
score = score + age_in_seconds # newer means a higher age which should net a higher score
Na prática, essa implementação não é realmente útil, então vamos dar uma olhada em como o Reddit faz isso :
cpdef double _hot(long ups, long downs, double date):
"""The hot formula. Should match the equivalent function in postgres."""
s = score(ups, downs)
order = log10(max(abs(s), 1))
if s > 0:
sign = 1
elif s < 0:
sign = -1
else:
sign = 0
seconds = date - 1134028003
return round(order + sign * seconds / 45000, 7)
cpdef long score(long ups, long downs):
return ups - downs
Como você pode ver, o Reddit começa calculando uma ups - downs
pontuação simples que coloca em uma escala logarítmica. Por quê? Um link com pontuação de 5.000 é realmente muito melhor do que um com 4.000? Que tal 10 contra 30? Essa escala logarítmica reduz o impacto de votos adicionais, a menos que haja muito mais.
Em seguida, ele calcula um seconds
valor que é uma representação inteira da idade do link. De onde 1134028003
vem isso? É o carimbo de data / hora UNIX para quinta-feira, 8 de dezembro de 2005 7:46:43 AM UTC, a data em que introduziram a classificação quente ao público.
Finalmente, ele divide esse seconds
valor por 45.000, que é 12,5 horas. Isso significa que a cada 12,5 horas anteriores à quinta-feira, 8 de dezembro de 2005, as novas histórias têm 1 ponto a mais do que as anteriores.
É isso para o algoritmo de classificação quente, se você quiser ver exatamente como a escala do log e a idade afetam as classificações, eu o encorajo a ler este artigo detalhado sobre algoritmos de classificação do Reddit .
Topo
O algoritmo de classificação superior simplesmente determina quais itens têm as pontuações mais altas, ele não discrimina a idade e sempre retornará o item com a pontuação mais alta. Isso pode parecer bom o suficiente para um agregador de notícias, mas depois de apenas alguns dias, você notaria que a lista nunca muda. Este algoritmo oferece uma tremenda vantagem para os itens mais antigos e para aqueles que obtiveram uma vantagem de pontuação inicial, criando um efeito de bola de neve e enterrando qualquer item que não teve a sorte de obter alguns votos positivos iniciais.
Melhor
Este é um pouco mais complicado. Ele é usado para mostrar os itens com maior probabilidade de interesse no topo. Como isso faz? Usando o cálculo de um intervalo de pontuação de confiança . Mais especificamente, o Reddit usa o intervalo de pontuação de Wilson . Basicamente, um intervalo de pontuação de confiança leva em consideração a quantidade de votos para determinar se a pontuação representa adequadamente o valor do item. O algoritmo é menos confiante sobre a pontuação de um item com apenas alguns votos do que um com centenas de votos. Dessa forma, um item com 3 votos positivos pode ser classificado pior do que um com 300 centenas de positivos e uma dúzia ou mais de negativos.
Não vou detalhar o algoritmo do Reddit aqui, pois não há [números mágicos] ( https://en.wikipedia.org/wiki/Magic_number_(programming#Unnamed_numerical_constants) .
Mais uma vez, para mais informações e para ver como as votações positivas , negativas e o número de votos afetam a classificação, leia o artigo de Amir Salihefendic sobre algoritmos do Reddit .
Novo
Os itens mais recentes aparecem primeiro, eu não acho que preciso me preocupar em explicar este.