前幾天做了一個作業,要求算出0-9999每一個的質因子計算出頻繁集。以前的簡單程序計算太慢,需要30多秒,仔細思考了一下,發現計算過程有很多的冗余。花了3個小時進行優化,結果改進到0.15s就可以算出來。

(1)優化1：不再區分每一個bucket對應的k頻繁集,而是將所有的頻繁集放在一個集合里面。

(2)優化2:針對每一個候選頻繁集的過濾,我們可以采取如下策略:因為候選頻繁集是由一個1頻繁集和k-1頻繁集合并得到的,所以我們只需要預處理所有1頻繁集對應的bucket，然后只在這些bucket里面進行查找即可。同時可以過濾掉所有長度小于k的bucket,因為k頻繁集也不可能是這些bucket的子集。

優化3:針對1頻繁集的優化,選擇利用collection模塊的Counter來進行計算,威力無窮,我們需要的就是把一個二維的輸入展開成一個一維的集合,然后利用Counter進行統計即可。怎么把二維展開成一維呢，利用itertools提供的chain函數(u for u in chain(*raw_data))就可以生成一個生成器,速度非?？?然后把這個生成器給Counter就ok了。

優化4：針對預處理的優化,我們在統計每一個1頻繁集對應的bucket時候,是從bucket開始遍歷,然后看該bucket里面有哪些1頻繁集。為了提高效率,可以利用filter進行過濾,這比你自己判斷要快的多。如果頻繁集的單個元素比較大(內存占用多),也可以考慮只存索引,在需要的時候再轉換回來。

def A_pri(raw_data,s,k):def get_singlgeitems():count = Counter((u for u in chain(*raw_data)))single_count = [set() for i in range(n)]count_filter = set(key for key,val in count.items() if val>=s)return count_filterdef convet_set(data):data_list = list(set(item) for item in data)return data_listraw_data = convet_set(raw_data)n = len(raw_data)single_items = get_singlgeitems()print('single done')data = [{key} for key in single_items]#preprocessD = defaultdict(list)for i,item in enumerate(raw_data):for single in filter(lambda x:x in single_items,(u for u in item)):D[single].append(item)for size in range(2,k+1):next = set()for single in single_items:check = list(filter(lambda x:len(x)>=size,D[single]))for k_item in data:tmp = {single}|set(k_item)tmp_tuple = tuple(sorted(tuple(tmp)))if len(tmp) < size or tmp_tuple in next:continue count = 0for subset in check:if tmp<=subset:count+= 1if count>=s:next.add(tmp_tuple)data = nextfor i in data:print(i)

最后給出生成x(1<=x<=9999)所有質數因子的代碼,利用素數曬法算出所有素數(小于9999),然后對每一個素數找它們的倍數并添加相應的素數。速度非常的快。

def get_primes(N):end = math.sqrt(N)+1nums = list(range(N+1))i = 2while i<=end: while i<=end and nums[i]==0:i+=1for j in range(i*2,N,i):nums[j] = 0i+=1return [x for x in nums if x!=0][1:]def gen_data(N):primes = get_primes(N)data = [[] for i in range(N)]for x in primes:for t in range(x,N,x):data[t].append(x)return data

總結

以上是生活随笔為你收集整理的A-priori算法的优化实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。