Re: [R] beginner Q: hashtable or dictionary?

From: Prof Brian Ripley <ripley_at_stats.ox.ac.uk>
Date: Mon 30 Jan 2006 - 18:37:00 EST

On Sun, 29 Jan 2006, hadley wickham wrote:

>> use a 'list':
>
> Is a list O(1) for setting and getting?

Can you elaborate? R is a vector language, and normally you create a list in one pass, and you can retrieve multiple elements at once.

Retrieving elements by name from a long vector (including a list) is very fast, as an internal hash table is used. Does the following item from ONEWS answer your question?

     o	Indexing a vector by a character vector was slow if both the
 	vector and index were long (say 10,000).  Now hashing is used
 	and the time should be linear in the longer of the lengths
 	(but more memory is used).

Indexing by number is O(1) except where replacement causes the list vector to be copied. There is always the option to use match() to convert to numeric indexing.

-- 
Brian D. Ripley,                  ripley@stats.ox.ac.uk
Professor of Applied Statistics,  http://www.stats.ox.ac.uk/~ripley/
University of Oxford,             Tel:  +44 1865 272861 (self)
1 South Parks Road,                     +44 1865 272866 (PA)
Oxford OX1 3TG, UK                Fax:  +44 1865 272595

______________________________________________
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 Mon Jan 30 18:44:58 2006

This archive was generated by hypermail 2.1.8 : Fri 03 Mar 2006 - 03:42:14 EST