J'ai eu récemment d'écrire l'algorithme suivant:algorithme: Sélection d'éléments communs d'une collection
Compte tenu d'un groupe de balises, et un groupe de messages de blog, où un billet de blog peut contenir zéro à -plusieurs étiquettes, renvoient les étiquettes communes à tous les articles.
Cette comparaison est fait en mémoire - l'accès soit collection ne pas la cause d'un voyage à travers le réseau (par exemple, à une base de données, etc.).
En outre, la collection Tags ne contient pas de référence à BlogPosts qui la contient. BlogPosts ont une collection de Tags qu'ils contiennent.
Voici ma mise en œuvre. Cela fonctionne très bien, mais je suis curieux de savoir s'il y avait une meilleure façon de l'implémenter.
Mon implémentation est dans Actionscript, mais je suis plus curieux du point de vue des algorithmes, donc les exemples dans n'importe quelle langue sont bons. (Mais si je ne connais pas la langue, je peux vous demander de clarifier certains aspects)
Tous les exemples d'améliorations seraient grandement reçus.
private function getCommonTags(blogPosts:Vector.<BlogPost>):Vector.<Tag>
{
var commonTags:Vector.<Tag> = new Vector.<Tag>();
if (!blogPosts || blogPosts.length == 0)
return commonTags;
var blogPost:BlogPost = blogPosts[0];
if (!blogPost.tags || blogPost.tags.length == 0)
return commonTags;
commonTags = Vector.<Tag>(blogPosts[0].tags);
for each (var blogPost:BlogPost in blogPosts)
{
if (!blogPost.tags || blogPost.tags.length == 0 || commonTags.length == 0)
// Updated to fix bug mentioned below
// Optomized exit - there are no common tags
return new Vector.<Tag>();
for each (var tag:Tag in commonTags)
{
if (!blogPost.containsTagId(tag.id))
{
commonTags.splice(commonTags.indexOf(tag),1);
}
}
}
return commonTags;
}
Je ne sais pas Actionscript, mais ce code fonctionnera plus vite si vous pouvez commander à peu de frais le blogposts par blogPost.tags.length. Aussi je pense qu'il y a un bug quand le premier post a 2 tags et le second 0, il va retourner les 2 tags du premier post. –
@ krusty.ar Merci! Tri par le nombre de tags est une excellente idée. Je pense que le bogue que vous mentionnez provient d'une mauvaise modification de la variable en mon nom - j'ai édité le code, faites le moi savoir si vous voyez toujours le bogue (je ne le fais pas). –
Ok, supposons que blogPosts [0] .tags.lenght == 2 et blogPosts [0] .tags.lenght == 0, le premier passage de chaque boucle comparera les 2 tags du premier post avec les 2 tags de le premier post, qui sont identiques, donc commonTags.lenght == 2, dans le second passage de la boucle, blogPost.tags.length == 0, donc la "sortie optimisée" est utilisée, mais toujours commonTags.lenght == 2 , donc vous renvoyez les balises du premier post, dont le second post n'a pas, la version correcte serait quelque chose comme le retour du nouveau vecteur.(); –