6

I am trying to seek to a token ':path,' in a file, then read all the following (arbitrary digit count) numbers as a number (so for ':path,123' I seek to the , in file then read the integer 123). Then read the chars between the current seek position and pos+123 (store them in a list or whatever). Then seek until the next match for ':path,' and repeat the process.

I would like a function a bit like:

 def fregseek(FILE, current_seek, /regex/): . . value_found = ? # result of reading next N chars after :path,[0-9]+ . . return next_start_seek, value_found

There may be any number of matches for ':path,' in a line, and that string may occur within the number of chars specified after ','. I have written a messy bunch of rubbish which reads in each line, then for each line chomps of the first N chars indicated by the match, then continues processing the string until it is all eaten up. Then reads the next string and so on.

This is horrible, I do not want to have to slurp off all the lines from a potentially huge file when all I really need to do is seek (especially since a newline is irrelevant, so having an extra processing step just because lines are easy to pull from files is ridiculous).

So, there it is, that is my problem that I would like to solve. I need to seek to a match, read a value, continue from the end of that value looking for the next match and so on until the file is exhausted.

If anybody can help me with this I will be happy to hear from them :)

I would like to avoid non-standard libraries if possible, I would also like the shortest code but this is the least of my concerns (speed and memory consumption are the important factors, but I don't want 50 loc extra just to bootstrap some library with a small funciton in it I could just rip out if only I knew what it was).

I would prefer python code, however, if perl beats python in this regard I will use perl instead, I am also open to clever sed/awk/bash scripts etc as long as they are not horribly slower.

Thanks very much in advance.

Improve this question
6
  • Does it need to use regex? If you're just trying to seek to a token like ":path", that's unnecessary, and it will be easier (and more efficient) if you just do a string search. Commented Sep 26, 2012 at 22:36
  • Also, you keep talking about seeking, but there's no way to do a search without scanning all the bytes, and I don't see anything you can't do in a single pass, so I'm not sure why you need any seeking at all. Commented Sep 26, 2012 at 22:38
  • Thanks for the comments abarnert. A string search is fine if I don't have to read in the whole file at once, but I'd have to efficiently handle whatever chunk I read in. I'm not sure if there is a better way than reading it all in, although I would like to be able to handle arbitrarily large files. Ideally, I would have several options to benchmark, but right now I just have my crappy code, there's already an answer much better than what I have now :) Commented Sep 26, 2012 at 22:50
  • OK, can you map the whole file at once (and let the OS worry about the disk I/O)? If you don't know the answer, it's probably yes if your files are <<2GB or if you only care about 64-bit platforms, no otherwise. If the answer is yes, you can write code that's almost the same as if you read the whole file into a str/bytes, but using an mmap object instead. Commented Sep 26, 2012 at 23:01
  • Usually I can map the whole file at once, but sometimes the file is over 4gb and I would like to, if possible, not restrict myself to 64bit machines. I am also not sure whether benchmarks of alternative approaches (e.g. reading part at a time) would work out better, but I'd sure like to see what algorithms people come up with. Failling a more universal approach, I like the one presented by BrtH, I think its an elegant solution to my problem, even if not exactly what I asked for. Commented Sep 26, 2012 at 23:07

2 Answers 2

Reset to default
3

If you don't need regexes, you can do this with just find and slicing.

Either way, the trivial solution is to read the whole file into memory, and find and slice the resulting str/bytes object.

But that doesn't work if you can't (or don't want to) read the whole file into memory.

Fortunately, if you can count on the fact that your files are << 2GB or you only need to work in 64-bit Python, and you're on a reasonable platform (POSIX, modern Windows, etc.), you can mmap the file into memory instead. The mmap object has a subset of the same methods that strings have, so you can just pretend you have a string, just as if you'd read the whole file into memory, but you can count on the Python implementation and OS to make it just work with reasonable efficiency.

Depending on your version of Python, re may not be able to scan an mmap as if it were a string, it may work but be slow, or it may work just fine. So, you might as well try that first, and if it doesn't throw an exception or go much slower than you expected, you're done:

def findpaths(fname): with open(fname, 'rb') as f: m = mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ) for match in re.finditer(':path,([0-9]+)', m): yield m[match.end():match.end()+int(match.group(1))]

(This is the same as BrtH's answer, just using an mmap instead of a string, and restructured to a generator instead of a list—although of course you could do the latter part by just replacing his square brackets with parentheses.)

If you're using an older (or non-CPython?) version of Python that can't (efficiently) re an mmap, it's a bit more complicated:

def nextdigits(s, start): return ''.join(itertools.takewhile(str.isdigit, itertools.islice(s, start, None))) def findpaths(fname): with open(fname, 'rb') as f: m = mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ) i = 0 while True: n = m.find(':path', i) if n == -1: return countstr = nextdigits(m, n+6) count = int(countstr) n += 6 + len(countstr) yield m[n:n+count] i = n + 6 + count

This probably isn't the fastest way to write the nextdigits function. I'm not sure that will actually matter (time it and see), but if it does, other possibilities are to slice out m[n+6:n+A_BIG_ENOUGH_NUMBER] and regex it, or write a custom loop, or… On the other hand, if that's your bottleneck, you might get far more benefit by switching to an interpreter with a JIT (PyPy, Jython, or IronPython)…

For my tests, I split things up: findpaths takes a string-like object, and the caller does the with open and mmap bits and just passes m into findpaths; I didn't do it here just for brevity.

Anyway, I've tested both versions against the following data:

BLAH:path,3abcBLAH:path,10abcdefghijklmnBLAH:path,3abc:path,0:path,3abc

And the output was:

abc abcdefghij abc abc

I think that's correct?

If my earlier version caused it to spin at 100% CPU, my guess would be that I didn't increment i properly in the loop; that's the most common reason you get that behavior in a tight parsing loop. Anyway, if you can reproduce that with the current version, please post the data.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Thank you for your suggestion, I like the idea of returning a generator. Its not quite working for me, for some reason when I actually try using the returned generator I either get very quick execution with nothing happening or munching all my system resources and needing killing (with a very small test file). Could you show me how you used it please?
This is a good answer and meets the requirements probably better than mine, so +1.
But there is one thing I don't understand. It seems that you assume that the count is already known and is constant. But if I understood the question correctly, this isn't the case, and you have to also find the count. And unless the count always has three digits, you will have to find it with a regex. And I think that you can use i = n + 7, because the word :path,{at least one digit} can't overlap.
@BrtH: Right on both counts. You don't have to use a regex to read the count, but it is definitely simpler, and maybe more efficient. Even if you can't regex the mmap in the first place, it's possible that regexing a small slice like m[n+6:n+50] would be the best solution.
Thanks so much for your answer abarnert, very comprehensive and well explained. Now I can get on with parsing mitmproxy flow files efficiently (which in itself is a miniscule portion of my current project)
|
3

You can do it in nearly one line in python:

with open('filename.txt') as f: text = f.read() results = [text[i[0]:i[0] + i[1]] for i in ((m.end(), int(m.group(1))) for m in re.finditer(':path,([0-9]+)', text))]

Note: untested...

Improve this answer

1 Comment

That works just fine for me for small files, thanks very much! I upvoted because it is a good answer and much more efficient than what I had. I'm holding out for an answer which doesn't require reading in the whole file at once, but handles arbitrarily large files (maybe using mmap?). If I don't find it here, I'll accept yours, because its helped me move on with a much broader range of files, albeit not meeting the zenith of my requirements (arbitrary file size with little extra cost ... no small order!). Thank you again for your contribution :)

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.