算法：選擇一個集合

我最近寫了下面的算法的共同元素：算法：選擇一個集合

給定一組標籤，和一羣博客文章，其中一篇博客文章可以包含零至-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

算法：選擇一個集合

回答

相關問題