Re: [xsl] Re: Keeping a running total?

["Dimitre Novatchev" <dnovatchev@xxxxxxxxx>]

> > So, how many times will parameter shift be required?
>
>
> Parameter shift will occur whenever a factory's capacity is used up (Fn
> times)

So we have Fn shifts of parameters. Every shift of parameters takes
O(Qn) -because every parameter takes the velue of the next parameter.

Therefore, the time only the shift of parameters will require will be
     Fn * O(Qn)

which, of course can be written as:

 O(Fn) * O(Qn).

This was my initial estimation and you now confirm it.

A better time complexity can be achieved if the "shift parameters"
operation can be replaced with something else.


--
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.




On 7/15/06, Andrew Franz <afranz0@xxxxxxxxxxxxxxxx> wrote:
> Dimitre Novatchev wrote:
>
> >> > Having to perform such shifts on template calls again leads to
> >> > quadratic-like time complexity.
> >>
> >>
> >> This is not correct.
> >>
> >> A template call will occur in 2 cases:
> >> 1. quota < capacity, in which case quota is consumed and quotas are
> >> shifted
> >> 2. capacity < quota, in which case you shift to the next factory
> >>
> >> Order(Qn) + Order(Fn)
> >>
> >> Like I said, "It is O(N) because it monotonically advances through both
> >> lists (factories and quotas) without backtracking"
> >>
> >
> >
> > So, how many times will parameter shift be required?
>
>
> Parameter shift will occur whenever a factory's capacity is used up (Fn
> times)
>
> 1. At any instant, you're comparing the head of the factory list with
> the head of the quota list.
> 2. For each comparison, either the quota list will advance (shift
> parameters) or the factory list will advance.(successor axis)
>
> Number of operations = O(Qn)+O(Fn)
>
> Is it usual to talk of O(n) with respect to an implementation, or should
> the term apply strictly to an algorithm?
>
>
> >
> >
> > Cheers,
> > Dimitre Novatchev
> >
> >
> >
> > On 7/14/06, Andrew Franz <afranz0@xxxxxxxxxxxxxxxx> wrote:
> >
> >> Dimitre Novatchev wrote:
> >>
> >> >> > 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.
> >> >
> >> >
> >> >>
> >> >>
> >> >> In the past I've 'cheated' by using the stack as a list, e.g. as
> >> >> follows:
> >> >>
> >> >> <xsl:template match="xml">
> >> >>   <xsl:apply-templates select="factory">
> >> >>       <xsl:with-param name="left0" select="$Widget_quota" />
> >> >>       <xsl:with-param name="left1" select="$Gadget_quota" />
> >> >>       ...
> >> >>       <xsl:with-param name="name0">Widget</xsl:with-param>
> >> >>       <xsl:with-param name="name1">Gadget</xsl:with-param>
> >> >>       ...
> >> >>   </xsl:apply-templates>
> >> >> </xsl:template>
> >> >>
> >> >> then in the factory template, each factory would consume $left0
> >> until it
> >> >> was depleted and then shift by assigning $left1 to $left0, $left2 to
> >> >> $left1 and so on through parameters.
> >> >> e.g.
> >> >>        <xsl:with-param name="left0" select="$left1" />   <!--
> >> shift to
> >> >> next quota -->
> >> >>        <xsl:with-param name="left1" select="$left2" />
> >> >>        <xsl:with-param name="left2" select="$left3" />
> >> >>        <xsl:with-param name="left3" select="$left4" />
> >> >>
> >> >> Quota-recursion would end when $left0 was empty then capacity would
> >> >> accumulate in $excess until factories were depleted.
> >> >
> >> >
> >> >
> >> > Having to perform such shifts on template calls again leads to
> >> > quadratic-like time complexity.
> >>
> >>
> >> This is not correct.
> >>
> >> A template call will occur in 2 cases:
> >> 1. quota < capacity, in which case quota is consumed and quotas are
> >> shifted
> >> 2. capacity < quota, in which case you shift to the next factory
> >>
> >> Order(Qn) + Order(Fn)
> >>
> >> Like I said, "It is O(N) because it monotonically advances through both
> >> lists (factories and quotas) without backtracking"
> >>
> >> >
> >> > 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.