- From: Allan Sandfeld Jensen <kde@carewolf.com>
- Date: Tue, 24 Apr 2007 18:13:40 +0200
- To: www-style@w3.org
On Tuesday 24 April 2007 04:42, Andrew Fedoniouk wrote: > > This is not about complexity of implementation but about computational > complexity of algorithm needed to calculate such a selector: > > See: http://en.wikipedia.org/wiki/Computational_complexity_theory > > For example proposed selector > > * < *:link /* element that has at least one link inside */ > > requires deep scan of all children of any given element to verify the > selector. > > Formula O( n * n ) means that document having twice more > elements will require four times more time to match selectors. > (In practice this can be lot less - this is just a worst case - but still) > > Again it is possible to compute this but selectors that have exponential > nature are *highly* non-desirable. > O(n*n) is quadratic not exponential, and many CSS implementations are worst case quadratic anyway. And no, it can still be done in linear time O(n) using a standard NFA to DFA conversion (consider the CSS selectors a collection of NFA rules). The problem is that it can't be done conclusively for all cases until the entire document has been parsed. This either makes the page keep changing style while loading and parsing, or delays the display until end of page-load. CSS has been designed to be applied incrementally (expect for a few odd CSS3 selectors). That said there have been suggestions on this list that could be applied better incrementally and achieve many of the same effects, and there is also the idea to just allow the web authors shoot themselves in the foot if they use the parent selector on BODY (worse case scenario). `Allan
Received on Tuesday, 24 April 2007 16:13:53 UTC