thcrt, 15 days ago

@nedbat @glyph this is really interesting! are there any downsides?

nedbat, 15 days ago

@thcrt @glyph If your grid isn't sparse, it could use more memory than other representations.

glyph, 15 days ago

@nedbat @thcrt In practice I think that Python's dicts specifically are surprisingly compact as compared to a naive / textbook hashtable implementation

glyph, 15 days ago

@nedbat @thcrt (to be clear, this is a "yes, and"; it definitely could use a bit more memory, just maybe less-more than one might initially think. measuring this empirically would be super interesting!)

glyph, 15 days ago

@nedbat @thcrt the "new" dictionary implementation used by python is well over a decade old at this point (💀) and was first developed in PyPy. You can read about it here: https://www.pypy.org/posts/2015/01/faster-more-memory-efficient-and-more-4096950404745375390.html . It was added to CPython only a year later: https://mail.python.org/pipermail/python-dev/2016-September/146327.html

vwbusguy, 15 days ago

@nedbat Indeed - the key just needs to be immutable and unique.

I did something like this in a Rust program once, but using defined structs. Unsurprisingly, the python way is much less verbose.

https://github.com/vwbusguy/curses-examples/blob/master/rust/src/main.rs

freeradical, 15 days ago

@nedbat One thing I learned from Advent of Code is that using complex numbers instead of tuples(e.g. 1+ 2i instead of (1,2) ) has many advantages. Those should work as dict keys too, right? (hashable)

nedbat, 15 days ago

@freeradical Complex numbers are hashable, and so can be used as dict keys. I never liked that technique though, because it doesn't generalize to more dimensions.