[Python-Dev] Type of range object members

[M.-A. Lemburg]

Martin v. Löwis wrote:
> Neal Norwitz schrieb:
>> I was playing around with a little patch to avoid that penalty.  It
>> doesn't take any additional memory, just a handful of bits we aren't
>> using. :-)
> 
> There are common schemes that allow constant-time issubclass tests,
> although they do require more memory:
> 
> 1. give each base class a small unique number, starting with 1
>    (0 means no number has been assigned). Give each class a bitmap
>    of all base classes, plus a field for the maximum-numbered
>    base class. Then,
> 
>    def issubclass(C, B):
>      return B.classnum and (B.classnum < C.maxbasenum) and\
>             bit_set(C.basenums, B.classnum)
> 
>    Supports multiple inheritance, space requirement linear
>    with the number of classes that are used as base classes.
>    Numbering should recycle class numbers when a class is
>    gced.
> 
> 2. restrict optimization to single-inheritance. Give each class
>    a "depth" (distance from object, 0 for object and
>    multiply-inherited classes). Also give each class an array
>    of bases, ordered by depth. Then,
> 
>    def issubclass(C, B):
>      if not C.depth: return expensive_issubclass(C, B)
>      return B.depth < C.depth and (C.bases[B.depth] is B)
> 
>    Space requirement is linear with the depth of the class
>    (but I think tp_mro could be used, if the formula is
>     changed to (C.bases[C.depth-B.depth] is B))

Two more:

3. Use a global cache of class objects that caches
   the issubclass() lookups.

   This is only amortized constant time, but easy to implement
   and has a few other nice features such as e.g. enabling
   traversal of the complete class inheritance forest (or tree
   if you just have new-style classes).

   Use weak references to the classes if you want to be
   able to GC them.

4. "Freeze" classes after they are constructed, meaning
   that all attributes from base-classes get bound to the
   inheriting class.

   This also speeds up method lookups considerably. Works
   great with classic classes, I'm not
   sure about new-style classes using e.g. staticmethods,
   slots and the like.

   mxTools has an implementation for classic classes called
   freeze().

   If you add special attributes such as ._issubclass_XYZ
   in the process, issubclass() would then be a single
   attribute lookup which is constant time.

-- 
Marc-Andre Lemburg
eGenix.com

Professional Python Services directly from the Source  (#1, Aug 16 2006)
>>> Python/Zope Consulting and Support ...        http://www.egenix.com/
>>> mxODBC.Zope.Database.Adapter ...             http://zope.egenix.com/
>>> mxODBC, mxDateTime, mxTextTools ...        http://python.egenix.com/
________________________________________________________________________

::: Try mxODBC.Zope.DA for Windows,Linux,Solaris,FreeBSD for free ! ::::