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 ! :::: _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
