0

今天上班有一个很简单的任务，就是拿一个rss feed，里面自然有入口元素，有些类似，不过更新日期比较晚。任务是将提要解析为唯一的条目元素列表，并根据更新日期获取类似条目元素中的最新条目元素，*强调文本*。我设计了一个算法，我认为它对于大型 rss 提要是最佳的，我想检查它并从这个组中获得 O 表示法：

所以我有一个函数可以执行 root.findall('entry') 并生成条目元素列表，所以......

def filter_entries(self,entries):
    d = dict()
    for entry in entries: # STEP 1
        job_link = self.get_job_link(entry) #helper function to extract href of link
        if job_link in d:
            d[job_link].append(entry)
        else:
            d[job_link] = [entry]
     for k,v in d.iteritems(): #STEP 2
         results.append(self.sort_entry_list(v)[0])

def sort_entry_list(self,entry_list): #STEP 3
    return sorted(entry_list,key=lambda entry: parser.parse(entry.find('updated').text), reverse=True)

现在：我知道#STEP 1 的 O 是 O(n) 因为它是一个简单的列表迭代，那么 #STEP 2 的 O 也是 O(m) 其中 m 是 d 的大小，而 #STEP 的 O 3 是 O(s)，其中 s 是要由 sorted() 函数排序的相似条目元素的大小。

所以算法 = O(m) + O(n) + O(s) <-- 对吗？

那么我如何推导出这些 max 函数的总和呢？另外，当 rss 提要有 500,000 个条目时，是否有更好的方法来做到这一点？

在此先感谢您的帮助

山姆

4

0 回答 0