[Zope-CMF] Re: CatalogTool: validity check extremely inefficient
Tres Seaver
tseaver at zope.com
Sat Jun 26 07:34:24 EDT 2004
Andreas Jung wrote:
> I am sure you are having a patch :-)
DateRangeIndex is designed for this particular query.
> Andreas
>
> --On Freitag, 25. Juni 2004 22:25 Uhr +0200 Dieter Maurer
> <dieter at handshake.de> wrote:
>
>> Today, I have analysed why CatalogTool searches take an incredible
>> long time. The "validity" check ("effective <= now <= expires")
>> turned out to be the culprit: more precisely: the "effective <= now"
>> part.
>>
>> The reason: "Unindex.Unindex._apply_index" uses successive
>> "union"s to combine the document lists for the individual
>> terms in the range. This algorithm has quadratic runtime
>> behaviour in the number of terms!
>> Instead, it should use "multiunion" which has linear runtime
>> in the number of terms!
>>
>>
>> To demonstrate the difference run the following script.
>> The "multiunion" variant is orders of magnitude faster
>> than the current implementation for portals with several
>> ten thousand objects...
>>
>>
>> from time import time
>> from BTrees.IIBTree import IITreeSet, union, multiunion
>> from random import randint
>>
>> def u(n):
>> s=time()
>> r = None
>> for i in range(n): r = union(r,l[i])
>> print 'union', n, time() - s
>>
>> def m(n):
>> sl = l[:n]
>> s=time()
>> multiunion(sl)
>> print 'multiunion', n, time()-s
>>
>> l = [IITreeSet([randint(0,1<<30)]) for i in range(20000)]
>>
>> # 5.000 terms
>> u(5000)
>> # 0.647865056992
>> m(5000)
>>
>> # 10.000 terms
>> # 0.00777697563171
>> u(10000)
>> # 2.45900988579
>> m(10000)
>> # 0.0156350135803
>>
>> # 20.000 terms
>> u(20000)
>> # 9.70094203949
>> m(20000)
>> # 0.0316338539124
>>
>>
>> --
>> Dieter
>
>
>
>
>
> _______________________________________________
> Zope-CMF maillist - Zope-CMF at zope.org
> http://mail.zope.org/mailman/listinfo/zope-cmf
>
> See http://collector.zope.org/CMF for bug reports and feature requests
>
--
===============================================================
Tres Seaver tseaver at zope.com
Zope Corporation "Zope Dealers" http://www.zope.com
More information about the Zope-CMF
mailing list