刪除目錄下相同文件的python代碼(逐級(jí)優(yōu)化)

更新時(shí)間：2012年05月25日 23:14:02 作者：

讓我們來(lái)分析一下這個(gè)問(wèn)題：首先，文件個(gè)數(shù)非常多，手工查找是不現(xiàn)實(shí)的，再說(shuō)，單憑我們?nèi)庋?，在幾千張圖片里面找到完全相同的難度也是很大的

這兩天閑來(lái)無(wú)事在百度上淘了點(diǎn)圖片，不多，也就幾萬(wàn)張吧，其中有不少美女圖片奧！哈哈！這里暫且不說(shuō)圖片是怎么獲得的，咱聊聊得到圖片以后發(fā)生的事。
遇到的第一個(gè)問(wèn)題就是有些圖片沒(méi)有后綴名。在windows下，沒(méi)有后綴名的文件是不能正確被識(shí)別的，沒(méi)有預(yù)覽，打開(kāi)時(shí)還要選擇打開(kāi)方式，費(fèi)勁！這個(gè)問(wèn)題比較容易解決，給每個(gè)圖片加上后綴名就是了。沒(méi)有后綴名的圖片也不多，不到1000張吧，一張一張地改很麻煩，還好我是學(xué)計(jì)算機(jī)的，上午寫(xiě)了個(gè)程序批量修改http://www.dhdzp.com/article/30400.htm。這個(gè)問(wèn)題就算解決了。接下來(lái)又遇到了一個(gè)新問(wèn)題：圖片多了，難免出現(xiàn)重復(fù)的，有些圖片完全一樣，沒(méi)有必要都留著，我就想把所有的重復(fù)圖片都刪除。

讓我們來(lái)分析一下這個(gè)問(wèn)題：首先，文件個(gè)數(shù)非常多，手工查找是不現(xiàn)實(shí)的，再說(shuō)，單憑我們?nèi)庋?，在幾千張圖片里面找到完全相同的難度也是很大的。如果不是圖片而是其他文檔，在不能預(yù)覽的情況下要正確區(qū)分是很困難的。所以要用程序?qū)崿F(xiàn)。那么用程序怎么實(shí)現(xiàn)呢？根據(jù)什么判斷兩個(gè)文件完全相同呢？首先，根據(jù)文件名判斷是靠不住的，因?yàn)槲募梢员浑S意更改，但文件內(nèi)容不變。再說(shuō)在同一個(gè)文件夾下面，也不可能出現(xiàn)兩個(gè)完全相同的文件名，操作系統(tǒng)不允許的。還有一種方法就是根據(jù)文件大小來(lái)判斷，這不失為一種好辦法，但是，文件大小相同的圖片可能不一樣。再說(shuō)圖片一般都比較小，超過(guò)3M的基本沒(méi)有，大部分不夠1M，如果文件夾下面文件特別多，出現(xiàn)大小相同的的文件可能性是相當(dāng)大的。所以單憑文件大小來(lái)比較不靠譜。還有一種方法是讀取每張圖片的內(nèi)容，然后比較這個(gè)圖片的內(nèi)容和其他圖片是否完全相同，如果內(nèi)容相同那么這兩張圖片肯定是完全相同的。這種方法看起來(lái)是比較完美的，讓我們來(lái)分析一下他的時(shí)空效率：首先每張圖片的內(nèi)容都要和其他圖片進(jìn)行比較，這就是一個(gè)二重循環(huán)，讀取的效率低，比較的效率更低，所有的都比較下來(lái)是非常費(fèi)時(shí)的！內(nèi)存方面，如果預(yù)先把所有圖片讀取到內(nèi)存可以加快文件的比較效率，但是普通計(jì)算機(jī)的內(nèi)存資源有限，如果圖片非常多，好幾個(gè)G的話，都讀到內(nèi)存是不現(xiàn)實(shí)的。如果不把所有的文件讀取到內(nèi)存，那么每比較一次之前就要先讀取文件內(nèi)容，比較幾次就要讀取幾次，從硬盤(pán)讀取數(shù)據(jù)是比較慢的，這樣做顯然不合適。那么有沒(méi)有更好的方法呢？我冥思苦想，絞盡腦汁，最后想到了md5。md5是什么？你不知道嗎？額，你火星了，抓緊時(shí)間duckduckgo吧！也許你會(huì)問(wèn)，md5不是加密的嗎？和我們的問(wèn)題有關(guān)系嗎？問(wèn)得好！md5可以把任意長(zhǎng)度的字符串進(jìn)行加密后形成一個(gè)32的字符序列，包括數(shù)字和字母（大寫(xiě)或小寫(xiě)），因?yàn)樽址魏挝⑿〉淖儎?dòng)都會(huì)導(dǎo)致md5序列改變，因此md5可以看作一個(gè)字符串的‘指紋'或者‘信息摘要'，因?yàn)閙d5字符串總共有3632個(gè)，所以兩個(gè)不同的字符串得到一個(gè)相同的md5概率是很小的，幾乎為0，同樣的道理，我們可以得到每個(gè)文件的md5，若干文件的md5相同的話就基本上可以肯定兩個(gè)文件是相同的，因?yàn)閙d5相同而文件不同的概率太小了，基本可以忽略，這樣我們就可以這樣做：得到每個(gè)文件的md5，通過(guò)比較md5是否相同我們就可以確定兩張圖片是否相同。下面是代碼實(shí)現(xiàn)，python的

復(fù)制代碼代碼如下:

 
# -*- coding: cp936 -*- 
import md5 
import os 
from time import clock as now 
def getmd5(filename): 
file_txt = open(filename,'rb').read() 
m = md5.new(file_txt) 
return m.hexdigest() 
def main(): 
path = raw_input("path: ") 
all_md5=[] 
total_file=0 
total_delete=0 
start=now() 
for file in os.listdir(path): 
total_file += 1; 
real_path=os.path.join(path,file) 
if os.path.isfile(real_path) == True: 
filemd5=getmd5(real_path) 
if filemd5 in all_md5: 
total_delete += 1 
print '刪除',file 
else: 
all_md5.append(filemd5) 
end = now() 
time_last = end - start 
print '文件總數(shù)：',total_file 
print '刪除個(gè)數(shù)：',total_delete 
print '耗時(shí)：',time_last,'秒' 
if __name__=='__main__': 
main() 

上面的程序原理很簡(jiǎn)單，就是依次讀取每個(gè)文件，計(jì)算md5，如果md5在md5列表不存在，就把這個(gè)md5加到md5列表里面去，如果存在的話，我們就認(rèn)為這個(gè)md5對(duì)應(yīng)的文件已經(jīng)出現(xiàn)過(guò)，這個(gè)圖片就是多余的，然后我們就可以把這個(gè)圖片刪除了。下面是程序的運(yùn)行截圖：

我們可以看到，在這個(gè)文件夾下面有8674個(gè)文件，有31個(gè)是重復(fù)的，找到所有重復(fù)文件共耗時(shí)155.5秒。效率不算高，能不能進(jìn)行優(yōu)化呢？我分析了一下，我的程序里面有兩個(gè)功能比較耗時(shí)間，一個(gè)是計(jì)算每個(gè)文件的md5，這個(gè)占了大部分時(shí)間，還有就是在列表中查找md5是否存在，也比較費(fèi)時(shí)間的。從這兩方面入手，我們可以進(jìn)一步優(yōu)化。

首先我想的是解決查找問(wèn)題，或許我們可以對(duì)列表中的元素先排一下序，然后再去查找，但是列表是變化的，每次都排序的話效率就比較低了。我想的是利用字典進(jìn)行優(yōu)化。字典最顯著的特點(diǎn)是一個(gè)key對(duì)應(yīng)一個(gè)值我們可以把md5作為key，key對(duì)應(yīng)的值就不需要了，在變化的情況下字典的查找效率比序列效率高，因?yàn)樾蛄惺菬o(wú)序的，而字典是有序的，查找起來(lái)當(dāng)然更快。這樣我們只要判斷md5值是否在所有的key中就可以了。下面是改進(jìn)后的代碼：

復(fù)制代碼代碼如下:

 
# -*- coding: cp936 -*- 
import md5 
import os 
from time import clock as now 
def getmd5(filename): 
file_txt = open(filename,'rb').read() 
m = md5.new(file_txt) 
return m.hexdigest() 
def main(): 
path = raw_input("path: ") 
all_md5={} 
total_file=0 
total_delete=0 
start=now() 
for file in os.listdir(path): 
total_file += 1; 
real_path=os.path.join(path,file) 
if os.path.isfile(real_path) == True: 
filemd5=getmd5(real_path) 
if filemd5 in all_md5.keys(): 
total_delete += 1 
print '刪除',file 
else: 
all_md5[filemd5]='' 
end = now() 
time_last = end - start 
print '文件總數(shù)：',total_file 
print '刪除個(gè)數(shù)：',total_delete 
print '耗時(shí)：',time_last,'秒' 

if __name__=='__main__': 
main() 

從時(shí)間上看，確實(shí)比原來(lái)快了一點(diǎn)，但是還不理想。下面還要進(jìn)行優(yōu)化。還有什么可以優(yōu)化呢？md5！上面的程序，每個(gè)文件都要計(jì)算md5，非常費(fèi)時(shí)間，是不是每個(gè)文件都需要計(jì)算md5呢？能不能想辦法減少md5的計(jì)算次數(shù)呢？我想到了一種方法：上面分析時(shí)我們提到，可以通過(guò)比較文件大小的方式來(lái)判斷圖片是否完全相同，速度快，但是這種方法是不準(zhǔn)確的，md5是準(zhǔn)確的，我們能不能把兩者結(jié)合一下？答案是肯定的。我們可以認(rèn)定：如果兩個(gè)文件完全相同，那么這兩個(gè)文件的大小和md5一定相同，如果兩個(gè)文件的大小不同，那么這兩個(gè)文件肯定不同！這樣的話，我們只需要先查看文件的大小是否存在在size字典中，如果不存在，就將它加入到size字典中，如果大小存在的話，這說(shuō)明有至少兩張圖片大小相同，那么我們只要計(jì)算文件大小相同的文件的md5，如果md5相同，那么這兩個(gè)文件肯定完全一樣，我們可以刪除，如果md5不同，我們把它加到列表里面，避免重復(fù)計(jì)算md5.具體代碼實(shí)現(xiàn)如下：

復(fù)制代碼代碼如下:

 
# -*- coding: cp936 -*- 
import md5 
import os 
from time import clock as now 
def getmd5(filename): 
file_txt = open(filename,'rb').read() 
m = md5.new(file_txt) 
return m.hexdigest() 
def main(): 
path = raw_input("path: ") 
all_md5 = {} 
all_size = {} 
total_file=0 
total_delete=0 
start=now() 
for file in os.listdir(path): 
total_file += 1 
real_path=os.path.join(path,file) 
if os.path.isfile(real_path) == True: 
size = os.stat(real_path).st_size 
name_and_md5=[real_path,''] 
if size in all_size.keys(): 
new_md5 = getmd5(real_path) 
if all_size[size][1]=='': 
all_size[size][1]=getmd5(all_size[size][0]) 
if new_md5 in all_size[size]: 
print '刪除',file 
total_delete += 1 
else: 
all_size[size].append(new_md5) 
else: 
all_size[size]=name_and_md5 
end = now() 
time_last = end - start 
print '文件總數(shù)：',total_file 
print '刪除個(gè)數(shù)：',total_delete 
print '耗時(shí)：',time_last,'秒' 

if __name__=='__main__': 
main() 

時(shí)間效率怎樣呢？看下圖：

只用了7.28秒！比前兩個(gè)效率提高了十幾倍！這個(gè)時(shí)間還可以接受

算法是個(gè)很神奇的東西，不經(jīng)意間用一下會(huì)有意想不到的收獲！上面的代碼還可以進(jìn)一步優(yōu)化，比如改進(jìn)查找算法等，讀者有啥想法可以和我交流一下。換成C語(yǔ)言來(lái)實(shí)現(xiàn)可能會(huì)更快。呵呵，我喜歡python的簡(jiǎn)潔！
博主ma6174

您可能感興趣的文章: