Efficient grep using Python?

[sf]

Just started thinking about learning python.

Is there any place where I can get some free examples, especially for
following kind of problem ( it must be trivial for those using python)

I have files A, and B each containing say 100,000 lines (each line=one
string without any space)

I want to do

" A - (A intersection B) "

Essentially, want to do efficient grep, i..e from A remove those lines which
are also present in file B.

[sf]

The point is that when you have 100,000s of records, this grep becomes
really slow?

Any comments?

Thats why I looked for python :)

that would be

grep -vf B A

and it is a rare use of grep, indeed.
--
TZOTZIOY, I speak England very best.
"Be strict when sending and tolerant when receiving." (from RFC1958)
I really should keep that in mind when talking with people, actually...

[Christos TZOTZIOY Georgiou]

On Fri, 17 Dec 2004 12:21:08 +0000, rumours say that [e-mail] m
might have written:

[snip some damn lie aka "benchmark"]

[me]

(Yes, I cheated by adding the F (for no regular expressions) flag :)
Also you only have 1000 entries in B!
Try it again with all entries in B also ;-)
Remember the original poster had 100K entries!

Well, that's the closest I can do:

$ py
Python 2.4c1 (#3, Nov 26 2004, 23:39:44)
[GCC 3.3.3 (SuSE Linux)] on linux2
Type "help", "copyright" , "credits" or "license" for more information.

import sys; sys.ps1='.>>' ..>> alist=[line.strip() for line in open('/usr/share/dict/words')]
..>> words=set()
..>> for word in alist:
.... words.add(word + '\n')
.... words.add(word[::-1] + '\n')
....
..>> len(words)
90525
..>> words=list(word s)
..>> open('/tmp/A', 'w').writelines (words)
..>> import random; random.shuffle( words)
..>> open('/tmp/B', 'w').writelines (words[:90000])
..>>
$ time sort A B B | uniq -u >/dev/null

real 0m2.408s
user 0m2.437s
sys 0m0.037s
$ time grep -Fvf B A >/dev/null

real 0m1.208s
user 0m1.161s
sys 0m0.035s

What now?-)

Mind you, I only replied in the first place because you wrote (my
emphasis) "...here is *the* unix way..." and it's the bad days of the
month (not mine, actually, but I suffer along...)
and finally destroys original line
order (should it be important).

true

That's our final agreement :)

Note the order is trivial to restore with a
"decorate-sort-undecorate" idiom.

Using python or unix tools (eg 'paste -d', 'sort -k', 'cut -d')?
Because the python way has been already discussed by Friedrik, John and
Tim, and the unix way gets overly complicated (aka non-trivial) if DSU
is involved.

BTW, the following occurred to me:

tzot@tril/tmp
$ cat >A
aa
ss
dd
ff
gg
hh
jj
kk
ll
aa
tzot@tril/tmp
$ cat >B
ss
ff
hh
kk
tzot@tril/tmp
$ sort A B B | uniq -u
dd
gg
jj
ll
tzot@tril/tmp
$ grep -Fvf B A
aa
dd
gg
jj
ll
aa

Note that 'aa' is contained twice in the A file (to be filtered by B).
So our methods do not produce the same output. As far as the OP wrote:
Essentially, want to do efficient grep, i..e from A remove those lines which
are also present in file B.

grep is the unix way to go for both speed and correctness.

I would call this issue a dead horse.
--
TZOTZIOY, I speak England very best.
"Be strict when sending and tolerant when receiving." (from RFC1958)
I really should keep that in mind when talking with people, actually...

[P]

sf wrote:

The point is that when you have 100,000s of records, this grep becomes
really slow?

There are performance bugs with current versions of grep
and multibyte characters that are only getting addressed now.
To work around these do `export LANG=C` first.

In my experience grep is not scalable since it's O(n^2).
See below (note A and B are randomized versions of
/usr/share/dict/words (and therefore worst case for the
sort method)).

$ wc -l A B
45427 A
45427 B

$ export LANG=C

$ time grep -Fvf B A
real 0m0.437s

$ time sort A B B | uniq -u
real 0m0.262s

$ rpm -q grep coreutils
grep-2.5.1-16.1
coreutils-4.5.3-19

--
Pádraig Brady - http://www.pixelbeat.org
--

[Christos TZOTZIOY Georgiou]

On Fri, 17 Dec 2004 14:22:34 +0000, rumours say that [e-mail] m
might have written:

sf:

sf wrote:

The point is that when you have 100,000s of records, this grep becomes
really slow?
There are performance bugs with current versions of grep
and multibyte characters that are only getting addressed now.
To work around these do `export LANG=C` first.

You also should use the -F flag that Pádraig suggests, since you don't
have regular expressions in the B file.
In my experience grep is not scalable since it's O(n^2).
See below (note A and B are randomized versions of
/usr/share/dict/words (and therefore worst case for the
sort method)).

$ wc -l A B
45427 A
45427 B

$ export LANG=C

$ time grep -Fvf B A
real 0m0.437s

$ time sort A B B | uniq -u
real 0m0.262s

$ rpm -q grep coreutils
grep-2.5.1-16.1
coreutils-4.5.3-19

sf, you better do your own benchmarks (there is quick, sample code in
other posts of mine and Pádraig's) on your machine, since on my test
machine the numbers are reversed re to these of Pádraig's (grep takes
half the time).

package versions (on SuSE 9.1 64-bit):

$ rpm -q grep coreutils
grep-2.5.1-427
coreutils-5.2.1-21

language:
$ echo $LANG
en_US.UTF-8

Caution: both solutions are interexchangeab le as long as you don't have
duplicate lines in the A file. If you do, use the grep version.
--
TZOTZIOY, I speak England very best.
"Be strict when sending and tolerant when receiving." (from RFC1958)
I really should keep that in mind when talking with people, actually...