[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: Re: Keeping a running total?
> What about having a bigger than 2 (variable) number of quotas? How > would your solution change to tackle this? > I suppose a general solution would have a list of quotas (and a corresponding list of quota names), e.g. : <quotas> <quota id="Widget" left="{$Widget_quota}" /> <quota id="Gadget" left="{$Gadget_quota}" /> ... </quotas> Updating this list on every template call leads to O(Qn)*O(Fn) time complexity, where Fn is the number of factories and Qn the number of quotas. In the general case this is quite similar to quadratic time complexity.
Having to perform such shifts on template calls again leads to quadratic-like time complexity. Better time complexity can be achieved if the running totals for *both* factories and quotas are calculated with an O(N) (linear) algorithm. The implementation I provided could have better than quadratic time complexity if it used a more efficient way to find overlapping intervals -- a binary search with an f:binSearch() - like function would be O(Log2(Qn)). In this case the time complexity would be: O(Fn)*O(Log2(Qn)) For simplicity, in the implementation I provided the identification of overlapping intervals traverses all quotas intervals for every factory. -- Cheers, Dimitre Novatchev --------------------------------------- Truly great madness cannot be achieved without significant intelligence.
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|