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

[Steve Holden]

Peter Otten wrote:

Bengt Richter wrote:

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']

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

No, you just realised subconsciously that we'd all spot the obvious one
and decided to point out the bug that would remain after the obvious one
had been fixed.

regards
Steve
--
Steve Holden [phone] [phone]
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/

[Tim Roberts]

Steven D'Aprano <st***@REMOVETH IScyber.com.au> wrote:

On Fri, 28 Oct 2005 15:29:46 +0200, Björn Lindström wrote:

"pi************ @gmail.com" <pi************ @gmail.com> writes:

f = open("filename" , "rb")
s = f.read()
sub = "\x00\x00\x01\x 00"
count = s.count(sub)
print count

That's a lot of lines. This is a bit off topic, but I just can't stand
unnecessary local variables.

print file("filename" , "rb").read().co unt("\x00\x00\x 01\x00")

Funny you should say that, because I can't stand unnecessary one-liners.

In any case, you are assuming that Python will automagically close the
file when you are done.

Nonsense. This behavior is deterministic. At the end of that line, the
anonymous file object out of scope, the object is deleted, and the file is
closed.
--
- Tim Roberts, ti**@probo.com
Providenza & Boekelheide, Inc.

[Scott David Daniels]

Paul Watson wrote:

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.

<ss = pattern, be = len(ss) - 1>
...
b = fp.read(blocksi ze)
count = 0
while len(b) > be:
count += b.count(ss)
b = b[-be:] + fp.read(blocksi ze)
...

In cases where that one wins and blocksize is big,
this should do even better:
...
block = fp.read(blocksi ze)
count = 0
while len(block) > be:
count += block.count(ss)
lead = block[-be :]
block = fp.read(blocksi ze)
count += (lead + block[: be]).count(ss)
...
--
-Scott David Daniels
sc***********@a cm.org

[Alex Martelli]

Tim Roberts <ti**@probo.com > wrote:
...

print file("filename" , "rb").read().co unt("\x00\x00\x 01\x00")

Funny you should say that, because I can't stand unnecessary one-liners.

In any case, you are assuming that Python will automagically close the
file when you are done.

Nonsense. This behavior is deterministic. At the end of that line, the
anonymous file object out of scope, the object is deleted, and the file is
closed.

In today's implementations of Classic Python, yes. In other equally
valid implementations of the language, such as Jython, IronPython, or,
for all we know, some future implementation of Classic, that may well
not be the case. Many, quite reasonably, dislike relying on a specific
implementation' s peculiarities, and prefer to write code that relies
only on what the _language_ specs guarantee.
Alex

[Steve Holden]

ne********@gmai l.com wrote:

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).

Indeed, but reading one byte at a time is about the slowest way to
process a file, in Python or any other language, because it fails to
amortize the overhead cost of function calls over many characters.

Buffering wasn't invented because early programmers had nothing better
to occupy their minds, remember :-)

regards
Steve
--
Steve Holden [phone] [phone]
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/

[Paul Watson]

"Alex Martelli" <al*****@yahoo. com> wrote in message
news:1h5760l.1e 2eatkurdeo7N%al *****@yahoo.com ...

In today's implementations of Classic Python, yes. In other equally
valid implementations of the language, such as Jython, IronPython, or,
for all we know, some future implementation of Classic, that may well
not be the case. Many, quite reasonably, dislike relying on a specific
implementation' s peculiarities, and prefer to write code that relies
only on what the _language_ specs guarantee.

How could I identify when Python code does not close files and depends on
the runtime to take care of this? I want to know that the code will work
well under other Python implementations and future implementations which may
not have this provided.

[Paul Rubin]

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

How could I identify when Python code does not close files and depends on
the runtime to take care of this? I want to know that the code will work
well under other Python implementations and future implementations which may
not have this provided.

There is nothing in the Python language reference that guarantees the
files will be closed when the references go out of scope. That
CPython does it is simply an implementation artifact. If you want to
make sure they get closed, you have to close them explicitly. There
are some Python language extensions in the works to make this more
convenient (PEP 343) but for now you have to do it by hand.

[David Rasmussen]

ne********@gmai l.com wrote:

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.)

I already have that book. The above solution very slow in practice. None
of the solutions presented in this thread is nearly as fast as the

print file("filename" , "rb").read().co unt("\x00\x00\x 01\x00")

/David

[Steven D'Aprano]

On Sat, 29 Oct 2005 21:08:09 +0000, Tim Roberts wrote:

In any case, you are assuming that Python will automagically close the
file when you are done.

Nonsense. This behavior is deterministic. At the end of that line, the
anonymous file object out of scope, the object is deleted, and the file is
closed.

That is an implementation detail. CPython may do that, but JPython does
not -- or at least it did not last time I looked. JPython doesn't
guarantee that the file will be closed at any particular time, just that
it will be closed eventually.

If all goes well. What if you have a circular dependence and the file
reference never gets garbage-collected? What happens if the JPython
process gets killed before the file is closed? You might not care about
one file not being released, but what if it is hundreds of files?

In general, it is best practice to release external resources as soon as
you're done with them, and not rely on a garbage collector which may or
may not release them in a timely manner.

There are circumstances where things do not go well and the file never
gets closed cleanly -- for example, when your disk is full, and the
buffer is only written to disk when you close the file. Would you
prefer that error to raise an exception, or to pass silently? If you want
close exceptions to pass silently, then by all means rely on the garbage
collector to close the file.

You might not care about these details in a short script -- when I'm
writing a use-once-and-throw-away script, that's what I do. But it isn't
best practice: explicit is better than implicit.

I should also point out that for really serious work, the idiom:

f = file("parrot")
handle(f)
f.close()

is insufficiently robust for production level code. That was a detail I
didn't think I needed to drop on the original newbie poster, but depending
on how paranoid you are, or how many exceptions you want to insulate the
user from, something like this might be needed:

try:
f = file("parrot")
try:
handle(f)
finally:
try:
f.close()
except:
print "The file could not be closed; see your sys admin."
except:
print "The file could not be opened."
--
Steven.

[Mike Meyer]

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

"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.

Um - you removed the code, but I could have *sworn* that it did
something like:

buf = buf[testlen:] + f.read(bufsize - testlen)

which should cause the the creation of three strings: the last few
bytes of the old buffer, a new bufferfull from the read, then the sum
of those two - created by copying the first two into a new string. So
you wind up copying all the data.

Which, as you showed, doesn't take nearly as much time as using mmap.

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