W3C home > Mailing lists > Public > www-style@w3.org > April 2007

Re: Select a parrent node with s CSS selector?

From: Andrew Fedoniouk <news@terrainformatica.com>
Date: Mon, 23 Apr 2007 19:42:16 -0700
Message-ID: <001301c7861a$2cda3c80$3501a8c0@TERRA>
To: "Ilia Goranov" <css-babailiica@babailiica.com>, <www-style@w3.org>, "Bruce Lawson" <bruce@brucelawson.co.uk>

  ----- Original Message ----- 
  From: Bruce Lawson 
  To: Andrew Fedoniouk ; Ilia Goranov ; www-style@w3.org 
  Sent: Monday, April 23, 2007 11:17 AM
  Subject: Re: Select a parrent node with s CSS selector?


    So to find style of p.description CSS engine will need to scan 
    1) all parents ( for body>div.content )  
    2) *and* all it is children ( for a:link )
     ...
    Your proposal changes the compelxity to O( n * n * m * d )  that is highly non-desirable as you may expect.

  Whilst I agree that it's far more complex to implement, does it mean that it's unimplementable and therefore beyond consideration?


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.  

Andrew Fedoniouk.
http://terrainformatica.com
Received on Tuesday, 24 April 2007 02:42:32 GMT

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