"logo.gif"  
Main
Read Online
Download PDF
Additional resources
Revision history
Known typos/bugs
Report a bug
License terms
About the author
"node355_1.gif" "node355_2.gif" "node355_3.gif"

4.2.5.4      Efficiency issues

There are many other non-trivial examples of this technique. However, often it turns out to be not the most efficient one, since it is quite easy to build inefficient rules and patterns. For instance, our first example with list sorting has a terrible performance and is completely impractical for any realistic sizes of a list, since the pattern-matcher needs roughly linear (in the list size) time to find a first match for exchange, and then it only does a single exchange and starts all over! The number of exchanges needed is of the order of the square of the list size, and thus we conclude that our realization has roughly cubic complexity.

Let us do some performance measurements:

"node355_4.gif"

This is the rule we need :

"node355_5.gif"

"node355_6.gif"

"node355_7.gif"

"node355_8.gif"

"node355_9.gif"

"node355_10.gif"

"node355_11.gif"

"node355_12.gif"

These timing results confirm our expectations. While this shows that our rule - based realization is completely inefficient since it adds another power of the list size to the standard complexity of the exchange sort algorithm, it is a good news that we can understand why this happens. Because it turns out that in many cases, the structures on which patterns are tried plus patterns themselves can be organized in such a way that the pattern is usually matched very soon after the beginning. In fact, as was demonstrated for instance by David Wagner in his book [7] in the context of the mergesort algorithm, this technique allows to make the rule-based solution the most efficient of all.

So, to put it simple: organize your data such as to ensure that the pattern matcher wastes as little time on a-priory doomed matching attempts as possible, and you will get an efficient rule-based solution.

"node355_13.gif" "node355_14.gif" "node355_15.gif"

Created by Wolfram Mathematica 6.0  (05 February 2009) Valid XHTML 1.1!