Kirill Smelkov <k...@navytux.spb.ru> writes:
> The following
> maybe looks a bit simpler, but calls tree_entry_pathcmp twice more times.
> Besides for important nparent=1 case we were not calling
> tree_entry_pathcmp at all and here we'll call it once, which would slow
> execution down a bit, as base_name_compare shows measurable enough in profile.
> To avoid that we'll need to add 'if (i==imin) continue' and this won't
> be so simple then. And for general nparent case, as I've said, we'll be
> calling tree_entry_pathcmp twice more times...
> Because of all that I'd suggest to go with my original version.
> ... After some break on the topic,
> with a fresh eye I see a lot of confusion goes from the notation I've
> chosen initially (because of how I was reasoning about it on paper, when
> it was in flux) - i.e. xi for x[imin] and also using i as looping
> variable. And also because xi was already used for x[imin] I've used
> another letter 'k' denoting all other x'es, which leads to confusion...
> I propose we do the following renaming to clarify things:
> A/a -> T/t (to match resulting tree t name in the code)
> X/x -> P/p (to match parents trees tp in the code)
> i -> imin (so that i would be free for other tasks)
> then the above (with a prologue) would look like
> ---- 8< ----
> * T P1 Pn
> * - - -
> * |t| |p1| |pn|
> * |-| |--| ... |--| imin = argmin(p1...pn)
> * | | | | | |
> * |-| |--| |--|
> * |.| |. | |. |
> * . . .
> * . . .
> * at any time there could be 3 cases:
> * 1) t < p[imin];
> * 2) t > p[imin];
> * 3) t = p[imin].
> * Schematic deduction of what every case means, and what to do, follows:
> * 1) t < p[imin] -> ∀j t ∉ Pj -> "+t" ∈ D(T,Pj) -> D += "+t"; t↓
> * 2) t > p[imin]
> * 2.1) ∃j: pj > p[imin] -> "-p[imin]" ∉ D(T,Pj) -> D += ø; ∀
> pi=p[imin] pi↓
> * 2.2) ∀i pi = p[imin] -> pi ∉ T -> "-pi" ∈ D(T,Pi) -> D +=
> "-p[imin]"; ∀i pi↓
> * 3) t = p[imin]
> * 3.1) ∃j: pj > p[imin] -> "+t" ∈ D(T,Pj) -> only pi=p[imin] remains
> to investigate
> * 3.2) pi = p[imin] -> investigate δ(t,pi)
> * |
> * |
> * v
> * 3.1+3.2) looking at δ(t,pi) ∀i: pi=p[imin] - if all != ø ->
> * ⎧δ(t,pi) - if pi=p[imin]
> * -> D += ⎨
> * ⎩"+t" - if pi>p[imin]
> * in any case t↓ ∀ pi=p[imin] pi↓
> now xk is gone and i matches p[i] (= pi) etc so variable names correlate
> to algorithm description better.
> Does that maybe clarify things?
That sounds more consistent (modulo perhaps s/argmin/min/ at the
> P.S. Sorry for maybe some crept-in mistakes - I've tried to verify it
> thoroughly, but am too sleepy to be completely sure. On the other hand I
> think and hope the patch should be ok.
Thanks and do not be sorry for "mistakes"---we have the review
process exactly for catching them.
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html