我有这段代码，它工作得很好，可以做我想做的，但是它以线性形式执行，这对于我的数据文件的大小来说是减慢的，所以我想把它转换为日志。我尝试了这段代码和许多其他发布在这里的代码，但仍然没有运气让它工作。我将发布这两组代码，并举例说明我的期望。
import pandas
import fileinput
'''This code runs fine and does what I expect removing duplicates from big
file that are in small file, however it is a linear function.'''
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('')
'''This code is my attempt at conversion to a log function.'''
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)
- 大文件有数百万行的 int 数据。
- 小文件包含数百行 int 数据。
- 比较数据并删除大文件中的重复数据，但将行号留空。
运行第一个代码块可以工作，但搜索大文件需要很长时间。也许我以错误的方式处理问题。我尝试将其转换为日志运行没有错误，但什么也没做。
我认为没有比您目前在第一种方法中所做的更好或更快的方法来做到这一点。(更新：有，见下文。将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 秒。因此，恕我直言，这并不值得付出努力，但当然这可能取决于您必须执行此操作的频率。
好吧，所以我自己也很好奇 - 反正谁需要午休?--所以我试图实现这个......而且效果出奇地好。这将在文件中找到给定的数字，并将其替换为相应的-号(不仅仅是一个空行，如果不重写整个文件是不可能的)。请注意，我没有彻底测试二进制搜索算法的边缘情况、逐个错误等。
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)
这将首先收集所有要覆盖的位置，然后在第二个 stes 中进行实际覆盖，否则二进制搜索在点击之前"删除"的行之一时会出现问题。我用一个文件测试了这一点，该文件按排序顺序保存从 0 到 1,000 的所有数字，并删除了要删除的随机数(界内和界外)列表，它工作得很好。
更新：还用一个随机数从 0 到 100,000,000 的文件按排序顺序 (944 MB) 并覆盖 100 个随机数对其进行了测试，它立即完成，所以这确实应该是 O(s*logb)，至少在我的系统上(file.seek的复杂性可能取决于文件系统、文件类型等)。
bsearch函数也可以推广为接受另一个参数value_function而不是硬编码val = int(line)。然后，它可以用于任意文件中的二进制搜索，例如庞大的字典，基因数据库，csv文件等，只要行按相同的值函数排序即可。