J'essaie d'apprendre à coder un algorithme de site Web comme Reddit.com où il y a des milliers de messages qui doivent être classés. Leur algorithme de classement fonctionne comme ceci (vous n'avez pas à le lire, sa question plus générale que j'ai): http://amix.dk/blog/post/19588
À l'heure actuelle, j'ai des messages stockés dans une base de données, j'enregistre leurs dates et ils ont chacun un champ UPVOTes et Downvotes, donc je stocke leurs dossiers. Je veux comprendre comment stockez-vous leur classement? Lorsque des messages spécifiques ont des valeurs classées, mais elles changent avec le temps, comment pourriez-vous stocker leur classement?
S'ils ne sont pas stockés, classez-vous chaque poste chaque fois qu'un utilisateur charge la page?
Quand voudriez-vous stocker les messages? Exécutez-vous un travail de cron pour donner automatiquement chaque poste une nouvelle valeur toutes les minutes? Stockez-vous leur valeur? Qui est temporaire. Peut-être que ce message atteint son score minimum et est oublié?
3 Réponses :
Je ne voudrais certainement pas calculer leur rang chaque fois que vous les affichez.
Une solution simple et non performante ne serait pas de mettre en cache le classement des postes, et une fois le classement d'une publication change, vous effacez ou rafraîchissez le cache.
Ce n'est pas idéal, mais c'est possible.
Une autre façon serait de faire comme vous allez faire allusion: calculer et stocker des rangs dans la base de données (et les cache idéalement), puis rafraîchissez ces classements à l'aide d'un travail cron toutes les minutes.
Encore une fois, ce sont des approches fondamentales de ce que vous voulez faire. Vous pouvez ensuite les construire au fil du temps.
L'algorithme que vous choisissez sera probablement très particulier à vos besoins.
Vous devez également évaluer le type de trafic que votre site obtiendrait, car cela dicterait quel type de longueurs vous devriez passer pour obtenir le bon algorithme.
Je serais probablement stocker la valeur de classement dans la base de données? Et changer cela via le cronjob? Semble avoir le plus de sens. Y a-t-il des options plus avancées que je devrais rechercher?
Au niveau de la base, oui, stockez le classement dans une base de données. Soit dans la même table que le post, soit dans une table séparée. À partir de là, vous pouvez ensuite stocker ces valeurs dans le cache (comme APC ou MemCached) et référencez le cache lors de l'affichage ou de l'utilisation de classements, ou à tout le moins, la table "Classement" utilise le moteur Memory MySQL.
Pourquoi ne pas calculer leur rang chaque fois que vous les affichez? Ce n'est pas une formule très compliquée. O (1)
@Nacht parce que votre comptage post monte, le temps d'exécution de l'algorithme de calcul augmentera. La méthode sur la mouche n'a pas échoué, même à un niveau moyen.
Oh à droite, "grade" comme dans les par rapport aux autres, pas seulement un nombre indiquant à quel point c'est bon. Est-ce vraiment une différence aussi massive à commander par (classing_expr) par opposition à la commande par rang_field ? Les bases de données sont plutôt bonnes pour faire ce genre de choses rapidement ... la récupération de la valeur du champ prendrait beaucoup plus de calcul que tout calcul, avec l'exception possible d'obtenir l'heure actuelle. Cela ne peut peut-être pas le ralentir de plus que O (1) et probablement pas plus lentement que 2x.
ah j'ai oublié d'indexation ... cela fait probablement la différence
Mais à moins que votre colonne soit indexée, tout ce que j'ai dit là-bas s'applique toujours
@Nacht vous faites de bons points nacht. Néanmoins, de nombreuses considérations doivent être prises lors du choix d'un algorithme pour le problème de l'OP. Il est très possible que votre solution fonctionne pour un petit site Web (cela le ferait probablement). Mais que se passe-t-il si l'OP a besoin de l'échelle plus gracieusement? Comme les tables deviennent plus grandes, elles peuvent être écrites au disque avant de pouvoir être triées. Ceci est une procédure de taxation.
Je calculerais instantanément un score pour le vote unique sur une échelle pondérée par temps. J'enverrais ce score dans une file d'attente ou j'utiliserais pour incrémenter un champ en fonction de celui de ceux-ci pour vous.
À un intervalle de temps régulier, je prendrais tous les articles actuellement classés et tous les articles qui ont reçu des votes lors de la fenêtre de temps et réévaluer tous les articles classés suivis de tous les articles en file d'attente de l'ordre décroissant du score jusqu'à ce que j'aie suffisamment été calculé mon quota de classement.
La liste de classement serait mise en cache et utilisée jusqu'au prochain cycle de classement. Vous devrez adapter la période de conservation de la file d'attente (peut-être tout ce qui avait eu une activité dans les n files d'attente de la dernière est rétablie), la rétention d'articles, etc. basées sur votre charge de votre site, mais cela devrait être un point de départ bien performant.
J'ai 2 questions: lorsque vous résonnez un groupe d'articles, les autres utilisateurs doivent-ils attendre que la suppression de la transaction se termine pour lire les 100 meilleurs de la plupart des classés? En d'autres termes, la réanortition va-t-elle affecter d'autres utilisateurs? Une base de données NOSQL serait également comme Cassandra faire un meilleur travail à cela?
Si vous utilisez l'algorithme exacte Reddit utilise, il vous suffit de modifier le champ de classement à chaque fois qu'un élément est voté de haut en bas - et vraiment uniquement lorsque la différence entre les avotes et les bowvotes change d'ordre de grandeur. Cet article explique un peu plus sur la façon dont leur classement fonctionne.
http://bibwild.wordpress.com/2012 / 05/08 / reddit-histoire-classing-algorithme /
Fondamentalement, les votes de haut en bas servent uniquement à "déplacer" les postes. Si D est la différence entre le nombre de prospectes et de bowvotes, un poste est déplacé de 12 heures par ordre de grandeur de la D. autre que cela, c'est juste un classement de temps simple.
Si toutefois, vous souhaitez utiliser votre propre système de classement où l'âge de la publication est d'une manière d'une manière linéaire, vous devrez créer un champ indexé et recalculer le classement à des intervalles de temps, comme cela a été dit, ou simplement Mettez votre tri dans votre requête SQL, comme je l'ai dit dans mon commentaire. Mais les chances sont, vous pouvez trouver un moyen là où il ne doit pas être recalculé dedans et plus.
Vous voudrez peut-être regarder dans Lamernews: GITUB.COM/ANTIREZ/LAMERNEWS