Как сравнить 2 очень большие матрицы с помощью Python - PullRequest
Новая
       74

Как сравнить 2 очень большие матрицы с помощью Python

1 голос
/ 21 сентября 2010

У меня интересная проблема.

У меня есть очень большой (более 300 МБ, более 10 000 000 строк / строк в файле) файл CSV с точками данных временных рядов внутри. Каждый месяц я получаю новый CSV-файл, который почти совпадает с предыдущим файлом, за исключением нескольких новых строк, которые были добавлены и / или удалены, и, возможно, несколько строк были изменены.

Я хочу использовать Python для сравнения двух файлов и определения, какие строки были добавлены, удалены и изменены.

Проблема в том, что файл очень большой, поэтому мне нужно решение, которое может обрабатывать файлы большого размера и эффективно выполнять их в течение разумного времени, чем быстрее, тем лучше.

Пример того, как может выглядеть файл и его новый файл:

Старый файл
A,2008-01-01,23
A,2008-02-01,45
B,2008-01-01,56
B,2008-02-01,60
C,2008-01-01,3
C,2008-02-01,7
C,2008-03-01,9
etc...

Новый файл
A,2008-01-01,23
A,2008-02-01,45
A,2008-03-01,67 (добавлено)
B,2008-01-01,56
B,2008-03-01,33 (удалено и добавлено)
C,2008-01-01,3
C,2008-02-01,7
C,2008-03-01,22 (изменено)
etc...

В основном 2 файла можно рассматривать как матрицы, которые нужно сравнивать, и я начал думать об использовании PyTable. Будем весьма благодарны за любые идеи о том, как решить эту проблему.

Ответы [ 2 ]

4 голосов
/ 21 сентября 2010

Вот так.

Шаг 1. Сортировка.

Шаг 2. Читайте каждый файл, проводя построчное сравнение. Запишите различия в другой файл.

Вы можете легко написать это сами. Или вы можете использовать difflib. http://docs.python.org/library/difflib.html

Обратите внимание, что общее решение довольно медленное, поскольку оно ищет совпадающие линии вблизи разницы. Написание собственного решения может выполняться быстрее, потому что вы знаете, как должны совпадать файлы. Вы можете оптимизировать этот алгоритм «resynch-after-a-diff».

И 10 000 000 строк вряд ли имеют значение. Это не так уж и много. Два файла размером 300 МБ легко помещаются в память.

1 голос
/ 21 сентября 2010

Это немного наивная реализация, но она будет работать с несортированными данными: 

import csv

file1_dict = {}
file2_dict = {}

with open('file1.csv') as handle:
    for row in csv.reader(handle):
        file1_dict[tuple(row[:2])] = row[2:]

with open('file2.csv') as handle:
    for row in csv.reader(handle):
        file2_dict[tuple(row[:2])] = row[2:]

with open('outfile.csv', 'w') as handle:
    writer = csv.writer(handle)
    for key, val in file1_dict.iteritems():
        if key in file2_dict:
            #deal with keys that are in both
            if file2_dict[key] == val:          
                writer.writerow(key+val+('Same',))
            else:
                writer.writerow(key+file2_dict[key]+('Modified',))
            file2_dict.pop(key)
        else:
            writer.writerow(key+val+('Removed',))
    #deal with added keys!  
    for key, val in file2_dict.iteritems():
        writer.writerow(key+val+('Added',))

Вы, вероятно, не сможете "вставить" это решение, но оно должно пройти вам ~ 95% пути. @ S.Lott прав: 2 300 МБ файлов легко уместятся в памяти ... если ваши файлы попадают в диапазон 1-2 ГБ, то это, возможно, придется изменить в предположении отсортированных данных.

Что-то вроде этого близко ... хотя вам, возможно, придется изменить сравнение для добавленного модифицированного, чтобы иметь смысл: 

#assumming both files are sorted by columns 1 and 2
import datetime
from itertools import imap

def str2date(in):
    return datetime.date(*map(int,in.split('-')))

def convert_tups(row):
    key = (row[0], str2date(row[1]))
    val = tuple(row[2:])
    return key, val

with open('file1.csv') as handle1:
    with open('file2.csv') as handle2:
        with open('outfile.csv', 'w') as outhandle:
            writer = csv.writer(outhandle)
            gen1 = imap(convert_tups, csv.reader(handle1))
            gen2 = imap(convert_tups, csv.reader(handle2))
            gen2key, gen2val = gen2.next()      
            for gen1key, gen1val in gen1:
                if gen1key == gen2key and gen1val == gen2val:
                    writer.writerow(gen1key+gen1val+('Same',))
                    gen2key, gen2val = gen2.next()
                elif gen1key == gen2key and gen1val != gen2val:
                    writer.writerow(gen2key+gen2val+('Modified',))
                    gen2key, gen2val = gen2.next()
                elif gen1key > gen2key:
                    while gen1key>gen2key:
                        writer.writerow(gen2key+gen2val+('Added',))
                        gen2key, gen2val = gen2.next()
                else:
                    writer.writerow(gen1key+gen1val+('Removed',))
...