我最近不得不编写以下算法:
Given a group of tags, and a group of blog posts, where a blog post may contain zero-to-many tags, return the tags common to all posts.
这种比较是在内存中进行的 - 访问任一集合不会导致跨网络旅行(即,到数据库等)。
此外,Tags
集合没有对包含它的 BlogPosts
的引用。 BlogPosts
包含一组 Tags
。
下面是我的实现。它表现得很好,但我很好奇是否有更好的方法来实现它。
我的实现是在 Actionscript 中,但我对算法的角度更感兴趣,所以任何语言的示例都可以。 (但如果我不懂语言,我可能会要求你澄清一些方面)
任何改进的例子都会受到极大的欢迎。
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;
}
最佳答案
好吧,您只需要一个计算两个集合的交集的高效算法,因为您可以为两个以上的集合重复调用该算法。
一种快速算法是将第一个集合的项目添加到哈希表中,然后遍历第二个集合检查哈希表是否存在;如果是,则将其添加到要在交集中返回的项目列表中。
关于算法:选择集合的公共(public)元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4339238/