2

I'm looking for a way to run a regex over a (long) iterable of "characters" in Python. (Python doesn't actually have characters, so it's actually an iterable of one-length strings. But same difference.)

The re module only allows searching over strings (or buffers), as far as I can tell.

I could implement it myself, but that seems a little silly.

Alternatively, I could convert the iterable to a string and run the regex over the string, but that gets (hideously) inefficient. (A worst-case example: re.search(".a", "".join('a' for a in range(10**8))) peaks at over 900M of RAM (private working set) on my (x64) machine, and takes ~12 seconds, even though it only needs to look at the first two characters in the iterable.)

pepr
  • 20,112
  • 15
  • 76
  • 139
TLW
  • 1,373
  • 9
  • 22
  • 2
    *"it only needs to look at the first character in the iterable."* Then why do you need regex in the first place? – netcoder May 14 '14 at 12:35
  • Without regular expressions there is the [startswith](https://docs.python.org/2/library/stdtypes.html#str.startswith) function `for string in iterable : if string.startswith("a") : print("Eureka")` – llrs May 14 '14 at 12:41
  • What are you actually trying to achieve? – deadly May 14 '14 at 12:51
  • 3
    +1. If I understand your thinking well, then this is actually a great question. I would translate it to: *Is there any streaming regular expression for Python?* – pepr May 14 '14 at 20:26
  • 1
    What sort of expression do you need? Do you need lookaheads, backreferences, etc? – Joel Cornett May 14 '14 at 20:28
  • @Netcoder - that was an example to show what I meant. – TLW May 14 '14 at 20:44
  • @pepr - Thanks. I sometimes (always) have trouble with phrasing. That is indeed what I meant. – TLW May 14 '14 at 20:46
  • @JoelCornett - I'd prefer a 'fully featured' regular expression, yes. Looking through, I don't actually _need_ either _currently_, but some things would be clunky without them, and I may need them later. – TLW May 14 '14 at 20:55

2 Answers2

3

As far as I understand, the example that joins a lot of 'a's is just extremely simple example that shows the problem. In other words, the construction of the content (generally) can be more time and memory consuming than the search itself.

The problem with the standard re module is that it uses the extended regular expression syntax, and it requires backtracking.

You may be interested in the very classic implementation by Thomson (NFA) -- see http://swtch.com/~rsc/regexp/regexp1.html for the explanation and the comparison of performance with the libraries that implement the extended syntax.

It seems that the re2 project can be useful for you. There should be the Python port -- see Is it possible to use re2 from Python? However, I do not know if it supports streaming and wherher any streaming regular expression engine for Python exists.

For understanding the Thomsons idea, you can also try the on-line visualization of the Regular Expression to NFA.

Community
  • 1
  • 1
pepr
  • 20,112
  • 15
  • 76
  • 139
  • So there's nothing built-in to Python that can achieve this, then? Too bad. – TLW May 14 '14 at 20:45
  • I am afraid it is not the major goal of the regular expression implementations in majority of programming languages. You should better explain for what kind of regular expressions you need -- as Joel Cornett asked in the comment just below your question. Look at the last link. You will find there also some generators for engines that may solve your problem. – pepr May 14 '14 at 20:59
0

If the number of elements in that list is truly to the order of 10**8 then you are probably better off doing a linear search if you only want to do it once. Otherwise, you have to create this huge string that is really very inefficient. The other thing I can think of if you need to do this more than once is inserting the collection into a hashtable and do the search faster.

Farhad Alizadeh Noori
  • 2,276
  • 17
  • 22