[R] Dynamic Dictionary Data Type?

Kjetil Brinchmann Halvorsen kjetil at acelerate.com
Thu Jun 2 21:02:09 CEST 2005


Duncan Murdoch wrote:

> Gabor Grothendieck wrote:
>
>> On 6/2/05, Prof Brian Ripley <ripley at stats.ox.ac.uk> wrote:
>>
>>> On Thu, 2 Jun 2005, hadley wickham wrote:
>>>
>>>
>>>>> An environment is a hash table, and copying occurs only on 
>>>>> modification,
>>>>> when any language would have to copy in this context.
>>>>
>>>
>>> Caveat: the default is new.env(hash=FALSE), so an environment is a hash
>>> table in one sense but not necessarily so in the strict sense.
>>
>>
>>
>> Can you expand on this?  When would one use hash = TRUE vs.
>> the default?
>
>
> It's an optimization question.  hash = TRUE uses more memory and takes 
> longer to set up, but will give faster searches in big environments. 
> The current default assumes that environments are small so the effort 
> of building the hash table is not worthwhile, and it does linear 
> searches.
>
> I suspect that we might have the default wrong (or perhaps should make 
> the transition from linear to hash search automatically at a certain 
> threshold size), but I haven't done the testing necessary to show this.
>
> Duncan Murdoch
>
> ______________________________________________
> R-help at stat.math.ethz.ch mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide! 
> http://www.R-project.org/posting-guide.html
>
>
>
An example, with my example in a post some m inutes ago:

memo <- function(fun, hash) {
   mem <- new.env(hash=hash) 
   function(x) {
       if (exists(as.character(x), envir=mem)) get(as.character(x), 
envir=mem, inherits=FALSE) else {
       val <- fun(x)
       assign(as.character(x), value=val, envir=mem)
       val }
   }
}

 > fib1 <- memo( function(n) if(n<=1)1 else fib1(n-1)+fib1(n-2), TRUE)
 > fib2 <- memo( function(n) if(n<=1)1 else fib2(n-1)+fib2(n-2), FALSE)
 > system.time( fib1(400) )
[1] 0.06 0.00 1.06   NA   NA
 > system.time( fib2(400) )
[1] 0.00 0.00 1.44   NA   NA

Kjetil

-- 

Kjetil Halvorsen.

Peace is the most effective weapon of mass construction.
               --  Mahdi Elmandjra




-- 
No virus found in this outgoing message.
Checked by AVG Anti-Virus.




More information about the R-help mailing list