改进从文件中删除重复行的过程，从线性复杂度变为对数复杂度

Question

我有这个代码，它工作得很好，可以做我想要的事情，但是它以线性形式完成，这对于我的数据文件的大小来说太慢了，所以我想将其转换为日志：

import pandas
import fileinput

with open('small.txt') as fin:
    exclude = set(line.rstrip() for line in fin)
    for line in fileinput.input('big.txt', inplace=True):
        if line.rstrip() not in exclude:
            print(line, end='')
        else:
            print('')

这段代码是我尝试转换为日志函数：

def log_search(small, big):
    first = 0
    last = len(big.txt) - 1
    while first <= last:
        mid = (first + last) / 2
        if str(mid) == small.txt:
            return True
        elif small.txt < str(mid):
            last = mid - 1
        else:
            first = mid + 1
    with open('small.txt') as fin:
        exclude = set(line.rstrip() for line in fin)
        for line in fileinput.input('big.txt', inplace=True):
            if line.rstrip() not in exclude:
                print(line, end='')
            else:
                print('')
            return log_search(small, big)   

1. 大文件有数百万行int数据。
2. 小文件有数百行int数据。
3. 比较数据并删除大文件中的重复数据，但将行号留空。

运行第一段代码可以工作，但搜索大文件需要很长时间。也许我正在以错误的方式处理这个问题。我尝试将其转换为日志，运行时没有错误，但什么也没做。

Answer 1

我认为没有比您目前在第一种方法中所做的更好或更快的方法了。 （更新：有，见下文。）将

small.txt

中的行存储在

set

中，并迭代

big.txt

中的行，检查它们是否在该集合中，将具有

O(b)

的复杂性，其中

b 

是

big.txt

中的行数。

您似乎正在尝试将其减少为

O(s*logb)

，其中

s

是

small.txt

中的行数，通过使用二分搜索来检查

small.txt

中的每一行是否在

big.txt

中然后删除/覆盖它。

如果所有行都在

list

中并且可以随机访问任何数组，那么这会很有效，但是您只有文件，它不允许随机访问任何行。然而，它确实允许随机访问具有

file.seek

的任何字符，这（至少在某些情况下？）似乎是O(1)。但是，在实际读取该行之前，您仍然必须找到该位置的上一个换行符。另外，您不能只用空行替换行，而是必须用相同数量的字符覆盖数字，例如空格。

所以，是的，理论上可以在

O(s*logb)

中完成，如果你执行以下操作：

• 实现二分查找，不是按行查找，而是按大文件的字符查找
  • 对于每个位置，回溯到最后一个换行符，然后读取该行以获取数字
  • 像往常一样使用二分搜索在下/上半部分再次尝试
• 如果找到该号码，请替换为与号码中的数字一样多的空格
• 重复小文件中的下一个数字

在我的系统上，读取和写入包含 1000 万行数字的文件每个只需要 3 秒，或者使用

fileinput.input

和

print

大约需要 8 秒。因此，恕我直言，这并不值得付出努力，但这当然可能取决于您执行此操作的频率。

---

好吧，所以我自己很好奇——谁需要午休？——所以我尝试实现这个......并且效果出奇的好。这将在文件中找到给定的数字，并将其替换为相应的

-

数字（not 只是一个空行，如果不重写整个文件，这是不可能的）。请注意，我没有彻底测试二分搜索算法的边缘情况、差一错误等。

import os

def getlineat(f, pos):
    pos = f.seek(pos)
    while pos > 0 and f.read(1) != "\n":
        pos = f.seek(pos-1)
    return pos+1 if pos > 0 else 0

def bsearch(f, num):
    lower = 0
    upper = os.stat(f.name).st_size - 1
    while lower <= upper:
        mid = (lower + upper) // 2
        pos = getlineat(f, mid)
        line = f.readline()
        if not line: break # end of file
        val = int(line)
        if val == num:
            return (pos, len(line.strip()))
        elif num < val:
            upper = mid - 1
        elif num > val:
            lower = mid + 1 
    return (-1, -1)

def overwrite(filename, to_remove):
    with open(filename, "r+") as f:
        positions = [bsearch(f, n) for n in to_remove]
        for n, (pos, length) in sorted(zip(to_remove, positions)):
            print(n, pos)
            if pos != -1:
                f.seek(pos)
                f.write("-" * length)

import random
to_remove = [random.randint(-500, 1500) for _ in range(10)]
overwrite("test.txt", to_remove)

这将首先收集所有要覆盖的位置，然后在第二步中进行实际的覆盖，否则当二分查找命中之前“删除”的行之一时，就会出现问题。我用一个按排序顺序保存从 0 到 1,000 的所有数字的文件和要删除的随机数（包括界内和界外）列表进行了测试，效果很好。

更新：还用一个按排序顺序从 0 到 100,000,000 的随机数的文件（944 MB）测试了它并覆盖 100 个随机数，它立即完成，所以这确实应该是 O(s*logb)，至少在我的系统（

file.seek

的复杂性可能取决于文件系统、文件类型等）。

bsearch

函数也可以推广为接受另一个参数

value_function

，而不是硬编码

val = int(line)

。然后它可以用于任意文件中的二进制搜索，例如巨大的字典、基因数据库、csv 文件等，只要行按相同的值函数排序即可。