- From: Andrew Fedoniouk <news@terrainformatica.com>
- Date: Tue, 22 Aug 2006 12:13:42 -0700
- 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 UTC