Re: [R] Dynamic Dictionary Data Type?

From: Kjetil Brinchmann Halvorsen <kjetil_at_acelerate.com>
Date: Fri 03 Jun 2005 - 05:02:09 EST

Duncan Murdoch wrote:

> Gabor Grothendieck wrote:
>
>> On 6/2/05, Prof Brian Ripley <ripley@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@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.

______________________________________________
R-help@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
Received on Fri Jun 03 05:11:24 2005

This archive was generated by hypermail 2.1.8 : Fri 03 Mar 2006 - 03:32:22 EST