测试file1中的行是否是file2中的行的子集

我试过在线搜索答案，但不幸的是没有成功。因此，我在这里问：测试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.

编辑：我刚刚添加了我的代码的工作版本，为他人带来好处。没有内存错误，但非常慢。

来源

2017-08-25 Ali

Ick，你的代码是'O（m * n）'。在'O（m log m + n log n）'中做这件事是微不足道的，有时候在'O（m + n）'中有可能。 – o11c

你对Algo复杂性的评论等于我的头上。 – Ali

然后在你学习*任何其他*关于编程，学习算法复杂性和大O符号。这个很重要*。 – o11c

我不知道为什么它不工作，但我想我知道一种方法，你如何能够解决它：

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行。这应该是非常有利于记忆的。

另一种方法（可能更快）将是对file1和file2进行排序。这样，如果字符串在词汇上小于第一个文件中的字符串，则可以逐行比较并移至其他文件中的下一行。可以在O(n*log(n))中执行的O(n**2)而不是O(n**2)。然而，这更复杂，我不知道排序GB文件是否合理（可能会使用太多的内存！）。

来源

2017-08-25 16:48:39 MSeifert

对不起，我忘了提及mmap.find（）不会给我一个内存问题。它只是没有正确做匹配。 – Ali

啊，我的代码工作正常吗？ – MSeifert

MSeifert，是你的代码工作。我给了你一个投票，但它没有注册，因为我的声望不到15。但是，你的代码比上面发布的mmap解决方案慢得多。我基本上从字符串中缺少一个strip（），这就是为什么它没有进行匹配。非常感谢:) – Ali

处理不适合内存的文件总是很难。

如果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排序）的文件中的至少一个。

来源

2017-08-25 17:05:42 o11c

测试file1中的行是否是file2中的行的子集

回答

相关问题