Re: Computational complexity of CSS

Andrew Fedoniouk schreef:
> Is anybody looking in this direction or you think this problem is a 
> bit artificial?

Yeah, user agents can (and do) optimize CSS checking already.

For example, # selectors can be optimised using hash tables, selectors 
which resemble partially can be grouped, etcetera. There are also cases 
when certain types of selectors aren’t present (like anything dynamic 
such as :hover), the methods can be simplified. I’ve seen a number of 
bugs along these lines in Mozilla, but I don’t think I’ll be able to 
find them again, maybe someone else knows.

I’d say that with techniques like that, and tree-based lookup methods, 
the ‘match’ method can be reduced to logarithmic time or less, so that 
would give a time of O(N log M) which is already much better.

Changing the syntax of CSS will not make things any easier. Any 
structure optimisations such as you suggest in another reply can easily 
be done internally by the browser (although I agree such functionality 
would be good to have, but for a different reason :)).

Also, the 1000 elements are not added simultaneously when the page is 
loaded incrementally, and if there are dynamic changes, only the element 
itself and in some cases its neighbours need to be re-evaluated.


~Grauw

-- 
Ushiko-san! Kimi wa doushite, Ushiko-san!!
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Laurens Holst, student, university of Utrecht, the Netherlands.
Website: www.grauw.nl. Backbase employee; www.backbase.com.

Received on Wednesday, 16 November 2005 22:38:48 UTC