Re: [css3-selectors] Grouping

Nikita Popov wrote:
> Am 09.01.2010 06:38, schrieb Andrew Fedoniouk:
>> Tab Atkins Jr. wrote:
>>> On Fri, Jan 8, 2010 at 10:49 PM, Andrew Fedoniouk
>>> <news@terrainformatica.com> wrote:
>>>> Boris Zbarsky wrote:
>>>>> On 1/8/10 12:33 PM, Nikita Popov wrote:
>>>>>> Which would lead to 3^4 = 81 rules. Hopefully nobody does it.
>>>>> Sure they will.  That's just life.
>>>>>

...

>>> It is similarly simple to say
>>>
>>> #publications.special :matches(input,select,textarea) {
>>>   //new rules
>>> }
>>>
>>> With the same effect.
>>>
>>
>> No. Effect is not the same. For each of 1000 DOM elements you should
>> execute at least following check:
>>
>>   if( element.tag == input ||
>>       element.tag == select ||
>>       element.tag == textarea )
>>
>> So in total at least 3000 checks by introducing just one (as author 
>> will think) CSS rule. Yes, element.tag == input is a cheap operation 
>> but still it should be made.
> And now it gets really wrong. If the rendering engines would really do 
> that, oh my god!

They do so you can start to pray already.

> Sure enough the rendering engines would first jump to the ID 
> #publications (which is fast, cause it's a lookup, not a loop), check 
> that the class is .special (again a lookup, therefore fast) ans only 
> then check for one of the children being a form-interaction-element. So, 
> not 3000 checks, but only 302, as many as with your @set-variant!
> 

You are wrong in your assumptions of how all this work.

You have defined very non-effective schema of matching CSS selectors 
that has complexity of O(N*N) (see:[1]) at least.

For testing any given DOM element for the selector:

.parent .child { ... }

following steps should be made:

1) check if the element has .child class. If no -> exit(false).
    That is O(1) operation.
2) check if it has parent element that has .parent class defined. If no 
-> exit(false).
    That is O(D) operation. D here is a depth of the DOM tree.

So the whole task is of O(N*D) complexity. N here is a number of DOM 
elements. No matter how many descendant groups in the selectors.

E.g. this selector:
   .super-parent .parent .child { ... }
has also complexity O(N*D)

And in the way you suspect how it works:

1) Find .parent DOM element - O(N) operation.
2) Find .child DOM element inside it - O(N) operation.
In total: O(N*N)

And for the selector:
   .super-parent .parent .child { ... }
complexity in your case will be: O(N*N*N).

[1] http://en.wikipedia.org/wiki/Big_O_notation

-- 
Andrew Fedoniouk.

http://terrainformatica.com

Received on Saturday, 9 January 2010 20:20:16 UTC