算法：选择一个集合

我最近写了下面的算法的共同元素：算法：选择一个集合

给定一组标签，和一群博客文章，其中一篇博客文章可以包含零至-many标签，返回所有帖子通用的标签。

这种比较是在内存中正在做 - 访问任一集合不原因的跨网络跳闸（即，到数据库，等等）。

另外，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; 
    }

来源

2010-12-02 Marty Pitt

我不知道Actionscript，但如果您可以通过blogPost.tags.length便宜地订购blogpost，则此代码运行得更快。另外我觉得有一个错误，当第一篇文章有2个标签，第二个0，它会返回第一篇文章的2标签。 – 2010-12-02 20:28:23

那么，你只需要一个有效的算法来计算两个集合的交集，因为你可以反复调用两个以上的算法。

一种快速算法是将第一组的项目添加到散列表中，然后遍历第二组检查散列表以查看它是否存在;如果是，则将其添加到路口中要返回的项目列表中。

来源

2010-12-02 20:22:44 jason

我可以用英文句子陈述这个程序：“返回在帖子中统一发生的所有标签。“

给予名称all_tags到标签的列表，并post_tags到列表标签相关到岗位，我可以说同样的事情，这句话在J programming language

all_tags #~ (#=+/) all_tags e.&>"_ 0 post_tags

望着这在一些细节：

#~表示 “拷贝，其中”
(# = +/)指“帐簿等于总和”
e.意味着“存在于”
&>"_ 0修改e.这样的all_tags整体与在post_tags

如果每个标签集的比较我们想让这个程序有两个参数，而不是一个特定于这些命名列表的程序，相应的程序可能是：

common_to=: [ #~ [:(#=+/) [ e.&>"_ 0 ]

运行使用相同的数据名称，方案是这样的：

all_tags common_to post_tags

似乎值得指出的是，我们实际上并不需要标签的完整清单，因为这可以得出。（计算结果为~. ; post_tags。）这意味着我们可以编写程序来只接受一个参数。但由于问题假设我们已经计算了all_tags列表，因此不需要再次计算它。

来源

2010-12-03 15:51:40 kaleidic

算法：选择一个集合

回答

相关问题