[gambit-list] SRFI 14 and data structures in gambit/lib/gambit/char/char#.scm

Marc Feeley feeley at iro.umontreal.ca
Sun May 21 09:05:13 EDT 2023


> On May 20, 2023, at 3:34 AM, John Cowan <cowan at ccil.org> wrote:
> 
> 
> Maybe a few more codes could be added for P*, S*, M* and N* above 199 in 
> your encoding in char#.scm to have fast membership testing for all the 
> "standard" classes.'
> 
> That makes sense to me.

Is it guaranteed by the Unicode standard that those properties are mutually exclusive with the other properties (letter, digit, etc)?

If so, that would be easy to add.

Concerning the general representation, I’m considering using a structure containing a “negation” flag and a reference to a vector (and other things like the size of the set). The vector has increasing values which are the Unicode points where there is a transition between “in the set” and “out of the set”. Because of the separate negation flag, the representation can assume that the Unicode point 0 is always in the set represented by the vector (in other words the first element of the vector will never be 0). This gives a constant time for set negation which I expect is a frequent operation. Moreover I’m thinking that the vector can be either a u32vector, a u16vector, or a u8vector depending on the size of the last value in the vector. When representing character sets over the latin-1 characters, probably a common situation, then a factor of 4 improvement in space is possible (although in this situation a plain bitmap might be a better idea for compactness and speed of membership testing). Benchmarking needed to sort this out!

Marc




More information about the Gambit-list mailing list