[Tutor] dictionary speeds?

[Magnus Lycka]

At 23:35 2002-08-29 +1200, Thomi Richards wrote:
>OK, i want to have a very complex dictionary structure, where the key is
>an ordinary old word, like "lion", but the value side is a tuple, which
>has other tuples nested inside it. it could have many thousand tuples
>inside it at once, and these need to be used frequently. My question is:
>
>how fast is the dictionary? would it slow down any data types _inside_
>it? would it be faster to have a dictionary which has the word on the
>right, and an index number on the left??
>
>I'm looking for speed here, its very important for this project.

Dictionaries are fast. AFAIK look-up time is more or less constant
regardless of dictionary size. (Assuming you fit in the RAM and
don't start swapping of course.)

The values are not stored inside the dictionary. The dictionary just
contains pointers to the locations in memory. Look at this example:

 >>> parrot =3D (1,2,3)
 >>> larch =3D (parrot,4,5,6)
 >>> kilimanjaro =3D {'tree' : larch}
 >>> ronObvious =3D kilimanjaro['tree']

larch, ronObvious and kilimanjaro['tree'] will now all refer to
the same object, a tuple containing ((1,2,3),4,5,6). It's not
stored in a dict or in a variable. It's an object, and it's
stored in the part of the compters memory called the heap.
In my particular case it's stored at memory location 22837480
but that not very interesting...

 >>> id(larch)
22837480
 >>> id(ronObvious)
22837480
 >>> id(kilimanjaro['tree'])
22837480

This memory location the contains a tuple, which is basically
four pointers, pointing out the locations of the four objects
in it (the tuple with (1,2,3) and the three integers 4, 5 and 6.

 >>> id(larch[0]) # the tuple (1,2,3)
22778384
 >>> id(parrot) # same tuple
22778384
 >>> id(larch[1]) # integer 4
3439804
 >>> id(larch[2]) # integer 5
3439600
 >>> id(larch[3]) # integer 6
3439588

Further, python is capable of interning simple objects like integers,
i.e. it will reuse immutable objects that are already used.

 >>> x =3D 6
 >>> id(x)
3439588

But as you see:

 >>> y =3D (1,2,3)
 >>> id(y)
22866432

it wasn't clever enough to reuse the tuple at 22778384 though...
(In theory it could have done that, since tuples can't change
once they are created, i.e. they are immutable.)


--=20
Magnus Lyck=E5, Thinkware AB
=C4lvans v=E4g 99, SE-907 50 UME=C5
tel: 070-582 80 65, fax: 070-612 80 65
http://www.thinkware.se/  mailto:magnus@thinkware.se