W3C home > Mailing lists > Public > www-style@w3.org > August 2006

Computational complexity of CSS selectors, part II, Was: Selector for parent/predecessor?

From: Andrew Fedoniouk <news@terrainformatica.com>
Date: Tue, 22 Aug 2006 12:13:42 -0700
Message-ID: <000701c6c61f$14f5d9a0$db02000a@internal.toppro.net>
To: <www-style@w3.org>

(See previous discussion on "Computational complexity of CSS" originated by 
[1] )

Brief explanation:
task of finding (resolving) all styles of elements in some document using
some stylesheet has computational complexity [2] expressed by the formula:

O ( n * m * d )

where:
n - number of elements in the DOM of the document
m - number of CSS selectors in style sheet.
d - depth of DOM tree ( if descendant combinators are used )

Problem of proposed parent/predecessor selectors is simple -
such selectors if they will be implemented (and used in some document)
will suddenly change this formula to

O ( n * n * m * d )

That is changing needed computational time in the order of
magnitude ( one more 'n' multiplier ) and will make such selectors
practically non-usable.

Yes, there are some optimizations/heuristics available [3] but
selectors of proposed type narrow that optimization field
proportionally - in the order of magnitude.

Andrew Fedoniouk.
http://terrainformatica.com

References:
1. http://lists.w3.org/Archives/Public/www-style/2005Nov/0072
2. http://en.wikipedia.org/wiki/Computational_complexity_theory
3. http://lists.w3.org/Archives/Public/www-style/2005Nov/0082 
Received on Tuesday, 22 August 2006 19:13:52 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 27 April 2009 13:54:46 GMT