I like to announce a tiny utility I did for my last project. It is only a single class that basically works like LRUCache internally but on the outside it is more like a dictionary. And it has no factory block.
If you don't know LRUCache, it's a fixed size dictionary that sorts its elements by usage in a "Least Recently Used" fashion. Meaning the last used element is put in front and the least used at the end. Elements get discarded at the end if space is full. Apart from #at: that is provided by LRUCache , LRUDictionary implements to following methods at:ifAbsent: at:ifAbsentPut: at:ifPresent: at:put: removeAt: removeKey: removeKey:ifAbsent It is available here MCHttpRepository location: 'http://source.selfish.org/mc/misc' user: '' password: '' Blog article is here http://norbert.hartl.name/blog/lrudictionary/ hope you like it, Norbert |
I always forget to move stuff. I moved it to squeaksource
http://ss3.gemstone.com/ss/lrudictionary.html Norbert Am 11.05.2012 um 14:51 schrieb Norbert Hartl: > I like to announce a tiny utility I did for my last project. It is only a single class that basically works like LRUCache internally but on the outside it is more like a dictionary. And it has no factory block. > > If you don't know LRUCache, it's a fixed size dictionary that sorts its elements by usage in a "Least Recently Used" fashion. Meaning the last used element is put in front and the least used at the end. Elements get discarded at the end if space is full. > > Apart from #at: that is provided by LRUCache , LRUDictionary implements to following methods > > at:ifAbsent: > at:ifAbsentPut: > at:ifPresent: > at:put: > removeAt: > removeKey: > removeKey:ifAbsent > > It is available here > > MCHttpRepository > location: 'http://source.selfish.org/mc/misc' > user: '' > password: '' > > Blog article is here > > http://norbert.hartl.name/blog/lrudictionary/ > > hope you like it, > > Norbert |
In reply to this post by NorbertHartl
Hi Norbert,
On 11 May 2012, at 14:51, Norbert Hartl wrote: > I like to announce a tiny utility I did for my last project. It is only a single class that basically works like LRUCache internally but on the outside it is more like a dictionary. And it has no factory block. > > If you don't know LRUCache, it's a fixed size dictionary that sorts its elements by usage in a "Least Recently Used" fashion. Meaning the last used element is put in front and the least used at the end. Elements get discarded at the end if space is full. > > Apart from #at: that is provided by LRUCache , LRUDictionary implements to following methods > > at:ifAbsent: > at:ifAbsentPut: > at:ifPresent: > at:put: > removeAt: > removeKey: > removeKey:ifAbsent > > It is available here > > MCHttpRepository > location: 'http://source.selfish.org/mc/misc' > user: '' > password: '' > > Blog article is here > > http://norbert.hartl.name/blog/lrudictionary/ > > hope you like it, > > Norbert This code strikes me as less than optimal: putInFront: anObject fromIndex: aNumber values replaceFrom: 2 to: aNumber with: (values first: aNumber - 1). values at: 1 put: anObject. ^ anObject #first: does a copy no ? #replaceFrom:to:with:startingAt: can do in place shifting, if you are careful. I would also optimize for the case when the object is already in front. But even then, all this shifting on each #at: access is a bit costly for a cache, no ? The alternative, working with timestamps is also not that elegant and maybe also not faster. Did you consider it ? Compare performance ? Sven |
Am 11.05.2012 um 16:48 schrieb Sven Van Caekenberghe: > Hi Norbert, > > On 11 May 2012, at 14:51, Norbert Hartl wrote: > >> I like to announce a tiny utility I did for my last project. It is only a single class that basically works like LRUCache internally but on the outside it is more like a dictionary. And it has no factory block. >> >> If you don't know LRUCache, it's a fixed size dictionary that sorts its elements by usage in a "Least Recently Used" fashion. Meaning the last used element is put in front and the least used at the end. Elements get discarded at the end if space is full. >> >> Apart from #at: that is provided by LRUCache , LRUDictionary implements to following methods >> >> at:ifAbsent: >> at:ifAbsentPut: >> at:ifPresent: >> at:put: >> removeAt: >> removeKey: >> removeKey:ifAbsent >> >> It is available here >> >> MCHttpRepository >> location: 'http://source.selfish.org/mc/misc' >> user: '' >> password: '' >> >> Blog article is here >> >> http://norbert.hartl.name/blog/lrudictionary/ >> >> hope you like it, >> >> Norbert > > This code strikes me as less than optimal: > > putInFront: anObject fromIndex: aNumber > values > replaceFrom: 2 > to: aNumber > with: (values first: aNumber - 1). > values at: 1 put: anObject. > ^ anObject > > #first: does a copy no ? > > #replaceFrom:to:with:startingAt: can do in place shifting, if you are careful. > I would also optimize for the case when the object is already in front. Sven, to be honest I didn't think about it. The part you are mentioning I took straight from LRUCache without doubting its usefulness. Everything you say makes sense to me. But I need to think first before saying anything useful :) > > But even then, all this shifting on each #at: access is a bit costly for a cache, no ? > The alternative, working with timestamps is also not that elegant and maybe also not faster. > Did you consider it ? Compare performance ? Of course the shifting is costly. I use it as a cache for outoging rest calls that does http and deserializes data. From that point of view it's no question. It accelerates immensly and the costs are leveraged easily. The timestamp approach needs to be tested. But I think you are right. It sounds much better to have to scan the array if an old element has to be removed instead of every access. Norbert |
Free forum by Nabble | Edit this page |