Python標準庫Difflib有坑？ —— 兩個方法快速提升數(shù)據(jù)對比效率

一 前言

最近在開發(fā)的數(shù)據(jù)核對方案中用到了Python標準庫Difflib，本來它工作的挺符合預期，可當它遇到那個文件，仿佛遇到了克星，那文件才100行*77列的數(shù)據(jù)，經(jīng)它對比，居然耗時61s。這是無法接受的，因為后續(xù)線上流量抽取比對，絕非這點量級。該怎么破？

?

二 重現(xiàn)現(xiàn)象

以下是使用Difflib比對那個文件，數(shù)據(jù)量是100行*77列，耗時61s，如下：

好吧，那就降低數(shù)據(jù)量到5行*77列，看看效果，耗時只有0.05s，如下：

從耗時結果上，不難發(fā)現(xiàn)，Difflib在這個文件的比對性能較差，而且耗時不隨數(shù)據(jù)量線性增加，這是最恐怖的地方，如果繼續(xù)增大數(shù)據(jù)量，耗時將會變得無法忍受。

?

三 優(yōu)化思路

Difflib作為標準庫，它的功能只是比對數(shù)據(jù)，然后生成各樣結果格式。當遇到耗時嚴重這類問題，首先應該從自己的數(shù)據(jù)上入手，我的優(yōu)化思路有兩個：

第一，?? 過濾掉相同的行數(shù)據(jù)，降低比對數(shù)據(jù)量；

第二，?? 數(shù)據(jù)分片；

針對第一個思路，將文件以行分割存放到列表，然后將列表相同位置的相同數(shù)據(jù)刪除掉，只剩下不同的行數(shù)據(jù)，這樣做的好處很明顯，一方面可以降低比對的數(shù)據(jù)量，提升效率，另外，輸出的結果也更干凈，不會再輸出無必要的相同行數(shù)據(jù)；

針對第二個思路，將待比對的數(shù)據(jù)劃分成一個個相對較小的數(shù)據(jù)塊，實現(xiàn)快速比對，這個方法的可行性，可以從上述數(shù)據(jù)量耗時比對得出。

?

四 具體實現(xiàn)

過濾相同行優(yōu)化策略，實現(xiàn)代碼如下：

#?過濾相同行
source_length?=?len(source)??#?source為原始數(shù)據(jù)按行分割的列表
target_length?=?len(target)??#?target為目標數(shù)據(jù)按行分割的列表
min_length?=?source_length?if?source_length?<?target_length?else?target_length?
pos_list?=?[]??#?標記相同行的行號,保留列頭
for?index?in?range(1,?min_length):
????#?注意保序
????if?operator.eq(source[index],?target[index]):
????????pos_list.append(index)
#?刪除相同行數(shù)據(jù),?注意索引漂移
source?=?[source[index]?for?index?in?range(source_length)?if?index?not?in?pos_list]
target?=?[target[index]?for?index?in?range(target_length)?if?index?not?in?pos_list]

數(shù)據(jù)分片優(yōu)化策略，實現(xiàn)代碼如下：

#?分片
max_length?=?source_length?if?source_length?>?target_length?else?target_length?#?用于分片
#?分片，注意保證不能漏行
start_pos?=?0
step?=?10??#?分片大小，即單次比對行數(shù)，默認10行
end_pos?=?start_pos?+?step
diff?=?difflib.HtmlDiff()??#?創(chuàng)建htmldiff實例對象
while?end_pos?<?max_length?+?step:
????detail_info?=?diff.make_file(source[start_pos:?end_pos],?target[start_pos:?end_pos])
????#?處理邏輯

?

五 優(yōu)化結果

在僅使用數(shù)據(jù)分片的優(yōu)化策略的情況下，比對那個100行*77列的文件，結果顯示比對耗時僅1.8s。而正如上文所述，優(yōu)化前比對該文件的耗時為61s，更重要的是，因為數(shù)據(jù)分片，每片比對耗時基本穩(wěn)定，即使數(shù)據(jù)量繼續(xù)增大，耗時也只是線性增加，而不再是類似指數(shù)型增加。另外，如果疊加過濾數(shù)據(jù)的第一種策略，相信隨著數(shù)據(jù)量的下降，耗時數(shù)據(jù)會有更好的表現(xiàn)。但為了更直觀的比對相同數(shù)據(jù)量下優(yōu)化前后的效果，所以，在此只是使用數(shù)據(jù)分片的策略。

優(yōu)化后耗時結果如下：

?

六 其他

本文針對Python標準庫Difflib比對文件時遇到的耗時嚴重問題，提出了兩種優(yōu)化策略，并經(jīng)測試驗證有效，即僅在數(shù)據(jù)分片策略下，同樣文件的比對耗時從原先的61s降到1.8s，且耗時只是線性增加。如果有更好的方法，歡迎留言、交流。

關于python學習、分享、交流，筆者開通了微信公眾號【小蟒社區(qū)】，感興趣的朋友可以關注下，歡迎加入，建立屬于我們自己的小圈子，一起學python。