2017-08-25 142 views
1

我試過在線搜索答案,但不幸的是沒有成功。因此,我在這裏問:測試file1中的行是否是file2中的行的子集

我想弄清楚file1中的所有行是否存在file2。幸運的是,我可以比較整行而不是單個單詞等。不幸的是,我正在處理GB文件,因此我嘗試過的一些基本解決方案給我帶來了內存錯誤。

目前我有下面的代碼不起作用。一些指導將非常感謝。

# Checks if all lines in file1 are present in file2 
def isFile1SubsetOfFile2(file1 , file2): 
    file1 = open(file1, "r") 


    for line1 in file1:   
     with open(file2, "r+b") as f: 

      mm=mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ) 
      my_str_as_bytes = str.encode(line1) 
      result = mm.find(line1.strip().encode()) 
      print(result) 
      if result == -1: 
       return False 
    return True 

樣品file2的:

This is line1. 
This is line2. 
This is line3. 
This is line4. 
This is line5. 
This is line6. 
This is line7. 
This is line8. 
This is line9. 

應該通過例如如果file1是:

This is line4. 
This is line5. 

例如, file1是:

This is line4. 
This is line10. 

編輯:我剛剛添加了我的代碼的工作版本,爲他人帶來好處。沒有內存錯誤,但非常慢。

+0

Ick,你的代碼是'O(m * n)'。在'O(m log m + n log n)'中做這件事是微不足道的,有時候在'O(m + n)'中有可能。 – o11c

+0

你對Algo複雜性的評論等於我的頭上。 – Ali

+0

然後在你學習*任何其他*關於編程,學習算法複雜性和大O符號。這個很重要*。 – o11c

回答

0

我不知道爲什麼它不工作,但我想我知道一種方法,你如何能夠解決它:

def is_subset_of(file1, file2): 
    with open(file1, 'r') as f1, open(file2, 'r') as f2: 
     for line in f1: 
      line = line.strip() 
      f2.seek(0) # go to the start of f2 
      if line not in (line2.strip() for line2 in f2): 
       return False 
    return True 

這樣就避免了一直在尋找到開始再次多次打開第二個文件對於每一行,在任何時候你只能在內存中保存2行。這應該是非常有利於記憶的。

另一種方法(可能更快)將是對file1file2進行排序。這樣,如果字符串在詞彙上小於第一個文件中的字符串,則可以逐行比較並移至其他文件中的下一行。可以在O(n*log(n))中執行的O(n**2)而不是O(n**2)。然而,這更復雜,我不知道排序GB文件是否合理(可能會使用太多的內存!)。

+0

對不起,我忘了提及mmap.find()不會給我一個內存問題。它只是沒有正確做匹配。 – Ali

+0

啊,我的代碼工作正常嗎? – MSeifert

+0

MSeifert,是你的代碼工作。我給了你一個投票,但它沒有註冊,因爲我的聲望不到15。但是,你的代碼比上面發佈的mmap解決方案慢得多。我基本上從字符串中缺少一個strip(),這就是爲什麼它沒有進行匹配。非常感謝:) – Ali

0

處理不適合內存的文件總是很難。

如果file1適合在內存中,但file2太大,這裏是一個解決方案:

# file1 and file2 are open file-like objects 
unseen = set(file1) 
for line in file2: 
    unseen -= {line} # avoid exception from set.remove 
#if unseen is empty, all lines were found in file2 

否則,你應該進行排序(或者CFBS排序)的文件中的至少一個。

相關問題