Фильтровать файл, когда столбец находится в белом списке

Question

Фильтровать файл, когда столбец находится в белом списке

671

Hugo Sereno Ferreira 2013-06-02 в 12:14

Предположим, у меня есть два файла, Файл A:

a,abcdef b,bcdefa c,cdefab a,defabc b,efabcd c,fabcde

И файл Б:

a b

Вывод, который я ищу:

a,abcdef b,bcdefa a,defabc b,efabcd

Итак, в основном я хочу выбрать строки из файла A, где первый столбец соответствует любому значению в файле B, используя стандартные команды unix. Этакий awk print $1,$2, но более эффективный.

Ожидаемое количество строк в файле A превышает 20 миллионов, а в файле B 1 миллион. Он должен работать в O (n), поэтому шаг содержит, вероятно, полагаться на хэш-таблицу.

2

Это то, что известно как база данных. Daniel R Hicks 10 лет назад 2

@DanielRHicks: Возможно, вы правы, но ОТО, я не вижу необходимости, чтобы каждому посту на сайтах, связанных со стеком, предшествовало полное объяснение, почему у автора есть ограничения - какими бы абсурдными ни казались эти ограничения. Hugo Sereno Ferreira 10 лет назад 0

3 ответа на вопрос

3

2

cYrus 2013-06-02 в 14:29

This should do the trick:

join -t, <(sort A) <(sort B)

+1 за присоединение, хорошая идея. Я боюсь, что это будет очень медленно, так как он должен сначала отсортировать оба файла. terdon 10 лет назад 0

Сортировка файла с 20 миллионами строк занимает около 30 секунд на моей машине. cYrus 10 лет назад 0

Посмотрите мой обновленный ответ, объединение и сортировка занимает около 8 минут в моих тестовых файлах, по сравнению с 40 секундами для Perl. Да, каждая `сортировка 'займет около полминуты, но это добавляет как минимум минуту к времени выполнения. Кроме того, почему вы сортируете численно? Это на самом деле добавляет несколько секунд времени выполнения. terdon 10 лет назад 0

Аааа, да, потому что я тестировал с числами ... cYrus 10 лет назад 0

0

n13 2013-06-02 в 14:13

i still dont understand what you are trying to do .... you already have something up in a awk stmt.

grep is basic and is based on a preety efficient and fast algorithm based on index of possible matches .... awk does individual comparison and checks so this should be fast .... wrt awk, here

 for pat in `cat zfile2` ; do grep -i "$pat," zfile1 ; done;

this works fine ...

 $ for pat in `cat zfile2` ; do grep -i "$pat," zfile1 ; done; a,abcdef a,defabc b,bcdefa b,efabcd

does this help ?

Проблема с этим подходом состоит в том, что ему придется `grep` через файл A N раз для N строк в файле B. Это будет медленно ... terdon 10 лет назад 1

да, это в сумме составляет O (n2) ... он хочет что-то вроде O (n), может быть, O (nlogn) .... но что я не понял, так это то, что в наши дни утилиты довольно эффективны и Равномерно подобранный в большинстве сценариев ..... я сомневаюсь, что во время выполнения было бы много различий, если бы он использовал то, что у него уже есть в awk ..... Вы не можете быть уверены, если не проанализируете используемый алгоритм в коде n13 10 лет назад 0

хеш в Perl должен быть быстрым, хотя +1 для этого @terdon n13 10 лет назад 0

Также это вернет все строки, которые содержат шаблоны файла A, а не только те строки, которые _старт_ с шаблоном. terdon 10 лет назад 0

хе хе хххххххххххххххххххххх ... в выводе нет ничего подобного: c, fabcde n13 10 лет назад 0

Хм, прости, но это будет. Вы делаете поиск чувствительным к регистру (`-i`), что, вероятно, нежелательно и замедляет поиск, и вы не указываете, что шаблон должен быть в начале каждой строки. Попробуйте это `echo -e" abbb \ nbaaa "| grep a`, он вернет обе строки. Если бы я хотел быть педантичным, я мог бы также указать на бесполезное использование кошки, `пока читал погладь; do grep ...; done <fileA` будет лучше :). terdon 10 лет назад 0

Accepted Answer · 2013-06-02 14:13:10

There are many ways of doing this. Here are a few but use the Perl one it is orders of magnitude faster. I include the others for the sake of completeness:

Perl and hashes, ridiculously fast

perl -e 'open(A,"fileB"); while(<A>)++} while(<>){@a=split(/,/); print if defined $k{$a[0]}}' fileA

gawk and associative arrays, much slower
```
 gawk ' else}}' fileA fileB 
```
grep, ridiculously slow. You will need to modify your fileB slightly to make the patterns match only on the first line
```
sed 's/$.$/^\1/' fileB > fileC grep -f fileC fileA 
```

I created a couple of test files and it turns out that the Perl solutions is much faster than the grep:

$ head -2 fileA GO:0032513_GO:0050129 GO:0050129_GO:0051712 $ head -2 fileB GO:0032513_GO:0050129 GO:0050129_GO:0051712 $ wc -l fileA fileB 1500000 fileA 20000000 fileB $ time perl -e 'open(A,"fileB"); while(<A>)++} while(<>){@a=split(/,/); print if defined $k{$a[0]}}' fileA > /dev/null real 0m41.354s user 0m37.370s sys 0m3.960s $ time gawk ' else}}' fileA fileB real 2m30.963s user 1m23.857s sys 0m9.385s $ time (join -t, <(sort -n fileA) <(sort -n fileB) >/dev/null) real 8m29.532s user 13m52.576s sys 1m22.029s

So, the Perl scriptlet can go through a 20 million line file looking for 1.5 million patterns and finish in ~40 seconds. Not bad. The other two are much slower, gawk took 2.5 minutes and the grep one has been running for more than 15. Perl wins hands down.

Фильтровать файл, когда столбец находится в белом списке

3 ответа на вопрос

Похожие вопросы