avoir / veut la liste d'algorithme correspondant
Je suis en train de mettre en œuvre un système de négociation d'objets sur un site de trafic élevé. J'ai un grand nombre d'utilisateurs qui gèrent chacun une liste et une liste de souhaits pour un certain nombre d'éléments spécifiques. Je cherche un algorithme qui me permettra de suggérer efficacement des partenaires commerciaux basés sur vos hanches et les désirs correspondant à la leurs. Idéalement, je veux trouver des partenaires avec le plus haut potentiel de négociation mutuelle (c'est-à-dire que j'ai une tonne de choses que vous voulez, vous avez une tonne de choses que je veux). Je n'ai pas besoin de trouver la paire globale potentielle (ce qui semble dur), il suffit de trouver les paires potentielles les plus potentielles pour un utilisateur donné (ou même juste quelques paires à fort potentiel, pas le monde. max). p> Exemple: P>
User 1 HAS A,C WANTS B,D
User 2 HAS D WANTS A
User 3 HAS A,B,D WANTS C
User 1 goes to the site and clicks a button that says
"Find Trading Partners" and the top-ranked result is
User 3, followed by User 2.
8 Réponses :
Bien sûr, vous pouvez toujours séparer le système en trois catégories; "Veut," "Haves" et "Open Offres". Disons donc que User1 a de l'élément A, User2 dispose d'un élément de b & C et commercialise ceux de l'élément A, mais utilisateur1 souhaite toujours l'élément D et User2 souhaite un élément E. SO User1 (en supposant qu'il est le "propriétaire") met une demande, Ou voulez-vous pour l'élément D et l'élément E, donc l'offre se tient et se trouve sur la liste "Open Offres". S'il n'est pas accepté ou édité dans les deux ou plus de jours, il est automatiquement annulé. Donc, User3 recherche l'élément F et l'élément G et recherchent la "liste des avoir" pour les éléments F & G, qui sont divisés entre User1 & User2. Il se rend compte que l'offre ouverte User1 et User2 inclut des demandes d'articles D & E, qu'il a. Il choisit donc de "rejoindre" l'opération, et il est accepté à leurs conditions, négocier et échanger des articles entre eux.
permet de dire que l'utilisateur1 veut maintenant un élément H. Il cherche simplement la liste "avoir" "avoir" pour l'élément et parmi les résultats, il trouve que User4 échangera l'élément H pour l'article I, quel utilisateur se trouve. Ils échangent, tout va bien.
Je ne pense pas que vous compris la question.
Vous pouvez le faire dans o (n * k ^ 2) code> (n est le nombre de personnes, k est le nombre moyen d'articles qu'ils ont / veulent) em> En conservant des tables de hachage (ou, dans une base de données, des index) de toutes les personnes qui ont et souhaitent des articles donnés, alors donnant des scores pour toutes les personnes qui ont des éléments que l'utilisateur actuel veut et que vous souhaitez que l'utilisateur actuel ait. Afficher les 10 ou 20 meilleurs scores.
-- Get score for @userid wants
SELECT UserHas.UserID, SUM(Items.Weight) AS Score
FROM UserWants
INNER JOIN UserHas ON UserWants.ItemID = UserHas.ItemID
INNER JOIN Items ON Items.ItemID = UserWants.ItemID
WHERE UserWants.UserID = @userid
GROUP BY UserWants.UserID, UserHas.UserID
O (n k ^ 2) pourrait être le meilleur que vous puissiez faire si vous vous souciez de la réponse optimale. Si vous pouviez cavalement choisir les gens que * probablement allait correspondre à ce que vous pourriez peut-être obtenir des résultats qui étaient presque aussi bons, mais en temps réel?
@John: Pour un seul utilisateur, cela ne prend que O (k ^ 2) - à moins que chaque utilisateur dispose de 10 000 haves / désirs, ce sera en temps réel. En supposant que vous utilisiez une base de données, des tables de haves, des désirs et une jointure interne sur des tables de poids et des utilisateurs devraient être assez rapides; Ou, comme Netflix, vous pourriez avoir une table pour les meilleures correspondances et le mettre à jour tous les jours ou deux.
Le SQL est utile - N'est-ce pas O (K LG K) dans le nombre d'articles? Vous devez traverser chacun des désirs, mais pour les Haves, vous pouvez trouver un identifiant donné dans LG K, s'il y a un index sur les articles.
@John: Il y a environ. k articles cet utilisateur veut; Pour chacun de ces articles, il y a environ. k utilisateurs qui l'ont. J'ai initialement indiqué en utilisant une table de hachage O (1), qui est là où je reçois O (k ^ 2) de.
Il suffit de le faire bc seulement. Qui résout tous les problèmes.
Je ne pense pas que vous compris la question.
Vous pouvez maintenir une liste par élément (en complément de la liste par utilisateur). La recherche d'article est alors sur place. Maintenant, vous pouvez autoriser votre recherche de force brute à votre force la plus précieuse en vérifiant d'abord les articles les plus précieux. Si vous souhaitez une recherche plus complexe (sans doute plus rapide), vous pouvez introduire un ensemble d'éléments qui se réunissent souvent comme des méta-articles et les recherchent d'abord.
i marque item par lettre et utilisateur par numéro.
m code> - nombre d'éléments dans toutes les listes de toutes les dispositions / veulent (avoir ou veulent, pas et ne veulent pas) li>
-
x code> - nombre d'utilisateurs. li>
ul> Pour chaque utilisateur, vous avez la liste de ses désirs et des Haves. LIGNE GAUCHE EST WIRE LISTE, DROITE Est une liste (les deux seront triés afin que nous puissions utiliser la recherche binaire). P> xxx pré> pour chaque paire d'utilisateurs que vous générez deux valeurs et stockez-les. Quelque part, vous ne le généreriez qu'une fois et que vous réaliser. Tri des premières table et générer une seconde, est O (m * x * journal (m / x)) code> + O (log (m)) code> et nécessitera o (x ^ 2) code> mémoire supplémentaire. Ces valeurs sont les suivantes: combien d'utilisateurs d'abord obtiendrais et combien d'autre (si vous voulez que vous puissiez modifier ces valeurs en leur multipliant par la valeur de l'élément particulier). P> 1-2 : 1 - 3 (user 1 gets 1) - (user 2 gets 3)
1-3 : 3 - 2
2-3 : 1 - 1
- Ajout / suppression d'élément -
O (m * journal (m / x)) CODE> (vous bouclez via la liste des utilisateurs / souhaitée et effectuez une recherche binaire sur la liste de tous les autres utilisateurs et actuellement Données) li>
- trouver la meilleure connexion -
O (1) ou O (x) code> (dépend de la mise à jour de la mise à jour du cache. Vous faites la mise à jour de l'utilisateur et faites ce que vous voulez avec Données pour revenir à l'utilisateur la meilleure connexion) li>
ul> par m / x code> i estimer le nombre d'éléments de la liste ou de la liste des utilisateurs d'un seul utilisateur. p> dans cet algorithme, je suppose que toutes les données ne sont pas T stocké dans la base de données (je ne sais pas si la recherche binaire est possible avec des bases de données) et que l'insertion / retrait de l'élément dans la liste est o (1) code>. p> PS . Désolé pour le mauvais anglais et j'espère que j'ai tout calculé correctement et qu'il fonctionne parce que j'en ai aussi besoin. Em> p> p> p>
D'accord, qu'en est-il de cela:
Il y a essentiellement des "piscines" géantes
Chaque "pool" contient des "sections". Chaque "piscine" est dédiée aux personnes qui possèdent un élément spécifique. Chaque section est destinée aux personnes qui possèdent cet article et y voulaient une autre.
Qu'est-ce que je veux dire:
piscine A (pour ceux qui demandent a)
- Section B (pour ceux qui demandent A qui ont B)
- Section C (pour ceux qui demandent A C, même s'ils ont aussi b)
piscine B
- Section A
- Section B
Piscine C
- Section A
- Section C
Chaque section est remplie de personnes. "Offres" consisterait d'un élément "demandé" et d'un "pack", vous êtes prêt à donner tout ou partie des articles pour obtenir l'article que vous avez demandé.
Chaque "transaction" est calculé par piscine .... Si vous voulez un article donné, vous allez sur les piscines des articles que vous seriez disposés à donner, et il trouve la section qui appartient à l'article que vous avez demandent.
De même, votre offre est placée dans les piscines. Vous pouvez donc immédiatement trouver toutes les personnes concernées, car vous savez exactement quels pools, et exactement quelles sections à rechercher dans, aucun tri nécessaire une fois entré dans le système.
et, alors, l'âge aurait une priorité, les plus anciennes seraient cueillies, plutôt que de nouvelles.
Yikes. L'espace requis ici est O (i ^ 2) où je suis le nombre d'articles? De plus, je pense ne résout pas le problème comme indiqué. Cela résout un problème connexe.
Ce problème semble assez semblable à Roomamates stables Problème . Je ne vois aucune chose tort avec l'implémentation SQL qui a obtenu les votes les plus élevés, mais comme certains suggèrent que cela ressemble à un problème de rencontre / match de la même manière que les lignes de problème de mariage stable mais ici tous les participants sont dans une piscine. La deuxième entrée Wikipedia a également un lien vers une solution pratique dans JavaScript qui pourrait être utile
Merci pour les conseils - je vais vérifier ceux-ci.
Supposons que vous puissiez récupérer vos articles, ou au moins triez-les. Supposons que votre objectif est de trouver le meilleur résultat pour un utilisateur donné, sur demande, comme dans votre exemple d'origine. (Optimisation des partenaires commerciaux afin de maximiser la valeur marchande globale est une question différente.)
Ce serait rapide. O (journal n) pour chaque opération d'insertion. Le pire des cas O (n) pour suggérer des partenaires commerciaux, mais vous avez tenu ceci en le délai de traitement.
user1 demande des partenaires commerciaux suggérés
- itérer sur leurs articles
article dans la valeur par la valeur.
- Itérate sur les Haves utilisateur
User2 pour chaque élément , dans la commande par le score de l'utilisateur.
- Compute Trade Valeur pour
User1 Trades-avec User2 .
- N'oubliez pas que le meilleur commerce jusqu'à présent.
- Gardez le hachage des utilisateurs traités jusqu'à présent pour éviter toute valeur de recharge pour un utilisateur plusieurs fois.
- se termine lorsque vous manquez de temps de traitement (votre garantie en temps réel).
Tri par la valeur de l'élément et la partition de l'utilisateur est l'approximation qui rend cela rapidement. Je ne suis pas sûr de la manière dont cela serait sous-optimal, cependant. Il existe certainement des exemples faciles où cela ne voudrait pas trouver le meilleur commerce si vous ne l'exécutez pas à la fin. En pratique, il semble que cela pourrait être assez bon. Dans la limite, vous pouvez le rendre optimal en le laissant courir jusqu'à épuiser les listes de l'étape 4.1 et 4.2. Il y a des coûts de mémoire supplémentaires associés aux listes inversées, mais vous n'avez pas dit que vous étiez la mémoire contrainte. Et généralement, si vous voulez une vitesse, il n'est pas rare d'échanger de l'espace pour l'obtenir.
Je ne pense pas que 4 est O (m). Si je l'ai bien compris, vous ithétiez la liste des utilisateurs de tous les utilisateurs et que chaque utilisateur vous calculez la valeur commerciale. Il aime o (m) + o (x * z). Où Z dépend de METOD que vous utilisez pour calculer la valeur commerciale.
Combien d'articles attendez-vous sur les listes de chaque utilisateur? Combien d'articles total sont là, s'il y a une limite du tout?
Cela semble être similaire à un algorithme correspondant à un site de rencontres. Vous pourriez que Google qui.
Votre exemple a le système générant un résultat pour un utilisateur spécifique. Voulez-vous trouver le meilleur résultat d'un utilisateur particulier, sur demande, ou souhaitez-vous trouver le meilleur ensemble global de partenaires commerciaux? Par exemple, il peut être préférable pour l'utilisateur1 et l'utilisateur2 de négocier une valeur de 10, mais si vous pouvez paire d'utilisateurs1 avec User3 pour la valeur 8 et User2 avec User4 pour la valeur 8, le total est de 16 au lieu de 10. Le TOTAL est au lieu de 10. Le TOTAL est au lieu de 10 ?