Предложения по обработке большого файла - python или командная строка?

Question

Имеются два файла, один из которых содержит записи вида:

label1 label2 name1
label1 label3 name2

и другой формы:

label1 label2 name1 0.1 1000
label9 label6 name7 0.8 0.5

Предположим, что вы хотите извлечь те строки из файла два, для которых первые три элемента появляются в строке (порядок важен) в файле один - какие-либо предложения о том, как это может быть быстро купировано?

Выходной файл из любого такого сценария с учетом приведенных выше примеров данных будет:

label1 label2 name1 0.1 1000

Я играл с питоном:

inp = open(file1.txt, 'r')
look_up = [i.split() for i in inp.readlines()]
inp.close()

inp = open('file2', 'wt')

holder = []

line = inp.readline()
while line:
    line = line.split()
    if [line[0], line[1], line[2]] in look_up:
        holder.append(line)
    line = inp.readline()

Однако, похоже, это займет некоторое время. Эти файлы довольно большие.

Спасибо!

Answer 1

Ваша версия на python довольно неэффективна, потому что вы проверяете членство в списке, а не набор или требование (т. Е. Время поиска O (n) вместо O (1)).

Попробуйтевместо этого используйте set кортежей или set строк.Кортежи будут лучшим выбором, так как два файла могут быть разделены на разные разделители, но я не думаю, что вы увидите особенно большую разницу в производительности.tuple('something'.split()) относительно быстро по сравнению с тестированием на членство в очень длинном списке.

Кроме того, нет необходимости звонить inp.readlines().Другими словами, вы можете просто сделать

look_up = set(tuple(line.split()) for line in inp)

И вы должны увидеть значительное ускорение без необходимости изменять какие-либо другие части вашего кода, кроме tuple(line[:3]), а не [line[0], line[1], line[2]].

На самом деле, grep и bash довольно хороши для этого ... (не проверено, но оно должно работать.)

while read line
do
    grep "$line" "file2.txt"
done < "file1.txt"

Чтобы увидеть, какой из них быстрее, мы можем сгенерировать некоторые тестовые данные (~ 4500 клавиш в file1.txt и 1000000 строк в file2.txt) и тестирование простой версии Python того же самого (грубо ... строки будут напечатаны в другом порядке, чем версия grep.).

with open('file1.txt', 'r') as keyfile:
    lookup = set(tuple(line.split()) for line in keyfile)

with open('file2.txt', 'r') as datafile:
    for line in datafile:
        if tuple(line.split()[:3]) in lookup:
            print line,

Версия Python оказывается в ~ 70 раз быстрее:

jofer@cornbread:~/so> time sh so_temp149.sh > a

real    1m47.617s
user    0m51.199s
sys     0m54.391s

против

jofer@cornbread:~/so> time python so_temp149.py > b

real    0m1.631s
user    0m1.558s
sys     0m0.071s

Конечно, два примера подходят к проблемев совсем разными способами.Мы действительно сравниваем два алгоритма, а не две реализации.Например, если у нас есть только несколько ключевых строк в file1, решение bash / grep легко выигрывает.

(Есть ли в bash какой-то встроенный контейнер с поиском O (1) для членства?(Я думаю, что у bash 4 может быть хеш-таблица, но я ничего о ней не знаю ...) Было бы интересно попробовать реализовать алгоритм, аналогичный приведенному выше в Python, на примере python ...)

Answer 2

Решение для хакерских bash / sort / Perl:

$ cat > 1
label1 label2 name1
label1 label3 name2

$ cat > 2
label1 label2 name1 0.1 1000
label9 label6 name7 0.8 0.5

$ (cat 1; cat 2; ) | sort | perl -ne 'INIT{$pattern_re="(?:\\S+) (?:\\S+) (?:\\S+)"; $current_pattern="";} if(/^($pattern_re)$/o){$current_pattern=$1} else {if(/^($pattern_re)/o) { print if $1 eq $current_pattern} }'
label1 label2 name1 0.1 1000

Объединяет оба файла в один список, сортирует его (поэтому мы получаем куски данных с одинаковым ключом, ведущими строку из файла 1),затем используйте специальный Perl oneliner, чтобы оставить из файла 1 только правильно сформированные строки с предшествующим «заголовком».

Answer 3

Я бы использовал хеш для хранения значения из первого файла. Не то чтобы устойчивость к ошибкам (1 и только 1 пробел между каждым элементом), но вы получите общее представление ...

#!/usr/bin/env python

labels={}
with open('log') as fd:
    for line in fd:
        line=line.strip()
        labels[line]=True

with open('log2') as fd:
    for line in fd:
        if " ".join(line.split()[0:3]) in labels:
            print line

Answer 4

Вы можете попробовать использовать в качестве ключа строку «label1 label2 name1», а не триплет значений.