beginner Q: hashtable or dictionary?

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

beginner Q: hashtable or dictionary?

context grey
Hi,

Is there something like a hashtable or (python)
dictionary in R/Splus?

(If not, is there a reason why it's not needed /
typical way to accomplish the same thing?)

Thank you

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: beginner Q: hashtable or dictionary?

jholtman
use a 'list':


> x <- list()
> x[['test']] <- 64
> x[['next one']] <- c(1,2,3,4)
> x
$test
[1] 64

$"next one"
[1] 1 2 3 4

> x[['test']]
[1] 64
>



On 1/29/06, context grey <[hidden email]> wrote:

>
> Hi,
>
> Is there something like a hashtable or (python)
> dictionary in R/Splus?
>
> (If not, is there a reason why it's not needed /
> typical way to accomplish the same thing?)
>
> Thank you
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide!
> http://www.R-project.org/posting-guide.html
>



--
Jim Holtman
Cincinnati, OH
+1 513 247 0281

What the problem you are trying to solve?

        [[alternative HTML version deleted]]

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: beginner Q: hashtable or dictionary?

Christos Hatzis
I was wondering if there is an easy way to extend this to implement a 2-D
hash, i.e. 2-way indexing?

> x[["a"]][["b"]] <- "something"

Thanks.

Christos Hatzis

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of jim holtman
Sent: Sunday, January 29, 2006 8:39 PM
To: context grey
Cc: [hidden email]
Subject: Re: [R] beginner Q: hashtable or dictionary?

use a 'list':


> x <- list()
> x[['test']] <- 64
> x[['next one']] <- c(1,2,3,4)
> x
$test
[1] 64

$"next one"
[1] 1 2 3 4

> x[['test']]
[1] 64
>



On 1/29/06, context grey <[hidden email]> wrote:

>
> Hi,
>
> Is there something like a hashtable or (python) dictionary in R/Splus?
>
> (If not, is there a reason why it's not needed / typical way to
> accomplish the same thing?)
>
> Thank you
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide!
> http://www.R-project.org/posting-guide.html
>



--
Jim Holtman
Cincinnati, OH
+1 513 247 0281

What the problem you are trying to solve?

        [[alternative HTML version deleted]]

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide!
http://www.R-project.org/posting-guide.html

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: beginner Q: hashtable or dictionary?

Gabor Grothendieck
Make a list of lists:

L <- list(a = list(a = 1, b = 2), b = list(a = 3, b = 4))
L[["a"]][["b"]]
L$a$b

On 1/29/06, Christos Hatzis <[hidden email]> wrote:

> I was wondering if there is an easy way to extend this to implement a 2-D
> hash, i.e. 2-way indexing?
>
> > x[["a"]][["b"]] <- "something"
>
> Thanks.
>
> Christos Hatzis
>
> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of jim holtman
> Sent: Sunday, January 29, 2006 8:39 PM
> To: context grey
> Cc: [hidden email]
> Subject: Re: [R] beginner Q: hashtable or dictionary?
>
> use a 'list':
>
>
> > x <- list()
> > x[['test']] <- 64
> > x[['next one']] <- c(1,2,3,4)
> > x
> $test
> [1] 64
>
> $"next one"
> [1] 1 2 3 4
>
> > x[['test']]
> [1] 64
> >
>
>
>
> On 1/29/06, context grey <[hidden email]> wrote:
> >
> > Hi,
> >
> > Is there something like a hashtable or (python) dictionary in R/Splus?
> >
> > (If not, is there a reason why it's not needed / typical way to
> > accomplish the same thing?)
> >
> > Thank you
> >
> > ______________________________________________
> > [hidden email] mailing list
> > https://stat.ethz.ch/mailman/listinfo/r-help
> > PLEASE do read the posting guide!
> > http://www.R-project.org/posting-guide.html
> >
>
>
>
> --
> Jim Holtman
> Cincinnati, OH
> +1 513 247 0281
>
> What the problem you are trying to solve?
>
>        [[alternative HTML version deleted]]
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide!
> http://www.R-project.org/posting-guide.html
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
>

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: beginner Q: hashtable or dictionary?

hadley wickham
In reply to this post by jholtman
> use a 'list':

Is a list O(1) for setting and getting?

Hadley

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: beginner Q: hashtable or dictionary?

Gabor Grothendieck
In reply to this post by Gabor Grothendieck
One could also use a matrix if appropriate:

> m <- matrix(1:4, 2, dimnames = list(c("a", "b"), c("a", "b")))
> m["a", "b"]
[1] 3

Also in the 1d case one could do this:

v <- c(a = 1, b = 2)
v[["a"]]

On 1/29/06, Gabor Grothendieck <[hidden email]> wrote:

> Make a list of lists:
>
> L <- list(a = list(a = 1, b = 2), b = list(a = 3, b = 4))
> L[["a"]][["b"]]
> L$a$b
>
> On 1/29/06, Christos Hatzis <[hidden email]> wrote:
> > I was wondering if there is an easy way to extend this to implement a 2-D
> > hash, i.e. 2-way indexing?
> >
> > > x[["a"]][["b"]] <- "something"
> >
> > Thanks.
> >
> > Christos Hatzis
> >
> > -----Original Message-----
> > From: [hidden email]
> > [mailto:[hidden email]] On Behalf Of jim holtman
> > Sent: Sunday, January 29, 2006 8:39 PM
> > To: context grey
> > Cc: [hidden email]
> > Subject: Re: [R] beginner Q: hashtable or dictionary?
> >
> > use a 'list':
> >
> >
> > > x <- list()
> > > x[['test']] <- 64
> > > x[['next one']] <- c(1,2,3,4)
> > > x
> > $test
> > [1] 64
> >
> > $"next one"
> > [1] 1 2 3 4
> >
> > > x[['test']]
> > [1] 64
> > >
> >
> >
> >
> > On 1/29/06, context grey <[hidden email]> wrote:
> > >
> > > Hi,
> > >
> > > Is there something like a hashtable or (python) dictionary in R/Splus?
> > >
> > > (If not, is there a reason why it's not needed / typical way to
> > > accomplish the same thing?)
> > >
> > > Thank you
> > >
> > > ______________________________________________
> > > [hidden email] mailing list
> > > https://stat.ethz.ch/mailman/listinfo/r-help
> > > PLEASE do read the posting guide!
> > > http://www.R-project.org/posting-guide.html
> > >
> >
> >
> >
> > --
> > Jim Holtman
> > Cincinnati, OH
> > +1 513 247 0281
> >
> > What the problem you are trying to solve?
> >
> >        [[alternative HTML version deleted]]
> >
> > ______________________________________________
> > [hidden email] mailing list
> > https://stat.ethz.ch/mailman/listinfo/r-help
> > PLEASE do read the posting guide!
> > http://www.R-project.org/posting-guide.html
> >
> > ______________________________________________
> > [hidden email] mailing list
> > https://stat.ethz.ch/mailman/listinfo/r-help
> > PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
> >
>

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: beginner Q: hashtable or dictionary?

Brian Ripley
In reply to this post by hadley wickham
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,                  [hidden email]
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

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: beginner Q: hashtable or dictionary?

Seth Falcon-2
In reply to this post by jholtman
> On 1/29/06, context grey <[hidden email]> wrote:
>>
>> Hi,
>>
>> Is there something like a hashtable or (python)
>> dictionary in R/Splus?

On 29 Jan 2006, [hidden email] wrote:
> use a 'list':

Most of the time, a list will be what you want, but it has some
important differences from a Python dictionary.  In particular, one
can end up with duplicate keys.  Here is an example:

    h <- list()
    h[["foo"]] <- 1
    h[[2]] <- 2
    names(h) <- rep("foo", 2)
    h
      $foo
      [1] 1
     
      $foo
      [1] 2
   
    h[["foo"]]
      [1] 1

'environments' may be what you are looking for, see help for new.env().

    h <- new.env(hash=TRUE)

An important thing to keep in mind with environments, however, is that
they are an exception to the pass by value semantics of the language.
Environments are not copied when passed as function args.  This has
its uses, but can be confusing.


+ seth

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: beginner Q: hashtable or dictionary?

hadley wickham
In reply to this post by Brian Ripley
> > 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.

When you use a hash table you expect it to be O(1) (on average) for
getting and setting values (conditional on having a good hash
function, a large enough table etc...).  (and thanks for the pointer
to that RNEWS item)

> 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.

I read this to mean that setting a value in list will be O(n) (where n
is the length of the new list) - If you blindly expect a list to act
like a hash table you will be badly surprised.  If you are copying an
algorithm from another language, you will probably need to rethink the
way that updates work.  If however, you just want an object that can
be indexed by a string, then a list will be fine.

Regards,

Hadley

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: beginner Q: hashtable or dictionary?

Duncan Murdoch
In reply to this post by Seth Falcon-2
On 1/30/2006 9:55 AM, Seth Falcon wrote:

>> On 1/29/06, context grey <[hidden email]> wrote:
>>>
>>> Hi,
>>>
>>> Is there something like a hashtable or (python)
>>> dictionary in R/Splus?
>
> On 29 Jan 2006, [hidden email] wrote:
>> use a 'list':
>
> Most of the time, a list will be what you want, but it has some
> important differences from a Python dictionary.  In particular, one
> can end up with duplicate keys.  Here is an example:
>
>     h <- list()
>     h[["foo"]] <- 1
>     h[[2]] <- 2
>     names(h) <- rep("foo", 2)
>     h
>       $foo
>       [1] 1
>      
>       $foo
>       [1] 2
>    
>     h[["foo"]]
>       [1] 1
>
> 'environments' may be what you are looking for, see help for new.env().
>
>     h <- new.env(hash=TRUE)
>
> An important thing to keep in mind with environments, however, is that
> they are an exception to the pass by value semantics of the language.
> Environments are not copied when passed as function args.  This has
> its uses, but can be confusing.

Both lists and environments have other oddities, too.  For example,
"mean" would be found in your environment above by functions like get(),
since the base environment is its parent; "f" would be found in your
list, since partial name matching is used in lists.  You can avoid the
parent problem in R 2.2.x+ by setting the parent explicitly to emptyenv().

Duncan Murdoch

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: beginner Q: hashtable or dictionary?

Patrick Burns
In reply to this post by hadley wickham
hadley wickham wrote:

> I read this to mean that setting a value in list will be O(n) (where n
>
>is the length of the new list) - If you blindly expect a list to act
>like a hash table you will be badly surprised.  If you are copying an
>algorithm from another language, you will probably need to rethink the
>way that updates work.  If however, you just want an object that can
>be indexed by a string, then a list will be fine.
>

I would think that when translating from another language,
it is best to write it in R in the simplest way, which probably
means using a list.  Then if it turns out to be too slow, try doing
something fancy.  I suspect that speed improvements are
seldom necessary -- I can't believe how fast most computations
are these days.

I don't see that worrying about O(1) versus O(n) is likely to
get you very far.  Just try it out on a normal size problem,
and try it out on a very large problem and see if it is good
enough.


Patrick Burns
[hidden email]
+44 (0)20 8525 0696
http://www.burns-stat.com
(home of S Poetry and "A Guide for the Unwilling S User")

>
>
>
>  
>

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: beginner Q: hashtable or dictionary?

hadley wickham
> I would think that when translating from another language,
> it is best to write it in R in the simplest way, which probably
> means using a list.  Then if it turns out to be too slow, try doing
> something fancy.  I suspect that speed improvements are
> seldom necessary -- I can't believe how fast most computations
> are these days.

I totally agree.  However, if you are implementing an algorithm that
is O(n^2) when using a hash table that has O(1) updates, it is likely
to be at least O(n^3) when using a list with O(n) updates.  And
sometimes speed does matter!  (Although not as often as most people
think, and, of course, beware premature optimisation.)

Hadley

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: beginner Q: hashtable or dictionary?

Warnes, Gregory R
In reply to this post by context grey

Standard R vectors and list elements can given names, and can be accessed by them.  This allows them to be used like the dictionaries or hashes of other languages.

For example

>  x = c("a"=1, "b"=2, "c"=3)
>  x["a"]
a
1
> x["foo"] = "bar"
> x["foo"]
  foo
"bar"
> x
    a     b     c   foo
  "1"   "2"   "3" "bar"

-Greg

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of context grey
> Sent: Sunday, January 29, 2006 8:35 PM
> To: [hidden email]
> Subject: [R] beginner Q: hashtable or dictionary?
>
>
> Hi,
>
> Is there something like a hashtable or (python)
> dictionary in R/Splus?
>
> (If not, is there a reason why it's not needed /
> typical way to accomplish the same thing?)
>
> Thank you
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide!
> http://www.R-project.org/posting-guide.html
>
----------------------------------------------------------------------
LEGAL NOTICE\ Unless expressly stated otherwise, this messag...{{dropped}}

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html