Kirill Smelkov <kirr@xxxxxxxxxxxxxx> 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. OK. > ... 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 beginning?). > 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 majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html