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.

[John Hunter]

>>>>> "sf" == sf <[e-mail]> writes:

sf> Just started thinking about learning python. Is there any
sf> place where I can get some free examples, especially for
sf> following kind of problem ( it must be trivial for those using
sf> python)

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

sf> I want to do

sf> " A - (A intersection B) "

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

If you're only talking about 100K lines or so, and you have a
reasonably modern computer, you can do this all in memory. If order
doesn't matter (it probably does) you can use a set to get all the
lines in file B that are not in A

from sets import Set
A = Set(file('test1 .dat').readline s())
B = Set(file('test2 .dat').readline s())
print B-A

To preserve order, you should use a dictionary that maps lines to line
numbers. You can later use these numbers to sort

A = dict([(line, num) for num,line in enumerate(file( 'test1.dat'))])
B = dict([(line, num) for num,line in enumerate(file( 'test2.dat'))])

keep = [(num, line) for line,num in B.items() if not A.has_key(line)]
keep.sort()
for num, line in keep:
print line,

Now someone else will come along and tell you all this functionality
is already in the standard library. But it's always fun to hack this
out yourself once because python makes such things so damned easy.

JDH

[Fredrik Lundh]

"sf" <[e-mail]> wrote:

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.

that's an unusual definition of "grep", but the following seems to
do what you want:

afile = "a.txt"
bfile = "b.txt"

bdict = dict.fromkeys(o pen(bfile).read lines())

for line in open(afile):
if line not in bdict:
print line,

</F>

[P]

sf wrote:

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.

You could implement elegantly using the new sets feature
For reference here is the unix way to do it:

sort a b b | uniq -u

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

[Tim Peters]

["sf" <[e-mail]>]

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.

[Fredrik Lundh] that's an unusual definition of "grep", but the following seems to
do what you want:

afile = "a.txt"
bfile = "b.txt"

bdict = dict.fromkeys(o pen(bfile).read lines())

for line in open(afile):
if line not in bdict:
print line,

</F>

Note that an open file is an iterable object, yielding the lines in
the file. The "for" loop exploited that above, but fromkeys() can
also exploit it. That is,

bdict = dict.fromkeys(o pen(bfile))

is good enough (there's no need for the .readlines()).

[Fredrik Lundh]

Tim Peters wrote:

bdict = dict.fromkeys(o pen(bfile).read lines())

for line in open(afile):
if line not in bdict:
print line,

</F>

Note that an open file is an iterable object, yielding the lines in
the file. The "for" loop exploited that above, but fromkeys() can
also exploit it. That is,

bdict = dict.fromkeys(o pen(bfile))

is good enough (there's no need for the .readlines()).

(sigh. my brain knows that, but my fingers keep forgetting)

and yes, for this purpose, "dict.fromk eys" can be replaced
with "set".

bdict = set(open(bfile) )

(and then you can save a few more bytes by renaming the
variable...)

</F>

[Tim Peters]

[Fredrik Lundh]

bdict = dict.fromkeys(o pen(bfile).read lines())

for line in open(afile):
if line not in bdict:
print line,

</F>

[Tim Peters] Note that an open file is an iterable object, yielding the lines in
the file. The "for" loop exploited that above, but fromkeys() can
also exploit it. That is,

bdict = dict.fromkeys(o pen(bfile))

is good enough (there's no need for the .readlines()).

[/F] (sigh. my brain knows that, but my fingers keep forgetting)

and yes, for this purpose, "dict.fromk eys" can be replaced
with "set".

bdict = set(open(bfile) )

(and then you can save a few more bytes by renaming the
variable...)

Except the latter two are just shallow spelling changes. Switching
from fromkeys(open(f ).readlines()) to fromkeys(open(f )) is much more
interesting, since it can allow major reduction in memory use. Even
if all the lines in the file are pairwise distinct, not materializing
them into a giant list can be a significant win. I wouldn't have
bothered replying if the only point were that you can save a couple
bytes of typing <wink>.

[P]

Christos TZOTZIOY Georgiou wrote:

On Wed, 15 Dec 2004 16:10:08 +0000, rumours say that [e-mail] m
might have written:

Essentiall y, want to do efficient grep, i..e from A remove those lines which
are also present in file B.
You could implement elegantly using the new sets feature
For reference here is the unix way to do it:

sort a b b | uniq -u

No, like I just wrote in another post, he wants

$ grep -vf B A

I think that

$ sort A B B | uniq -u

can be abbreviated to

$ sort -u A B B

which is the union rather than the intersection of the files

wrong. Notice the -u option to uniq.
http://marc.free.net.ph/message/2002....1bc24964.html
wastes some time by considering B twice
I challenge you to a benchmark :-)
and finally destroys original line
order (should it be important).

true

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

[Christos TZOTZIOY Georgiou]

On Thu, 16 Dec 2004 14:28:21 +0000, rumours say that [e-mail] m
might have written:

[sf]

Essentially , want to do efficient grep, i..e from A remove those lines which
are also present in file B.
[p@draig]You could implement elegantly using the new sets feature
For reference here is the unix way to do it:

sort a b b | uniq -u
[Christos]

No, like I just wrote in another post, he wants

$ grep -vf B A

I think that

$ sort A B B | uniq -u

can be abbreviated to

$ sort -u A B B

which is the union rather than the intersection of the files
[P@draig]

wrong. Notice the -u option to uniq.
http://marc.free.net.ph/message/2002....1bc24964.html

I see your point. That's a new to me use of uniq, since I started using
Unices long before GNU versions of the tools, but then, I might have
missed the -u option.

$ cat A
aa
ss
dd
ff
gg
hh
jj
kk
$ cat B
aa
dd
gg
jj
pp
$ time sort A B B | uniq -u
ff
hh
kk
ss

real 0m0.004s
user 0m0.004s
sys 0m0.004s
$ time grep -vf B A
ss
ff
hh
kk

real 0m0.003s
user 0m0.000s
sys 0m0.003s

So I stand corrected that your solution does *not* give the union.
wastes some time by considering B twice

I challenge you to a benchmark :-)

Well, the numbers I provided above are almost meaningless with such a
small set (and they easily could be reverse, I just kept the
convenient-to-me first run :). Do you really believe that sorting three
files and then scanning their merged output counting duplicates is
faster than scanning two files (and doing lookups during the second
scan)?

$ python
Python 2.3.3 (#1, Aug 31 2004, 13:51:39)
[GCC 3.3.3 (SuSE Linux)] on linux2
Type "help", "copyright" , "credits" or "license" for more information. x=open('/usr/share/dict/words').readlin es()
len(x) 45378 import random
random.shuffle( x)
open("/tmp/A", "w").writelines (x)
random.shuffle( x)
open("/tmp/B", "w").writelines (x[:1000])

$ time sort A B B | uniq -u >/dev/null

real 0m0.311s
user 0m0.315s
sys 0m0.008s
$ time grep -Fvf B A >/dev/null

real 0m0.067s
user 0m0.064s
sys 0m0.003s

(Yes, I cheated by adding the F (for no regular expressions) flag :)
and finally destroys original line
order (should it be important).

true

That's our final agreement :)
--
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]

Christos TZOTZIOY Georgiou wrote:

On Thu, 16 Dec 2004 14:28:21 +0000, rumours say that [e-mail] m

I challenge you to a benchmark :-)

Well, the numbers I provided above are almost meaningless with such a
small set (and they easily could be reverse, I just kept the
convenient-to-me first run :). Do you really believe that sorting three
files and then scanning their merged output counting duplicates is
faster than scanning two files (and doing lookups during the second
scan)?

$ python
Python 2.3.3 (#1, Aug 31 2004, 13:51:39)
[GCC 3.3.3 (SuSE Linux)] on linux2
Type "help", "copyright" , "credits" or "license" for more information.

x=open('/usr/share/dict/words').readlin es()
len(x)
45378
import random
random.shuf fle(x)
open("/tmp/A", "w").writelines (x)
random.shuf fle(x)
open("/tmp/B", "w").writelines (x[:1000])

$ time sort A B B | uniq -u >/dev/null

real 0m0.311s
user 0m0.315s
sys 0m0.008s
$ time grep -Fvf B A >/dev/null

real 0m0.067s
user 0m0.064s
sys 0m0.003s

(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!

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.

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