[Python-Dev] Type of range object members (original) (raw)

M.-A. Lemburg mal at egenix.com
Thu Aug 17 00:01:23 CEST 2006

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_ bitset(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 expensiveissubclass(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 tpmro could be used, if the formula is changed to (C.bases[C.depth-B.depth] is B))

Two more:

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

  2. "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 ! ::::

More information about the Python-Dev mailing list