Hacker News Reader

Comment by Animats | Hacker News Reader

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.

View on HN

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

Reply on news.ycombinator.com