> Say there are 100 tiddlers tagged tagA and only 10 tagged tagB, and
> these are among some 1000 tiddlers tagged with other stuff. And
> "IsTagged<X>" is some generic function listing or identifying all
> tiddlers tagged with tag<X>
>
> Which is faster, if any;
>
> (IsTaggedA AND IsTaggedB) vs (IsTaggedB AND IsTaggedA)
> (IsTaggedA OR IsTaggedB) vs (IsTaggedB OR IsTaggedA)
>
> Is there any difference in evaluation speed?
Potentially, yes. Javascript boolean expressions are evaluated only
up to the point that a definitive true/false value can be calculated.
For example:
if (true || something)...
will not even evaluate 'something', since the initial 'true' value
makes the whole expression true, regardless of the value of
'something'. Similarly,
if (false && something)
does *not* evaluate 'something', as the initial 'false' value makes
the whole expression false, regardless of the value of 'something'.
In contrast,
if (true && something)
*does* evaluate 'something', as the value of the entire expression
cannot be determined without it.
Thus, using the following TW core functions as test terms:
store.getTiddler('A').isTagged('foo')
store.getTiddler('B').isTagged('bar')
1) store.getTiddler(...) is a very efficient retrieval because it uses
the tiddler name as a direct index into an 'associative array' of
tiddlers. Thus, the lookup to fetch the tiddler is a constant O(1).
[note: actually, it's more like O(n) - where 'n' is the number of
tiddlers - but that lookup is done by the browser's native JS engine
code, so it's vastly more efficient... and in terms of Javascript
programming, that lookup is an 'atomic operation' and can be treated
as O(1) for the purposes of discussion.
2) isTagged(...) is a TW-defined method for tiddler objects. It uses
a custom defined 'indexOf' prototype method for Array objects to
perform a linear lookup for a matching tag value. The lookup stops as
soon as a match is found. Assuming random distribution of matching
values in the tag array, a match would be found, on average, after
examining half of the tag values, so the lookup is O(n/2)
Thus, the total cost of checking
store.getTiddler('A').isTagged('foo')
is
O(1) * O(n/2) = O(n/2)
where 'n' is the number of tags on tiddler [[A]]
Thus, combined with the partial evaluation of booleans described
above, the potential variance in computational overhead depends
entirely on the number of tags on the tiddlers in question, rather
than the number of tiddlers itself.
If tiddler [[A]] has 10 tags and tiddler [[B]] has 100 tags, then:
store.getTiddler('A').isTagged('foo') || store.getTiddler('B').isTagged
('bar')
would be O(5) if 'foo' is a tag on [[A]], but O(5)+O(500) if 'foo' is
*not* a tag on [[A]].
In conclusion, always put the more efficient conditional expressions
first, to minimize the overhead... e.g. for (A||B), when A is true, B
is not evaluated, and for (A&&B), when A is false, B is not evaluated.
enjoy,
-e
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"TiddlyWikiDev" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/tiddlywikidev?hl=en
-~----------~----~----~----~------~----~------~--~---
