[Tutor] object representation

[Alan Gauld]

"spir" <denis.spir at gmail.com> wrote

> Does this mean that the associative arrays representing objects are
> implemented like python dicts, thus hash tables?

Yes, in fact I think they are Python dicts - although I've never actually
looked at the source to confirm that.

> I was wondering about the question because I guess the constraints
> are quite different:
> * Dict keys are of any type, including heterogeneous (mixed).
> Object keys are names, ie a subset of strings.

The keys must be immutable but ...
the object keys are a perfect subset of the generic dict.

> * Object keys are very stable, typically they hardly change;
> usually only values change. Dicts often are created empty and fed in a 
> loop.

The normal case is as you say but you can if you with create an empty
object and then later add attributes - in a loop if you wish.

> * Objects are small mappings: entries are explicitely written in code 
> (*).
> Dicts can be of any size, only limited by memory; they are often fed
> by computation.

But again the object usage is just a subset of the generic.

> * In addition, dict keys can be variables, while object keys rarely
> are: they are literal constants (*).

variables in Python are just names that efer to objects.
When you use a variable as a key to a dict you really use
the value of the variable.

>>> d = {}
>>> x = 42
>>> d[x] = 66
>>> d[42]
66
>>> d[x]
66
>>> x = 5
>>> d[x]
Traceback (most recent call last):
  File "<pyshell#12>", line 1, in <module>
    d[x]
KeyError: 5
>>>

It is the value of x that is the key not 'x'. If you change the value of x
it ceases to be a valid key of the dict.

> So, I guess the best implementations for objects and dicts may
> be quite different. i wonder about alternatives for objects,

They could be different and perhaps optimised but I don't think
they are. Pythons dicts are already pretty efficient. They form
the backbone of almost everything in Python not just objects.

> in particuliar trie and variants: http://en.wikipedia.org/wiki/Trie,
> because they are specialised for associative arrays which keys are 
> strings.

> PS: Would someone point me to typical hash funcs for string keys,
> and the one used in python?

Wikipedia for generic and the source for Python?

HTH,


-- 
Alan Gauld
Author of the Learn to Program web site
http://www.alan-g.me.uk/