5 ms·

I wonder if using a trie instead of a hash would have provided a performance win. if you're parsing the file row by row, iterating over the trie as you process

I wonder if using a trie instead of a hash would have provided a performance win. if you're parsing the file row by row, iterating over the trie as you process each character (as they argue to calculate the int value) (so what you have to do to hash it anyways), should be similar. What you'd end up in is micro-architectual issues on cache performance.

haxen 3y ago
Interestingly enough, that was my first idea. But when you consider the tiny keyset size, it would be hard to beat two machine instructions to calculate the hash + a single array lookup.
gunnarmorling 3y ago
There is one entry which uses a trie, but it's not at the top, IIRC (which may or may not be related to using a trie, there's many other relevant design decisions).
o11c 3y ago
There's a reason everybody uses hashing - if your data is trusted, it does very few operations. Tries have to allocate, walk, and interpret multiple nodes. Perhaps not as bad as trees (though that depends on how many possible trie node representations there are, vs what the data density is at each level), but still worse than the non-colliding hash. That said, with a finite dataset a perfect hash would probably beat a general hash though.
- koliber 3y ago
  Was the list of city names known? Could you statically pre-build the Trie structure?
  - haxen 3y ago
    It was known, but the requirement was that the program keep working for an arbitrary keyset that conforms to the specified rules (up to 10,000 unique keys, each up to 100 bytes in length).
paulddraper 3y ago
Tries are rarely the most efficient option. Kind of like linked lists...conceptually pleasant but rarely if ever the best option for real-world perf.
anonymoushn 3y ago
Top solutions tend to use hashes that ignore many input bytes. Even if they did not, they would use hashes that consume 4 or 8 bytes of input at a time (you could do more if the language exposed aesenc)

haxen 3y ago

Interestingly enough, that was my first idea. But when you consider the tiny keyset size, it would be hard to beat two machine instructions to calculate the hash + a single array lookup.

gunnarmorling 3y ago

There is one entry which uses a trie, but it's not at the top, IIRC (which may or may not be related to using a trie, there's many other relevant design decisions).

o11c 3y ago

There's a reason everybody uses hashing - if your data is trusted, it does very few operations. Tries have to allocate, walk, and interpret multiple nodes. Perhaps not as bad as trees (though that depends on how many possible trie node representations there are, vs what the data density is at each level), but still worse than the non-colliding hash. That said, with a finite dataset a perfect hash would probably beat a general hash though.

koliber 3y ago
Was the list of city names known? Could you statically pre-build the Trie structure?
- haxen 3y ago
  It was known, but the requirement was that the program keep working for an arbitrary keyset that conforms to the specified rules (up to 10,000 unique keys, each up to 100 bytes in length).

paulddraper 3y ago

Tries are rarely the most efficient option. Kind of like linked lists...conceptually pleasant but rarely if ever the best option for real-world perf.

anonymoushn 3y ago

Top solutions tend to use hashes that ignore many input bytes. Even if they did not, they would use hashes that consume 4 or 8 bytes of input at a time (you could do more if the language exposed aesenc)