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
