一、背景

環(huán)境中，有多種數(shù)據(jù)規(guī)格很大，通常通過嵌套循環(huán)檢測，效率低下，不通用。

二、分析過程

大容量數(shù)據(jù)基本上以list為主，原來的檢測工具經(jīng)常用到如下代碼，甚至疊加嵌套:

code示例:list嵌套對賬查詢

for _a in a:
     if _a not in b:
            in_a_not_in_b.append(_a)

在上面代碼中，for循環(huán)遍歷a每個元素，not in實際上也是遍歷b的每個元素后，找到b中不存在a中存在的元素，本次循環(huán)一共執(zhí)行了a*b次，時間復(fù)雜度為O(n^2).這樣條件下，a,b數(shù)量越大，時間平方倍增長，若是a,b代表100w條數(shù)據(jù)，最壞情況下則要執(zhí)行1萬億次才能得到結(jié)果，耗時數(shù)小時。

三、解決方案

針對此類大容量已知對比解決的辦法有很多,都離不開排序和索引兩類，目前共使用以下幾種：

(1) 內(nèi)置函數(shù)set()的交并查找（索引類）

(2) 構(gòu)建索引改變數(shù)據(jù)結(jié)構(gòu)從list變?yōu)閐icr存?。ㄋ饕悾?/p>

(3) 利用數(shù)據(jù)庫自建索引的方式進行對賬（索引類）

(4) 使用排序算法（歸并，快排）對兩邊數(shù)據(jù)進行排序（排序類）

下面著重看下此各方法的適用性和對應(yīng)的效果結(jié)論。

3.0 使用排序算法（歸并，快排）對兩邊數(shù)據(jù)進行排序

在不排序的情況下，元素在列表中尋找自己可能要跨整個列表，如果兩個列表都排序，就能大幅減少這種情況，在此基礎(chǔ)之上，通過復(fù)制列表并將復(fù)制后的列表中已經(jīng)找到的元素刪除，會不斷提高查詢的速率：

效果：

code示例:利用排序進行對賬

# coding=utf-8
import copy
from random import random, randint


def add_list(start_num, end_number):
    s = []
    for i in range(start_num, end_number + 1):
        s.append(randint(start_num, end_number))
    return s


a = add_list(10, 100000)
b = add_list(10, 100000)
in_a_not_in_b = []

a_sort = sorted(a)
a_sort_copy = copy.copy(a_sort)
b_sort = sorted(b)
b_sort_copy = copy.copy(a_sort)
import time
t1=time.time()

for _a in a:
    if _a in b :
        in_a_not_in_b.append(_a)
print "(非排序)比較時間為：",time.time()-t1,"s"

t2=time.time()
for _a in a_sort:
    if _a not in b_sort_copy:
        in_a_not_in_b.append(_a)
    else:
        b_sort_copy.remove(_a)
print "（排序）比較時間為：",time.time()-t2,"s"

輸出為

(非排序)比較時間為： 100.325999975 s

（排序）比較時間為： 1.97900009155 s

優(yōu)點：

該方法是針對原方法的優(yōu)化，修改簡單，實行方便

缺點：

時間復(fù)雜度在O(nlogn)和O(n2)之間，優(yōu)化后的速度在大容量情況下滿足不了要求（上面的例子是10W，100W排序后實測也需要260秒）

3.1 內(nèi)置函數(shù)set()的交并查找

python自帶函數(shù)set是個將迭代對象轉(zhuǎn)換為無序集合的函數(shù)，本質(zhì)上是hash存儲，所以每個元素雖然無序但是hashcode固定，故而在查找元素時，比單純的list查找，有復(fù)雜度上的優(yōu)勢，見下圖：

所以原來的代碼變?yōu)椋?/p>

code示例:set差值尋不一致

in_a_not_in_b=set(a)-set(b)

或者

in_a_not_in_b=set(a).difference(b)

效果：

時間負載降至O(n),同樣100w數(shù)據(jù)規(guī)格下，只需要幾秒甚至更短時間就能完成

code示例:set效果比較

a = add_list(10, 1100000)
b = add_list(11, 1120000)

 

import time
t1=time.time()
in_a_not_in_b=set(a).difference(b)
print "比較時間為：",time.time()-t1,"s"

輸出：

比較時間為： 0.116999864578 s

優(yōu)點：

編寫簡單，代碼清晰，時間復(fù)雜度逼近O(n)，是最理想結(jié)果

缺陷：

set集合要求其元素一定要是能夠hash的,也就是不可變數(shù)據(jù)，但通常我們的數(shù)據(jù)是字典嵌列表的結(jié)構(gòu)，如：

[{u'status': 1, u'layer': u'', u'protocol': u'OPENFLOW', u'hardware': u''}....]

而字典（dict）格式并不是個可以hash的數(shù)據(jù)結(jié)構(gòu)，故在很多情況下，就算set優(yōu)點很多，我們也是無法使用的。

code示例:set集合元素必須可hash

set([{u'status': 1, u'layer': u'', u'protocol': u'OPENFLOW', u'hardware': u''}])

輸出：

TypeError: unhashable type: 'dict'

3.2 構(gòu)建索引改變數(shù)據(jù)結(jié)構(gòu)從list變?yōu)閐ict存取

雖然set集合無法用在我們大多數(shù)的數(shù)據(jù)結(jié)構(gòu)上，但依然提供了一種可行的思路。

現(xiàn)在litst中嵌套dict的數(shù)據(jù)換成另外一個可hash同時又能存儲及表達dict字典的值，利用元組（tuple）的不可變性，對dict進行編輯。

code示例:dict_list變?yōu)閠uple_list

# dict:
dict_list = [{u'status': 1, u'layer': u'', u'protocol': u'OPENFLOW', u'hardware': u''}]
# 在已知其中鍵值得情況下事先構(gòu)造一個元組key_tuple
key_tuple = (u'status', u'layer', u'protocol', u'hardware')
value_tuple = ()
tuple_list = []
for i in dict_list:
    hash_key = tuple()
    for key in key_tuple:
        hash_key = hash_key + (i.get(key),)
    tuple_list.append(hash_key)
print key_tuple
print tuple_list
print set(tuple_list)

輸出結(jié)果

key_tuple (u'status', u'layer', u'protocol', u'hardware')

tuple_list [(1, u'', u'OPENFLOW', u'')]

set(tuple_list) set([(1, u'', u'OPENFLOW', u'')])

如上拆成2組數(shù)據(jù)就可以利用set的hash進行排序，但key_tuple存在不確定性，比如在數(shù)據(jù)并不是每個字段都需要對比的情況下可以構(gòu)造成字典存?。?/p>

code示例:dict_list變?yōu)閠uple_list，提取部分key構(gòu)成index_map

# dict:
dict_list = [{u'status': 1, u'layer': u'', u'protocol': u'OPENFLOW', u'hardware': u''}]
# key_tuple減少參數(shù)
key_tuple = (u'status', u'layer')
index_map = {}
for i in dict_list:
    hash_key = tuple()
    for key in key_tuple:
        hash_key = hash_key + (i.get(key),)
    index_map[hash_key] = i
print "key_tuple", key_tuple
print "tuple_list", tuple_list
print "index_map", index_map

#輸出結(jié)果

key_tuple (u'status', u'layer')

tuple_list [(1, u'', u'OPENFLOW', u'')]

index_map {(1, u''): {u'status': 1, u'hardware': u'', u'layer': u'', u'protocol': u'OPENFLOW'} }

對index_map進行對賬后可以反查index_map的原數(shù)據(jù)，相比于之前占用了更多內(nèi)存空間，但對比效率還是很高。

效果：

code示例:dict_list變?yōu)閠uple_list后對賬效果展示

import psutil
import os

# dict:
dict_list = [{u'status': i, u'layer': u'', u'protocol': u'OPENFLOW', u'hardware': u''} for i in range(1, 1000000)]
dict_list2 = [{u'status': i, u'layer': i, u'protocol': u'OPENFLOW', u'hardware': u''} for i in range(1, 1000000)]

#記錄初始內(nèi)存

m1=psutil.Process(os.getpid()).memory_info().rss
# 在已知其中鍵值的情況下事先構(gòu)造一個元組key_tuple
key_tuple = (u'status', u'layer', u'protocol', u'hardware')
def transfer_tuple_list(key_tuple, dict_list):
    tuple_list = []
    for i in dict_list:
        hash_key = tuple()
        for key in key_tuple:
            hash_key = hash_key + (i.get(key),)
        tuple_list.append(hash_key)
    return tuple_list
t1 = time.time()
tuple_list1 = transfer_tuple_list(key_tuple, dict_list)
tuple_list2 = transfer_tuple_list(key_tuple, dict_list2)
in_tuple_list1_not_in_tuple_list2 = set(tuple_list1).difference(tuple_list2)
print "比較時間為：", time.time() - t1, "s"
print u'內(nèi)存使用為：%d M'%((psutil.Process(os.getpid()).memory_info().rss-m1)/1000/1024)

輸出：

比較時間為： 2.10100007057 s

內(nèi)存使用為：214 M

時間的縮短是以空間為代價進行平衡，消耗內(nèi)存214M,但對比時間依然只有幾秒。

（ps:案例中100w長度的list多是I/O，若是程序構(gòu)造，應(yīng)該使用生成器generator）

優(yōu)點：

能夠?qū)δ壳暗膌ist中嵌套dict的結(jié)構(gòu)進行索引，效率符合要求

缺陷：

將數(shù)據(jù)轉(zhuǎn)換的思路存儲hash的思路，針對list嵌套dict進行重新編輯形成list嵌套tuple，也可以將list嵌套list轉(zhuǎn)成list嵌套tuple，但是針對完全不同的dict元素或是更復(fù)雜的結(jié)構(gòu)則顯得很無力。

code示例:dict_list中數(shù)據(jù)key不統(tǒng)一的情況無法使用統(tǒng)一的key_tuple

dict_list = [{u'status': 1, u'layer': u'', u'protocol': u'OPENFLOW', u'hardware': u''}

    ,{1:2,3:4,5:6},[(1,2,3,4),[1,2,3,4]]]

key_tuple = (u'status', u'layer', u'protocol', u'hardware')#無法通用

由此可見，在更加復(fù)雜的情況下，該方法的局限性凸顯，仍然不夠通用，所以在此基礎(chǔ)之上必須要一個完整而統(tǒng)一的解決方案。

3.3 利用數(shù)據(jù)庫自建索引的方式進行數(shù)據(jù)整理對賬

通常情況下，list嵌套dict中的元素必有實際用途，構(gòu)建數(shù)據(jù)庫將兩個來源的數(shù)據(jù)統(tǒng)一結(jié)構(gòu)無論是適配、修改都非常方便:

code示例：利用sqlalchemy框架構(gòu)建數(shù)據(jù)庫存儲數(shù)據(jù)并比較

from sqlalchemy import Column, String, Integer
from sqlalchemy.ext.declarative import declarative_base

TableBase = declarative_base()


class Classify(TableBase):
    __tablename__ = "classify"
    priority = Column(Integer, primary_key=True, default=0)
    in_port = Column(Integer, primary_key=True, default=0)
    tag = Column(String(50), primary_key=True)

 

#。。。。

此處省略數(shù)據(jù)庫構(gòu)建，數(shù)據(jù)插入和該方法類函數(shù)

def reconciliation(self):


    q1 = self.dbf.query_by_filter(PortClassify.in_port, tag="A")
    q2 = self.dbf.query_by_filter(PortClassify.in_port, tag="B")
    #由于在數(shù)據(jù)庫存在索引，利用sql的except和intersection方法可以進行迅速對比

    self.dbf.except_queries(q1, q2).all()
    self.dbf.except_queries(q2, q1).all()

效果：

import time
def reconciliation(self):
  t1 = time.time()


  q1 = self.dbf.query_by_filter(PortClassify.in_port, tag="A")
  q2 = self.dbf.query_by_filter(PortClassify.in_port, tag="B")
  #由于在數(shù)據(jù)庫存在索引，利用sql的except和intersection方法可以進行迅速對比

  self.dbf.except_queries(q1, q2).all()
  self.dbf.except_queries(q2, q1).all()  

print "比較時間為：", time.time() - t1, "s"

輸出為：

比較時間為： 3.0150001049042 s

優(yōu)點：

功能強大，全面，適用性高，對賬只是該方案的其中一項功能，且速率達到O(n)

缺陷：

編寫難度較大，為了對賬去構(gòu)建數(shù)據(jù)庫代價較大，且插入速度依賴于系統(tǒng)cpu性能，數(shù)據(jù)量大的情況下插入時間可能會較長。

四、結(jié)論

上面四種方案各有千秋，一切皆以業(yè)務(wù)場景進行選擇。當(dāng)然也可以看到，前期代碼中的一些業(yè)務(wù)項添加唯一索引ID字段則只需要對賬反查即可出結(jié)果，對我們的代碼改進也是可以值得探討的。