Hacker News Reader

Comment by Animats | Hacker News Reader

If everything that can match in a regular expression is valid UTF-8, and everything the regular expression can generate is valid UTF-8, you can just run the regular expression on the byte string.

This requires that matches match UTF-8 substrings, only. That's easy for explicit strings, such as "abc". For more general forms, "." must match one rune, not one byte. But that's not hard.

Python's problem is that strings are random-access indexable by rune (in the Go sense). Python either needs a representation that's rune-indexable, or it needs to generate an index array for strings that need one. There's an argument for the second approach, because most loops don't need a random-access index. "for i in "abcdef: ... " does not, for example.

View on HN

> Python's problem is that strings are random-access indexable by rune

Yeah, one of my points in the blog post is that random-access rune (code point) indexing isn't very valuable. Python is stuck with it, but if anyone in the future needs to make a similar choice, I hope they don't use O(1) rune indexing as a reason unless they have a very specific use case where O(1) rune indexing actually matters.

(I, for one, am very happy with the "rune" terminology, "char" is way too overloaded. It took me a minute to understand why they did that in Go when I first picked it up, but when I realized the reason I found it brilliant)

One approach for a Python implementation would be to store strings as UTF-8, and generate an index array as needed. For most operations, you don't need an index. Concatenation doesn't need one. Ordinary iteration (for c in "hello" :) doesn't need one. Regular expressions don't need an index. That covers most of the common use cases.

I like "rune" as terminology. A rune is one Unicode code point. A grapheme is a sequence of runes which should not be split.

Yeah, that could work. You don't even need a full index array, it can be a binary datastructure (I am reminded of how skip lists work), e.g. you start off with just one index for the halfway point and fill in things afterwards. There are lots of optimizations you could do.

I'm a bit wary of this because I fear indexing in Python is currently used more than this scheme can handle (i.e. too much for it to be considered a win), if erroneously. I'm not too sure. I certainly have written bad python code using indexing in the past, but that's just me (and many years ago).

String indexing is pretty rare. Most of them are s[0] or s[:n], where you don't need an index.

Typically this is found when parsing something, eg.

    if line[0] == '#':
      # skip comment lines
      continue

    prefixes = {...}
    for line in lines:
        prefix, remainder = line[:4], line[4:]
        if prefix not in prefixes:
            raise ValueError('Invalid prefix ' + prefix)
        parsed = prefixes[prefix](remainder)

Don't you need to index for `s[:n]`? You need to find the byte position of code point n. In current python this isn't a problem because the strings don't use a variable-width encoding, but we're talking about making Python use utf8 :)

It's also possible to chunk the index array: to store the byte-index of every 16th rune, say, and do a bit of cheap iteration afterward. I've had good success with this approach: it's fast, it's light on memory, and it preserves constant-time indexing by code point.

Reply on news.ycombinator.com