今日の仕事で、RSS フィードを取得するという非常に単純なタスクがありました。RSS フィードには、当然エントリ要素があり、それらのいくつかは似ていますが、後で更新された日付になっています。タスクは、フィードを一意の entry 要素のリストに解析し、同様の entry 要素の最新の entry 要素 (更新された日付に基づく *強調されたテキスト*) を取得することでした。大規模な 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) <-- そうですか?
では、これらの最大関数の合計を導出するにはどうすればよいですか? また、RSS フィードが 500,000 エントリの場合、これを行うためのより良い方法はありますか?
助けてくれてありがとう
サム