Software Cinema

剛剛跟學長討論到怎樣快速的作 Python list 的 intersection 以及 union. 當然直接用雙層 for-loop 的作法是很直覺, 但是相對來說就會需要 M x N 的 performance cost, 希望在利用 Python 本身語法跟資料結構的特性下, 可以有更容易的作法.

我是想到了用 dictionary 的 key 來紀錄的作法, 同時間也找到這個 mailing list 紀錄也說明了類似的作法, 就從他的範例稍作修改成為以下這樣 :

<br />def exclusion(list1, list2):<br /> int_dict = {}<br /> list1_dict = {}<br /> for e in list1:<br /> list1_dict[e] = 1<br /> for e in list2:<br /> if list1_dict.has_key(e):<br /> del list1_dict[e]<br /> return list1_dict.keys()<br /><br />def intersection(list1, list2):<br /> int_dict = {}<br /> list1_dict = {}<br /> for e in list1:<br /> list1_dict[e] = 1<br /> for e in list2:<br /> if list1_dict.has_key(e):<br /> int_dict[e] = 1<br /> return int_dict.keys()<br /><br />def union(list1, list2):<br /> union_dict = {}<br /> for e in list1:<br /> union_dict[e] = 1<br /> for e in list2:<br /> union_dict[e] = 1<br /> return union_dict.keys()<br /> <br />list_1 = [1,2,3,4,5,6]<br />list_2 = [3,4,5,6,7,8]<br /><br />print 'exclusion:', exclusion(list_1, list_2)<br />print 'exclusion:', exclusion(list_2, list_1)<br />print 'intersection:', intersection(list_1, list_2)<br />print 'union:', union(list_1, list_2)<br />
基本上就是利用 dictionary 的 key 不會重複的特性省掉一些麻煩. 不過嚴格來說這樣也可能還是 M x N 就是了.