tag:blogger.com,1999:blog-5246987755651065286.post1209468066283518271..comments2023-11-16T20:41:38.285-08:00Comments on cbloom rants: 09-28-11 - Algorithm - Next Index with Lower Valuecbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-5246987755651065286.post-30899700391714121172016-06-16T10:20:41.846-07:002016-06-16T10:20:41.846-07:00Yep, you're totally right, I failed to mention...Yep, you're totally right, I failed to mention that.<br /><br />Both your solutions are good. <br /><br />Lots of stuff in suffix trees & suffix arrays works neatly if you have a sentinel token at the end, unfortunately we don't get a byte that's > 255 ;) So in practice the code gets a lot uglier with lots of special case handling for the end-of-string case that would've been handled very neatly with a sentinel.<br /><br />I use the first option of manually bubbling back a null entry at the end. It's in the String Match Test code that I released, in MakeNextLowerPosArray.<br />cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-43583378285477254712016-06-16T09:28:41.311-07:002016-06-16T09:28:41.311-07:00Thanks for all your posts, they've been very h...Thanks for all your posts, they've been very helpful. I implemented this algorithm, and discovered that it was incomplete. I'm sure you handled this in your local implementation years ago, but I wanted to document it for others who find this helpful as well.<br /><br />The problem happens when the stack is not empty at the end of the loop. In this case, the stack holds all the values "i" that don't yet have any "j" such that "j > i && A[j] < A[i]". There are no more "j" values to consider, so this condition will never become true.<br /><br />In your notation, "B[i] = j", so we want the invariant on exit to be that "B[i] > i && A[B[i]] < A[i]".<br /><br />Since the stack is stored in the B[] array in the order encountered, and since i increments, these entries for B[i] do satisfy "B[i] > i". The fact that they are still on the stack means "!(B[i] > i && A[B[i]] < A[i])". Since "B[i] > i", this proves "A[B[i]] >= A[i]". If the "A[i]" array has no duplicates, as in the suffix array use case, this becomes a strict inequality: "A[B[i]] > A[i]".<br /><br />Again, in the suffix array case, this means the array that was supposed to only hold pointers to longest *past* matches also has some pointers to *future* matches.<br /><br />There are two fixes I can think of. The most obvious is, after exiting the loop, just pop the stack until it is empty, setting B[i] to "none" as you go.<br /><br />Another solution is to have a sentinel token A[end] at the end of the list that satisfies A[end] < A[i] for all i != end. If "end" is the same as "none", these two solutions are effectively equivalent. The first solution is more obvious, the second solution uses less code and avoids special case handling.<br />Anonymoushttps://www.blogger.com/profile/11052241440319908551noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-12739158277334887232011-10-04T13:00:19.934-07:002011-10-04T13:00:19.934-07:00The full 2N time is taken by
2,4,6,8..M,M-1,M-3,M...The full 2N time is taken by<br /><br />2,4,6,8..M,M-1,M-3,M-5,...1<br /><br /><br />I wish I could find the version of this algorithm that works for windowed ranges, not just monotonic conditions.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-36911787276419343022011-10-04T12:58:51.005-07:002011-10-04T12:58:51.005-07:00It's pretty trivial to prove.
Every iteration...It's pretty trivial to prove.<br /><br />Every iteration writes to B[i] at least once<br /><br />each B[i] can written to at most twice (once for a fence and once for its final correct value)<br /><br />there are N elements of B[]<br /><br />therefore # of operations is >= N and <= 2N<br /><br />QEDcbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-7563745139951338392011-10-04T12:26:10.926-07:002011-10-04T12:26:10.926-07:00I'm not sure this is O(N). What if the input ...I'm not sure this is O(N). What if the input is an array starting with even integers from 2..M and ending with odd integers from 1..M-1.b0b0b0bhttps://www.blogger.com/profile/09035894926385999507noreply@blogger.com