- From: Andrew Fedoniouk <news@terrainformatica.com>
- Date: Thu, 24 Jul 2008 11:33:07 -0700
- To: Francois Remy <fremycompany_pub@yahoo.fr>
- CC: Boris Zbarsky <bzbarsky@MIT.EDU>, www-style list <www-style@w3.org>
Francois Remy wrote:
> > /* I don't have better solution if we must generalize in JScript */
> > setInterval(update, 500);
> >
> > (As far as I understand you think that there is a better
> > solution, right?)
> >
> > Your function update() {} has worst case complexity O(n*n).
> > You can *easily* hit the point when it will take more than 500ms
> > to execute. So UA will be busy crunching selectors most of the time.
> >
> > Cheers.
> >
> > --
> > Andrew Fedoniouk.
>
> Yes, there's another solution : you can watch change applied on the
> elements that can change the value of the rule.
> But it's not possible to know when an element changes in JScript...
Imagine that I you have some event that is fired when one of its
attributes, states or its subtree is getting changed.
(Lets put aside for the second when such an event needs to be fired)
How it will help you?
>
> -----------------------------
>
> No, it is'nt O(n*n).
It is not O(n*n), it is even worse, see below.
>
> imagine this case :
>
> <div id="base">
> <div class="el1">
> <a href="#"><b><span>First</span> link</b></a>
> <a href="#"><span>Second</span> link</a>
> </div>
> <div class="el2">
> <a href="#"><b><span>First</span> link</b></a>
> <a href="#"><span>Second</span> link</a>
> </div>
> </div>
>
> and this rule :
>
> div#base div.el1:with-child(a:hover b) span:hover { color: green; }
> -------------------------------
>
> The complexity of #base .el1 a:hover is O(n).
Agreed at this point.
> The rule need to be reevaluated each time :
> - (1) The elements matched by "div" change (any DIV can get or loose
> id="base")
> - (2) The elements matched by "div#base div" change (any DIV of
> div#base can get or loose class="el1")
> - (3) The elements matched by "div#base div.el1 span" change (any
> SPAN can get or loose :hover)
Each of this operations is by itself O(n) operation.
Complexity of this step is O(3*n).
So on *each DOM modification* you will run O(3*n) operation.
For each element found you need to check for $(#base .el1 a:hover).
Therefore total (worst case) is O(m*n*n) where 'm' is a number of simple
selectors of the complex selector.
>
> It's a O(n) complexity, you can trust me at this point.
I will.
--
Andrew Fedoniouk.
http://terrainformatica.com
Received on Thursday, 24 July 2008 18:33:59 UTC