[R] beginner Q: hashtable or dictionary?
Prof Brian Ripley
ripley at stats.ox.ac.uk
Mon Jan 30 08:37:00 CET 2006
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
Brian D. Ripley, ripley at 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
More information about the R-help