Scanning a file

[pinkfloydhomer]

I want to scan a file byte for byte for occurences of the the four byte
pattern 0x00000100. I've tried with this:

# start
import sys

numChars = 0
startCode = 0
count = 0

inputFile = sys.stdin

while True:
ch = inputFile.read( 1)
numChars += 1

if len(ch) < 1: break

startCode = ((startCode << 8) & 0xffffffff) | (ord(ch))
if numChars < 4: continue

if startCode == 0x00000100:
count = count + 1

print count
# end

But it is very slow. What is the fastest way to do this? Using some
native call? Using a buffer? Using whatever?

/David

[Mike Meyer]

"Paul Watson" <pw*****@redlin epy.com> writes:

Here is a better one that counts, and not just detects, the substring. This
is -much- faster than using mmap; especially for a large file that may cause
paging to start. Using mmap can be -very- slow.

#!/usr/bin/env python
import sys

fn = 't2.dat'
ss = '\x00\x00\x01\x 00'

be = len(ss) - 1 # length of overlap to check
blocksize = 64 * 1024 # need to ensure that blocksize > overlap

fp = open(fn, 'rb')
b = fp.read(blocksi ze)
count = 0
while len(b) > be:
count += b.count(ss)
b = b[-be:] + fp.read(blocksi ze)
fp.close()

print count
sys.exit(0)

Did you do timings on it vs. mmap? Having to copy the data multiple
times to deal with the overlap - thanks to strings being immutable -
would seem to be a lose, and makes me wonder how it could be faster
than mmap in general.

Thanks,
<mike
--
Mike Meyer <mw*@mired.or g> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

[Fredrik Lundh]

Mike Meyer wrote:

Did you do timings on it vs. mmap? Having to copy the data multiple
times to deal with the overlap - thanks to strings being immutable -
would seem to be a lose, and makes me wonder how it could be faster
than mmap in general.

if you use "mmap" to read large files sequentially, without calling "madvise",
the system may try to keep old pages around just in case, and won't do as
much read-ahead as it can do. if you're low on memory, that means that
the system may waste some time swapping out data for other applications,
rather than throwing away data that you know that you will never look at
again.

if you have reasonably large files and you're not running on an overcrowded
machine, this is usually not a problem.

(does Python's mmap module support madvise, btw? doesn't look like it does...)

</F>

[Bengt Richter]

On 28 Oct 2005 06:51:36 -0700, "pi************ @gmail.com" <pi************ @gmail.com> wrote:

First of all, this isn't a text file, it is a binary file. Secondly,
substrings can overlap. In the sequence 0010010 the substring 0010
occurs twice.

ISTM you better let others know exactly what you mean by this, before
you use the various solutions suggested or your own ;-)

a) Are you talking about bit strings or byte strings?
b) Do you want to _count_ overlapping substrings??!!
Note result of s.count on your example:

s = '0010010'
s.count('0010') 1

vs. brute force counting overlapped substrings (not tested beyond what you see ;-)
def ovcount(s, sub): ... start = count = 0
... while True:
... start = s.find(sub, start) + 1
... if start==0: break
... count += 1
... return count
... ovcount(s, '0010')

2

Regards,
Bengt Richter

[Bengt Richter]

On Fri, 28 Oct 2005 20:03:17 -0700, al*****@yahoo.c om (Alex Martelli) wrote:

Mike Meyer <mw*@mired.or g> wrote:
...

Except if you can't read the file into memory because it's to large,
there's a pretty good chance you won't be able to mmap it either. To
deal with huge files, the only option is to read the file in in
chunks, count the occurences in each chunk, and then do some fiddling
to deal with the pattern landing on a boundary.

That's the kind of things generators are for...:

def byblocks(f, blocksize, overlap):
block = f.read(blocksiz e)
yield block
while block:
block = block[-overlap:] + f.read(blocksiz e-overlap)
if block: yield block

Now, to look for a substring of length N in an open binary file f:

f = open(whatever, 'b')
count = 0
for block in byblocks(f, 1024*1024, len(subst)-1):
count += block.count(sub st)
f.close()

not much "fiddling" needed, as you can see, and what little "fiddling"
is needed is entirely encompassed by the generator...

Do I get a job at google if I find something wrong with the above? ;-)

Regards,
Bengt Richter

[Peter Otten]

Bengt Richter wrote:

On Fri, 28 Oct 2005 20:03:17 -0700, al*****@yahoo.c om (Alex Martelli)
wrote:

Mike Meyer <mw*@mired.or g> wrote:
...

Except if you can't read the file into memory because it's to large,
there's a pretty good chance you won't be able to mmap it either. To
deal with huge files, the only option is to read the file in in
chunks, count the occurences in each chunk, and then do some fiddling
to deal with the pattern landing on a boundary.

That's the kind of things generators are for...:

def byblocks(f, blocksize, overlap):
block = f.read(blocksiz e)
yield block
while block:
block = block[-overlap:] + f.read(blocksiz e-overlap)
if block: yield block

Now, to look for a substring of length N in an open binary file f:

f = open(whatever, 'b')
count = 0
for block in byblocks(f, 1024*1024, len(subst)-1):
count += block.count(sub st)
f.close()

not much "fiddling" needed, as you can see, and what little "fiddling"
is needed is entirely encompassed by the generator...

Do I get a job at google if I find something wrong with the above? ;-)

Try it with a subst of length 1. Seems like you missed an opportunity :-)

Peter

[Bengt Richter]

On Sat, 29 Oct 2005 10:34:24 +0200, Peter Otten <__*******@web. de> wrote:

Bengt Richter wrote:

On Fri, 28 Oct 2005 20:03:17 -0700, al*****@yahoo.c om (Alex Martelli)
wrote:

Mike Meyer <mw*@mired.or g> wrote:
...
Except if you can't read the file into memory because it's to large,
there's a pretty good chance you won't be able to mmap it either. To
deal with huge files, the only option is to read the file in in
chunks, count the occurences in each chunk, and then do some fiddling
to deal with the pattern landing on a boundary.

That's the kind of things generators are for...:

def byblocks(f, blocksize, overlap):
block = f.read(blocksiz e)
yield block
while block:
block = block[-overlap:] + f.read(blocksiz e-overlap)
if block: yield block

Now, to look for a substring of length N in an open binary file f:

f = open(whatever, 'b')
count = 0
for block in byblocks(f, 1024*1024, len(subst)-1):
count += block.count(sub st)
f.close()

not much "fiddling" needed, as you can see, and what little "fiddling"
is needed is entirely encompassed by the generator...

Do I get a job at google if I find something wrong with the above? ;-)

Try it with a subst of length 1. Seems like you missed an opportunity :-)

I was thinking this was an example a la Alex's previous discussion
of interviewee code challenges ;-)

What struck me was

gen = byblocks(String IO.StringIO('no '),1024,len('en d?')-1)
[gen.next() for i in xrange(10)]

['no', 'no', 'no', 'no', 'no', 'no', 'no', 'no', 'no', 'no']

Regards,
Bengt Richter

[Alex Martelli]

Bengt Richter <bo**@oz.net> wrote:
...

while block:
block = block[-overlap:] + f.read(blocksiz e-overlap)
if block: yield block

...

I was thinking this was an example a la Alex's previous discussion
of interviewee code challenges ;-)

What struck me was
>>> gen = byblocks(String IO.StringIO('no '),1024,len('en d?')-1)
>>> [gen.next() for i in xrange(10)]

['no', 'no', 'no', 'no', 'no', 'no', 'no', 'no', 'no', 'no']

Heh, OK, I should get back into the habit of adding a "warning: untested
code" when I post code (particularly when it's late and I'm
jetlagged;-). The code I posted will never exit, since block always
keeps the last overlap bytes; it needs to be changed into something like
(warning -- untested code!-)

if overlap>0:
while True:
next = f.read(blocksiz e-overlap)
if not next: break
block = block[-overlap:] + next
yield block
else:
while True:
next = f.read(blocksiz e)
if not next: break
yield next

(the if/else is needed to handle requests for overlaps <= 0, if desired;
I think it's clearer to split the cases rather than to test inside the
loop's body).
Alex

[Peter Otten]

Bengt Richter wrote:

What struck me was

*gen*=*byblo cks(StringIO.St ringIO('no'),10 24,len('end?')-1)
*[gen.next()*for* i*in*xrange(10)]

['no',*'no',*'no ',*'no',*'no',* 'no',*'no',*'no ',*'no',*'no']

Ouch. Seems like I spotted the subtle cornercase error and missed the big
one.

Peter

[Paul Watson]

"Mike Meyer" <mw*@mired.or g> wrote in message
news:86******** ****@bhuda.mire d.org...

"Paul Watson" <pw*****@redlin epy.com> writes: .... Did you do timings on it vs. mmap? Having to copy the data multiple
times to deal with the overlap - thanks to strings being immutable -
would seem to be a lose, and makes me wonder how it could be faster
than mmap in general.

The only thing copied is a string one byte less than the search string for
each block.

I did not do due dilligence with respect to timings. Here is a small
dataset read sequentially and using mmap.

$ ls -lgG t.dat
-rw-r--r-- 1 16777216 Oct 28 16:32 t.dat
$ time ./scanfile.py
1048576
0.80s real 0.64s user 0.15s system
$ time ./scanfilemmap.py
1048576
20.33s real 6.09s user 14.24s system

With a larger file, the system time skyrockets. I assume that to be the
paging mechanism in the OS. This is Cyngwin on Windows XP.

$ ls -lgG t2.dat
-rw-r--r-- 1 268435456 Oct 28 16:33 t2.dat
$ time ./scanfile.py
16777216
28.85s real 16.37s user 0.93s system
$ time ./scanfilemmap.py
16777216
323.45s real 94.45s user 227.74s system

[netvaibhav]

I think implementing a finite state automaton would be a good (best?)
solution. I have drawn a FSM for you (try viewing the following in
fixed width font). Just increment the count when you reach state 5.

<---------------|
| |
0 0 | 1 0 |0
-->[1]--->[2]--->[3]--->[4]--->[5]-|
^ | | ^ | | |
1| |<---| | | |1 |1
|_| 1 |_| | |
^ 0 | |
|---------------------|<-----|

If you don't understand FSM's, try getting a book on computational
theory (the book by Hopcroft & Ullman is great.)

Here you don't have special cases whether reading in blocks or reading
whole at once (as you only need one byte at a time).

Vaibhav