tag:blogger.com,1999:blog-876358347971598886.post5512475025629513867..comments2022-03-18T05:33:29.769+02:00Comments on nothingmuch's perl blog: Why another caching module?nothingmuchhttp://www.blogger.com/profile/03855760206940108541noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-876358347971598886.post-10406755404184629032010-07-03T23:19:54.974+03:002010-07-03T23:19:54.974+03:00Heaps are optimized to add an element anywhere in ...Heaps are optimized to add an element anywhere in the ordering, and to remove from the head.<br /><br />To update LRU we need to add an element only to the tail (therefore ordering is not important, the element being inserted is always "biggest"), to remove elements from the head, and most importantly to remove elements from the middle (every hit moves the key to the end of the list again, since it's more recently used).<br /><br />Implementing a binary heap over an array is definitely nice for heapsorting because it's a very compact representation, but in this case not helpful because to extract an element from the middle and to reinsert it with a new key is O(N) + O(log N), since all the entries after it in the heap need to be moved up one spot, instead of log N swaps.nothingmuchhttps://www.blogger.com/profile/03975438115490089158noreply@blogger.comtag:blogger.com,1999:blog-876358347971598886.post-22689505183692935052010-07-03T21:43:05.999+03:002010-07-03T21:43:05.999+03:00Errr... I was thinking about implementing priority...Errr... I was thinking about implementing priority queue using array implementation of heap. Adding an element to heap is O(log N), as is removing "smallest" element from heap. Getting "smallest" element from heap is O(1).<br /><br />You can implement heap in array, by assuming that children of element at i-th position (if they exist) are at 2*i and 2*i+1 indices. See "Programming Pearls" by Jon Bentley (where such structure was used to implement heapsort).<br /><br />Unless there are some operations beside "add element" and "remove smallest" that are needed for LRU algorithm bookkeeping?Jakub Narebskihttps://www.blogger.com/profile/11847202568800326989noreply@blogger.comtag:blogger.com,1999:blog-876358347971598886.post-38739702951688869482010-07-03T15:57:17.567+03:002010-07-03T15:57:17.567+03:00That would require timestamping or a counter but o...That would require timestamping or a counter but otherwise would be doable.<br /><br />The doubly linked list is O(1) so there's no real point in a heap, you just add at the end, take from the begining, and splice to the end on a hit.<br /><br />In a heap, you'd still have to splice out of the middle and reinsert it, which is not guaranteed to be cheap on a binary heap, and the major reason the array implementation is slow is because splice is an O(N) operation. It's probably faster on pointer based heap algorithms, but there's no real point since no comparison is necessary between elements, n insert the element is always at the end.nothingmuchhttps://www.blogger.com/profile/03975438115490089158noreply@blogger.comtag:blogger.com,1999:blog-876358347971598886.post-72562147962026777902010-07-03T11:35:30.712+03:002010-07-03T11:35:30.712+03:00Why not use heap for implementing LRU algorithm? ...Why not use heap for implementing LRU algorithm? Unless 'array' is really array implementation of heap?Jakub Narebskihttps://www.blogger.com/profile/11847202568800326989noreply@blogger.com