@bascule You mean Ruby Array, or you mean, in C, under the hood, as an array? Because list outperforming array in C would be surprising.
I'm pretty surprised how many crappy LRUs there are implemented with an array instead of a doubly linked list o_O
-
-
-
@tqbf Ruby arrays... also removing elements from a even a C array sucks if you need to preserve order -
@bascule You can amortize the cost by invalidating entries and then collecting every N deletes. -
@tqbf removing from a DLL is O(1) if you know the element's location ;) -
@bascule Yes, but having to seek around memory for individually allocated list nodes can hurt. I'm not arguing with you, though! -
@tqbf you can get the node to remove out of the hash
End of conversation
New conversation -
-
-
@bascule was asked about LRU in interview and was told how many people don't know/think of doubly linked list. -
@ehthayer unfortunately the best algorithm is patented :( http://patft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=6996676.PN.&OS=PN/6996676&RS=PN/6996676 … -
@bascule shoot, that looks tasty
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.