У меня есть два файла, huge.txtи small.txt. huge.txtимеет около 600 миллионов строк и 14 ГБ. В каждой строке есть четыре слова (токены), разделенные пробелами, и, наконец, еще один столбец с цифрами, разделенный пробелами. small.txtимеет 150K строк размером ~ 3M, разделенное пробелами слово и число.
Оба файла отсортированы с помощью команды сортировки без дополнительных опций. Слова в обоих файлах могут включать апострофы (') и тире (-).
Желаемый вывод будет содержать все столбцы из huge.txtфайла и второй столбец (число), small.txtоткуда первое слово huge.txtи первое слово small.txtсовпадения.
Мои попытки ниже потерпели неудачу со следующей ошибкой:
cat huge.txt|join -o 1.1 1.2 1.3 1.4 2.2 - small.txt > output.txt join: memory exhausted Я подозреваю, что порядок сортировки как-то неправильный, даже если файлы предварительно отсортированы с использованием:
sort -k1 huge.unsorted.txt > huge.txt sort -k1 small.unsorted.txt > small.txt Проблемы, кажется, появляются вокруг слов, которые имеют апострофы (') или тире (-). Я также пробовал сортировку по словарю, используя -dопцию, наталкивающуюся на ту же ошибку в конце.
Я попытался загрузить файлы в MySQL, создать индексы и присоединиться к ним, но, похоже, на моем ноутбуке это занимает недели. (У меня нет компьютера с большим объемом памяти или быстрым диском / SSD для этой задачи)
Я вижу два выхода из этого, но не знаю, как реализовать любой из них.
Как отсортировать файлы так, чтобы команда соединения считала их правильно отсортированными?
Я думал о том, чтобы вычислить MD5 или некоторые другие хеши строк, чтобы избавиться от апострофов и тире, но оставить числа нетронутыми в конце строк. Выполняйте сортировку и объединение хешей вместо самих строк и, наконец, «переводите» хеши в строки. Поскольку хэшей будет всего 150K, это не так уж плохо. Что будет хорошим способом для вычисления отдельных хешей для каждой из строк? Немного волшебства AWK?
Смотрите образцы файлов в конце.
Образец огромный. Текст
had stirred me to 46 had stirred my corruption 57 had stirred old emotions 55 had stirred something in 69 had stirred something within 40 Образец small.txt
caley 114881 calf 2757974 calfed 137861 calfee 71143 calflora 154624 calfskin 148347 calgary 9416465 calgon's 94846 had 987654 Желаемый результат:
had stirred me to 46 987654 had stirred my corruption 57 987654 had stirred old emotions 55 987654 had stirred something in 69 987654 had stirred something within 40 987654 IMO лучший способ сделать это - использовать язык программирования / сценариев, который вы знаете лучше всего:
Основываясь на ответе Майкла Боргвардта: пока оба файла отсортированы, их можно объединить, выполнив один шаг сортировки. Это будет немного отличаться от стандартной сортировки слиянием, потому что вы хотите сохранить только один из файлов. Это, конечно, должно быть реализовано на вашем любимом языке программирования.
Вот эскиз алгоритма:
line1 = read a line from file 1 line2 = read a line from file 2 start of loop: if (first word of line1 == first word of line2) { write all fields of line1 and second field of line2 to output line1 = read a line from file 1 go to start of loop } else if (first word of line1 < first word of line2) { write line1 to output line1 = read a line from file 1 go to start of loop } else (first word of line1 > first word of line2) { line2 = read a line from file 2 go to start of loop } Вот версия Python (так как Python - это то, что я знаю лучше всего, не обязательно лучший язык для работы):
file1 = open('file1', 'r') file2 = open('file2', 'r') w2, n2 = file2.readline().split() for line1 in file1: w11, w12, w13, w14, n15 = line1.split() if w11 == w2: print w11, w12, w13, w14, n15, n2 continue elif w11 < w2: print w11, w12, w13, w14, n15 continue else: while w11 > w2: w2, n2 = file2.readline().split() if w11 == w2: print w11, w12, w13, w14, n15, n2 elif w11 < w2: print w11, w12, w13, w14, n15 и для полноты после некоторого копания вот что я придумал для Awk:
BEGIN { getline line2 <"file2"; split(line2, a); } { if (a[1] == $1) print $0,a[2]; else if (a[1] < $1) print $0; else { getline line2 <"file2"; split(line2, a); } } Вызывать как awk -f program.awk <file1.
Мой ответ похож на ответ Майкла Боргвардта, но вам не нужно загружать все файлы в память. Если оба файла отсортированы, вы просматриваете первый файл по одной строке за раз и выполняете бинарный поиск по второму файлу, чтобы найти целевую строку, о которой идет речь. Это много HD-доступа, но это низкое потребление памяти.
Хорошо, этот подход использует http://cr.yp.to/cdb.html как более быстрый способ поиска содержимого файла small.txt:
cdbmake(часть пакета 'freecdb' в Ubuntu, но существует множество реализаций).Используйте awk для передачи small.txt в cdbmake.
% awk ' { printf "+%d,%d:%s->%s\n", \ length($1),length($2),$1,$2 } \ END { print "" }' | cdbmake small.cdb small.cdbtmp (Это преобразует строку small.txt из чего-то вроде «значения ключа» в «+ ks, vs: key-> value».)
Теперь вы переходите строка за строкой над «принцпом» и распечатываете его, ища первое слово в «канале»:
#!/bin/python import cdb import fileinput c = cdb.init("small.cdb") for l in fileinput.input(['huge.txt']): print l.strip(), v = c.get(l.split()[0]) print "" if v == None else v Конечно, вам придется установить python-cdb, чтобы этот крошечный фрагмент работал (и он работает только для Python 2.5 из-за « условного выражения ». В любом случае, существует множество привязок для любого языка, который вам нравится. Вы также можете использовать cdbget(инструмент командной строки) и вызывать его снова и снова, но порождать новый процесс для миллионов строк немного неэффективно.
Во всяком случае, имейте это в виду:
Я знаю, что это невероятно просто, но это работает.
Исходя из предположения о том, что мои исходные файлы содержат только строчные буквы, я просто заменил проблемные апострофы и тире двумя заглавными буквами, пересортировав, а не присоединив файлы, и, наконец, вернул буквы обратно к знакам. Вот и все.
Еще раз спасибо за каждый вклад в ответ или проницательный комментарий.
Для огромного .txt (14Gig) сортировка заняла около 2 часов, соединение заняло менее часа.
cat small.txt | tr "\'-" "AD" | sort -k1 > small.AD cat huge.txt | tr "\'-" "AD" | sort -k1 | cat huge.txt | join -o 1.1 1.2 1.3 1.4 2.2 - small.AD | tr "AD" "\'-" > output.txt Вместо MySQL вы можете попробовать PostgreSQL, который, вероятно, справится с этой задачей более изящно. Смотрите их руководство по эффективному заполнению базы данных.