python - 한줄씩 - 파이썬에서 다른 파일에없는 한 파일의 모든 숫자 찾기




파이썬 파일 읽기 배열 (3)

FileA와 FileB라는 두 파일이 있으며 FileB에없는 FileA에있는 모든 숫자를 찾아야합니다. FileA의 모든 숫자가 정렬되고 FileB의 모든 숫자가 정렬됩니다. 예를 들어,

입력:

FileA = [1, 2, 3, 4, 5, ...]
FileB = [1, 3, 4, 6, ...]

산출:

[2, 5, ...]

메모리는 매우 제한되어 있으며 한 번에 전체 파일 한 개를 메모리에로드 할 수 없습니다. 또한 선형 또는 덜 복잡한 시간 복잡성이 필요합니다.

따라서 파일이 메모리에 충분히 작 으면 파일을로드하고 두 세트로 내용을 초기화 한 다음 O (1) 또는 일정 시간 복잡도에서 문제가 해결되도록 설정 차이를 가져올 수 있습니다.

set(contentsofFileA)-set(contentsofFileB)

그러나 파일이 너무 크기 때문에 메모리에 완전히로드 할 수 없으므로 불가능합니다.

또한, 또 다른 접근법은 일괄 처리와 무차별 방식을 사용하는 것입니다. 그래서 우리는 FileA에서 데이터 청크 또는 일괄 처리를로드 한 다음 FileB에서 일괄 처리를로드 한 다음 FileB의 다음 청크를 비교합니다. 그런 다음 FileA 청크가 FileB의 모든 요소를 ​​검사 한 후 FileA에서 다음 배치를로드하면이 작업이 계속됩니다. 그러나 이것은 O (n ^ 2) 또는 2 차 시간 복잡성을 생성하고 큰 항목이 포함 된 매우 큰 파일에는 효율적이지 않습니다.

선형 또는 시간 복잡성을 줄이고 전체 파일을 메모리에로드하지 않고도 문제를 해결해야합니다. 어떤 도움?


메모리가 많지 않고 선형 솔루션이 필요하기 때문에 파일을 줄 단위로 읽으려는 경우 파일이 줄 단위 인 경우 iter를 사용하여이 작업을 수행 할 수 있습니다. 그렇지 않으면 다음을 참조 this .

터미널에서 먼저 테스트 파일을 생성 할 수 있습니다.

seq 0 3 100 > 3k.txt
seq 0 2 100 > 2k.txt

그런 다음이 코드를 실행합니다.

i1 = iter(open("3k.txt"))
i2 = iter(open("2k.txt"))
a = int(next(i1))
b = int(next(i2))
aNotB = []
# bNotA = []
while True:
    try:
        if a < b:
            aNotB += [a]
            a = int(next(i1, None))
        elif a > b:
            # bNotA += [a]
            b = int(next(i2, None))
        elif a == b:
            a = int(next(i1, None))
            b = int(next(i2, None))
    except TypeError:
        if not b:
            aNotB += list(i1)
            break
        else:
            # bNotA += list(i1)
            break
print(res)

산출:

[3,9,15,21,27,33,39,45,51,57,63,69,75,81,87,93,99] aNotB와 bNotA에 대한 결과를 모두 원한다면 그 두 가지 주석 처리를 제거 할 수 있습니다 윤곽.

Andrej Kesely의 답변과 타이밍 비교 :

$ seq 0 3 1000000 > 3k.txt
$ seq 0 2 1000000 > 2k.txt
$ time python manual_iter.py        
python manual_iter.py  0.38s user 0.00s system 99% cpu 0.387 total
$ time python heapq_groupby.py        
python heapq_groupby.py  1.11s user 0.00s system 99% cpu 1.116 total

파일 읽기에 기반한 간단한 해결책 (각 줄에 번호가 있음) :

results = []
with open('file1.csv') as file1, open('file2.csv') as file2:
        var1 = file1.readline()
        var2 = file2.readline()
        while var1:
            while var1 and var2:
                if int(var1) < int(var2):
                    results.append(int(var1))
                    var1 = file1.readline()
                elif int(var1) > int(var2):
                    var2 = file2.readline()
                elif int(var1) == int(var2):
                    var1 = file1.readline()
                    var2 = file2.readline()
            if var1:
                results.append(int(var1))
                var1 = file1.readline()
print(results)
output = [2, 5, 7, 9]

itertools.groupby ( doc )와 heapq.merge ( doc )를 결합하여 FileAFileA 를 반복적으로 반복 할 수 있습니다 (파일이 정렬되는 한 오래 작동합니다).

FileA = [1, 1, 2, 3, 4, 5]
FileB = [1, 3, 4, 6]

from itertools import groupby
from heapq import merge

gen_a = ((v, 'FileA') for v in FileA)
gen_b = ((v, 'FileB') for v in FileB)

for v, g in groupby(merge(gen_a, gen_b, key=lambda k: int(k[0])), lambda k: int(k[0])):
    if any(v[1] == 'FileB' for v in g):
        continue
    print(v)

인쇄물:

2
5

편집 (파일에서 읽기) :

from itertools import groupby
from heapq import merge

gen_a = ((int(v.strip()), 1) for v in open('3k.txt'))
gen_b = ((int(v.strip()), 2) for v in open('2k.txt'))

for v, g in groupby(merge(gen_a, gen_b, key=lambda k: k[0]), lambda k: k[0]):
    if any(v[1] == 2 for v in g):
        continue
    print(v)

기준:

10_000_000 개 항목으로 파일 생성 :

seq 0 3 10000000 > 3k.txt
seq 0 2 10000000 > 2k.txt

스크립트를 완료하는 데 ~ 10 초가 소요됩니다.

real    0m10,656s
user    0m10,557s
sys 0m0,076s




out-of-memory