Учитывая файл L с одним неотрицательным целым числом в строке и текстовым файлом F, что будет быстрым способом сохранить только те строки в F, чей номер строки появляется в файле L?
Пример:
$ cat L.txt
1
3
$ cat F.txt
Hello World
Hallo Welt
Hola mundo
$ command-in-question -x L.txt F.txt
Hello World
Hola mundo
Я ищу команду, которая может обработать файл L с 500 миллионами или более записями; Файл L отсортирован по номерам.
Примечание: я на полпути к реализации для, command-in-question
но я просто задавался вопросом, можно ли здесь использовать некоторые инструменты Unix.
Обновление: Спасибо за все ответы, сегодня я многому научился! Я хотел бы принять еще один ответ, но это невозможно.
Ответы:
С
C
пропуском значимых сообщений об ошибках:источник
xsel -bo | cc -xc - -o cselect
. И это просто сработало - ему нужны только две библиотеки.LINE_MAX
свою версию, поэтому вы, вероятно, работаете с очень большими строками в ваших файлах. Я обновил А с помощью версии,getline()
чтобы убрать ограничение размера строки.LINE_MAX
, так что,getline
кажется, это правильно.Я хотел бы использовать
awk
, но не хранить весь контентL.txt
в памяти и делать ненужные хэш-поиски ;-).источник
n
, в противном случае (как есть) он пропускает1
вL.txt
command-in-question
сценарий, то вы не сможете вставить имя файла в код.-v list="$opt_x"
также не работает из-за обработки обратной косой черты, выполняемой с помощью awk. Вот почему я использую ENVIRON вместо этого здесь.grep -n | sort | sed | cut
Это должно работать довольно быстро (некоторые временные тесты включены ниже) с вводом любого размера. Некоторые заметки о том, как:
export LC_ALL=C
./F
встроенного./L
файла, встроенного вместе с файлом белья, единственными символами, которые нам действительно нужно беспокоиться, являются[0-9]
цифры ASCII и:
двоеточие.grep -n ''
LINENO:
в заголовок каждой строки в stdin - или<./F
.sort -t: -nmk1,1 ./L -
sort
пренебрегаешь сортировать свои входные файлы на всех, и вместо этого (правильно) предполагает , что они отсортированы и-m
erges их в-numerically
отсортированном порядке, игнорируя в принципе ничего , кроме любого возможного-k1,1
го происходящего-t:
двоеточия в любом случае.sort
будет выводить один поток, где любое бельё./L
будет сразу же предшествовать соответствующим строкам./F
../L
Линии всегда на первом месте, потому что они короче.sed /:/d\;n
/:/
двоеточию,d
исключите ее из выходных данных. Иначе, автоматически печатать текущую иn
внешнюю строку.sed
черносливsort
выход «ы к только последовательные пары строк , которые не соответствуют двоеточие и следующую строку - или, только линии ,./L
а затем следующий.cut -sd: -f2-
cut
-s
подавляет из вывода те его входные строки, которые не содержат по крайней мере одну из его-d:
строк-элимитеров - и поэтому./L
строки полностью удаляются .:
разделенный двоеточиями-f
ield отсутствуетcut
- и то же самое относится ко всемgrep
вставленным бельям.небольшой входной тест
... генерирует 5 строк ввода образца. Потом...
... печать ...
большие тесты по времени
Я создал пару довольно больших файлов:
... которые помещают 5 миллионов строк
/tmp/F
и 1,5 миллиона случайно выбранных строк в/tmp/L
. Я тогда сделал:Это напечатано:
(Я добавил туда обратную косую черту)
Среди решений, предлагаемых в настоящее время, это самое быстрое из всех, но одно, если оно сопоставлено с набором данных, сгенерированным выше на моей машине. Из остальных только один был близок к тому, чтобы бороться за второе место, и это мое дело
perl
здесь .Это ни в коем случае не оригинальное предлагаемое решение - оно сократило треть своего времени выполнения благодаря советам / вдохновению, предлагаемым другими. Смотрите историю сообщений для более медленных решений (но почему?) .
Кроме того, стоит отметить, что некоторые другие ответы вполне могли бы бороться лучше, если бы не архитектура с несколькими процессорами моей системы и одновременное выполнение каждого из процессов в этом конвейере. Все они работают одновременно - каждое на собственном процессорном ядре - обмениваясь данными и выполняя свою небольшую часть целого. Это довольно круто.
но самое быстрое решение ...
Но это не самое быстрое решение. Самое быстрое решение, предлагаемое здесь, это программа на Си . Я назвал это
cselect
. После копирования его в буфер обмена X я скомпилировал его так:Я тогда сделал:
... и результаты были ...
источник
sed -ne'/:/!{n;p;}' | cut -d: -f2-
вместоsed -ne'/:/!N;/\n/s/[^:]*://p'
sed
s -sed
я использую семейную реликвиюsed
- вы можете увидетьalias
значение вtime
результатах. Кстати, мой семейный пакет статически скомпилирован с библиотекой musl - реализация regex, для которой основан TRE . Когда я переключаю его на GNUsed
- и запускаю его безcut
- он добавляет целую секунду ко времени завершения (2,8 секунды) - составляет более трети. И это всего на 0,3 секунды быстрее, чем у вас в моей системе.sort -mn
в отличие отsort -nmk1,1
может быть лучше, поскольку вам не нужно делать расщепление здесь (не проверено)-n
is spec'd просто сделать первую числовую строку в строке, поэтому я решил, хорошо-mn
или-nm
и, по какой-то причине, единственный раз, когда она опускалась ниже 2 секунд во время завершения, это когда я добавлял все параметры как есть. Это странно - и это причина, по которой я вчера не взялся за-m
дело - я знал, о чем я, но казалось, что это просто что-то вроде автооптимизации. Интересно, что у семейной реликвииsort
есть-z
опция длины строки, которая применяется только к-[cm]
....-n
не первая числовая строка в строке . Она просто рассматривает строку как число, поэтому онаabc 123
будет равна 0. Поэтому она не может быть менее эффективной, чем с-t: -k1,1
Я бы использовал
awk
:Обновление: я сделал измерения производительности; кажется, что эта версия масштабируется еще лучше с очень большими наборами данных (как в случае с заявленными требованиями), поскольку сравнение выполняется очень быстро и компенсирует усилия, необходимые для создания хэш-таблицы.
источник
awk
могут справиться с такими огромными наборами данных. - Я использую GNUawk
и проблем нет; тест с 500 миллионами строк данных занял 7 минут.real 16m3.468s
-user 15m48.447s
-sys 0m10.725s
. Он использовал 3,3 ГБ ОЗУ для тестирования 1/10 размераL
с 50 000 000 строк; иF
с 500 000 000 строк - по сравнению с временем для awk anser Стефана Шазеласа:real 2m11.637s
-user 2m2.748s
-sys 0m6.424s
- Я не использую быстрый ящик, но сравнение интересно.seq
выход , а затем меньше, случайным образом выбирается подмножество же в L .Просто для полноты: мы можем объединить отличный сценарий awk в ответе Стефана Шазеласа и сценарий perl в ответе kos, но без сохранения всего списка в памяти, в надежде, что perl может быть быстрее, чем awk. (Я изменил порядок аргументов в соответствии с исходным вопросом).
источник
awk
. Это примерно так же быстро, как у меня - я тестировал оба три раза прямо сейчас, и каждый раз мой обрабатывал мой 5-миллионный тестовый набор линии за 1,8 ... секунды, а ваши 1,9 ... секунды каждый раз. Код testset gen находится в моем ответе, если вам интересно, но дело в том, что он очень хорош. Более того, результат правильный - я все еще не могу сделатьawk
работу ... Тем не менее, оба наших ответа опозорены FloHimself .awk
s. В вашем примере я получаю 1,4 с gawk (4 с для Janis '), 0,9 с mawk, 1,7 с с помощью этого Perl-решения, 2,3 с с KOS', 4,5 с с вашим (GNU sed) и 1,4 с с вашим ( GNU sed) и мое предложенное улучшение (и 0,5 с для решения C).Я написал простой Perl-скрипт для этого:
Usage: script.pl inputfile_f inputfile_f
F.txt
L.txt
L.txt
в массивF.txt
строку за строкой, отслеживая ее текущий номер строки и текущий индекс массива; увеличиваетF.txt
текущий номер строки; еслиF.txt
текущий номер строки соответствует содержимому массива по текущему индексу массива, он печатает текущую строку и увеличивает индексСтоимость и сложность соображений :
Учитывая стоимость выполнения назначений, стоимость сравнений и стоимость печати строк, учитывая N 1 как количество строк в
F.txt
и N 2 как количество строкL.txt
,while
цикл выполняется не более N 1 раз, ведение к 2N 1 + N 2 назначениям (очевидно, предполагая N 1 > N 2 ), к 2N 1 сравнениям и к N 2 отпечаткам; При условии равной стоимости каждой операции общая стоимость выполненияwhile
цикла составляет 4N 1 + 2N 2 , что приводит к усложнению сценария O (N).Тест на входной файл 10 миллионов строк :
Используя
F.txt
файл из 10 миллионов строк, содержащий случайные строки длиной 50 символов, иL.txt
файл из 10 миллионов строк, содержащий числа от 1 до 10000000 (в худшем случае):источник
Это решение на Perl быстрее, чем другие решения на awk или perl, примерно на 20%, но, очевидно, не так быстро, как решение на C.
источник
Поскольку L.txt отсортирован, вы можете использовать join. Просто пронумеруйте каждую строку в F.txt, объедините два файла, затем удалите номер строки. Никаких больших промежуточных файлов не требуется.
На самом деле, вышеизложенное будет искажать ваши строки данных, заменяя все пробелы одним пробелом. Чтобы сохранить строку нетронутой, вам нужно выбрать в качестве разделителя символ, который не отображается в ваших данных, например, «|». Cmd тогда
Первый sed удаляет начальные пробелы из вывода "cat -n" и заменяет вкладку. Второй sed удаляет номер строки и «|».
источник
join L.txt <(nl F.txt )
но она не будет работать с большими файлами. Добро пожаловать на сайт, кстати, не часто мы получаем такие четкие и хорошо отформатированные ответы от новых пользователей!join
/comm
не может работать с численно отсортированным вводом.join -t' ' <(<L.txt awk '{printf("%010s\n",$0)}') <(<F.txt awk '{printf("%010s %s\n",NR,$0)}') | cut -d' ' -f2-
- это было медленно! - и даже когда я подавал подготовленные файлы с подходящими 0-клавишными клавишамиjoin -t' ' L.txt F.txt | cut -d' ' -f2-
, он все еще был медленным (не считая времени на подготовку) - медленнее, чемawk
ответ @Janis (где я разместил комментарий относительно фактического времени, взятого для обоих его и @ StéphaneChazelas 'ответjoin
+ было против Стефана Шазеласа с использованием 50 миллионов строк, 500 миллионов строк.awk printf
real 20m11.663s user 19m35.093s sys 0m10.513s
real 2m11.637s user 2m2.748s sys 0m6.424s
L
F
Для полноты еще одна попытка
join
решения:Это работает путем форматирования столбца с номером строки, который соединяется, работает как фиксированная длина с ведущими нулями, так что числа всегда имеют длину 15 цифр. Это позволяет обойти проблему неприсоединения в обычном порядке числовой сортировки, поскольку столбец теперь фактически вынужден выполнять словарную сортировку.
nl
используется для добавления номеров строк в этом формате в F.txt. К сожалению,sed
необходимо использовать для переформатирования нумерации в L.txt.Этот подход, кажется, работает нормально на тестовых данных, сгенерированных с использованием метода @ mikeserv. Но это все еще очень медленно - решение c в 60 раз быстрее на моей машине. около 2/3 времени тратится на
sed
и 1/3 вjoin
. Возможно, есть лучшее выражение sed ...источник
nl
это очень круто, но вы не можете надежно использовать его на непроверенных данных. Одна из вещей, которая делает его таким крутым, это его логический-d
разделитель страниц . По умолчанию, если на входе есть какая-либо строка, состоящая только из строк:\`
(но без завершающей могилы) 1, 2, 3 или три раза подряд, ваш счет будет немного сумасшедшим. Эксперимент с этим - это довольно опрятно. Особенно взгляните на то, что происходит, когда nl` читает строку с 1 строкой-разделителем, а затем еще раз с w / 3 или 2Так как принятый ответ находится на C, я решил, что можно добавить решение Python здесь:
При использовании внешней библиотеки, такой как numpy, решение выглядело бы еще более элегантно:
источник