| # Here's a probably-not-new data structure I discovered after implementing weight-balanced trees with | |
| # amortized subtree rebuilds (e.g. http://jeffe.cs.illinois.edu/teaching/algorithms/notes/10-scapegoat-splay.pdf) | |
| # and realizing it was silly to turn a subtree into a sorted array with an in-order traversal only as an | |
| # aid in constructing a balanced subtree in linear time. Why not replace the subtree by the sorted array and | |
| # use binary search when hitting that leaf array? Then you'd defer any splitting of the array until inserts and | |
| # deletes hit that leaf array. Only in hindsight did I realize this is similar to the rope data structure for strings. | |
| # Unlike ropes, it's a key-value search tree for arbitrary ordered keys. | |
| # | |
| # The main attraction of this data structure is its simplicity (on par with a standard weight-balanced tree) and that it | |
| # coalesces subtrees into contiguous arrays, which reduces memory overhead and boosts the performance of in-order traversals |
| # Hash, displace, and compress: http://cmph.sourceforge.net/papers/esa09.pdf | |
| # This is expected linear time for any seeded hash function that acts like a random hash function (universality isn't enough). | |
| # (Actually, the code as written is O(n log n) when targeting 100% load. It's O(n) when targeting any smaller load factor.) | |
| # You can make keys_per_bucket higher than the default of 4 but construction time will start to increase dramatically. | |
| # The paper this is based on compresses the seeds (so the fact that the algorithm tries seeds in increasing order is important) | |
| # which brings the representation size close to the information-theoretical minimum. I don't do any of that here, but it could | |
| # be done as a postprocess. | |
| def make_perfect_hash(keys, load_factor=1.0, keys_per_bucket=4, rhash=murmurhash, max_seed=1000000): | |
| m = int(len(keys) / load_factor) | |
| r = int(len(keys) / keys_per_bucket) |
| // We have five kinds of nodes: literal, negate, not, add, xor. | |
| // In this case we only need 3 bits for the tag but you can use as many as you need. | |
| enum Tag { | |
| LIT, | |
| NEG, | |
| NOT, | |
| ADD, | |
| XOR, | |
| }; |
A traditional table-based DFA implementation looks like this:
uint8_t table[NUM_STATES][256]
uint8_t run(const uint8_t *start, const uint8_t *end, uint8_t state) {
for (const uint8_t *s = start; s != end; s++)
state = table[state][*s];
return state;
}
| // if 'f' is the 64-bit input CRC32-C (with 'incoming' 32-bit value of zero) then | |
| // there are 50 bijections (invertiable functions) which are a sum of f | |
| // and a simple xorshift. So the follow two forms: | |
| // | |
| // f(x) ^ (x ^ (x << S)) | |
| // f(x) ^ (x ^ (x >> S)) | |
| // | |
| // and 23 using a rotate instead of a shift: | |
| // |
| // Returns 8 bit fields at the given positions (in bits) and of the | |
| // given widths as 16-bit integers, with the values aligned with the | |
| // MSB at the top and garbage in the lower-order bits. | |
| // | |
| // The individual lens must be <=8, the positions are bit offsets | |
| // into the 128-bit "bytes". | |
| template< | |
| int pos0, int len0, | |
| int pos1, int len1, | |
| int pos2, int len2, |
| #include <stdio.h> | |
| #include <stdlib.h> | |
| #include <stdint.h> | |
| #include <string.h> | |
| #include <smmintrin.h> | |
| #ifdef __RADAVX__ | |
| #include <immintrin.h> | |
| #endif |