3 ms·
Replaced the linked list with a Python list, for clarity: https://gist.github.com/tommie/577b4e154731a280136295180211e953 https://gist.github.com/tommie/577b4e1
by tommiegannert 3y ago
Replaced the linked list with a Python list, for clarity: https://gist.github.com/tommie/577b4e154731a280136295180211e953 https://gist.github.com/tommie/577b4e154731a280136295180211e... (and I hope I got it right)
Since this is using a 1-bit visited counter, a small cache could use a bit vector and bit shifting to "remove" a value from the queue.
- falserum 3y agoPython list is backed by array. So removing an element from the middle of list is costly. (I assume this was the reason for linked list usage in original version)
- tommiegannert 3y agoIndeed, but this is clearer to read.
- ianbicking 3y agoPython's ordered dict uses an efficient linked list implementation, it might be elegant here?
- tommiegannert 3y agoOh, interesting. The documentation there also says > They have become less important now that the built-in dict class gained the ability to remember insertion order (this new behavior became guaranteed in Python 3.7). https://docs.python.org/3/library/collections.html#ordereddict-objects https://docs.python.org/3/library/collections.html#ordereddi... It assumes iterators are stable (and valid) under insertion, and I can't find any docs on that for either. Since you (AFAIK) can't create an iterator at a specific key, we also couldn't use keys as the "hand."