4 ms·
I don't think you're correct that the hare can skip past the tortoise indefinitely. Certainly, I cannot find such a loop. On the question of whether it is a co
by barrkel 17y ago
I don't think you're correct that the hare can skip past the tortoise indefinitely. Certainly, I cannot find such a loop.
On the question of whether it is a constant factor optimization, though, it rather depends on the relative costs of following a link versus the bookkeeping accounting for steps taken. Empirically tested in a simple program, teleporting turtle (TT) is slower than tortoise and hare (TH) when simply following linked lists in adjacently laid out in memory. When retrieving a link is made more costly, TT pulls ahead. I cannot find any scenario where TT follows more links than TH, only less or equal.
So it seems that following links is the thing that is being optimized for, which makes sense for finding loops in PRNGs and similar problems: you want to optimize to reduce the number of links taken. As I explain in a different message, because each iteration of TH is so much more costly than TT, TT can't really lose.
- hristov 17y agoActually it seems you are right on both accounts. In the first case the hair would not actually jump over the turtle except for the very beginning. It is funny how that works, it is rather counter intuitive. And in the second case, I think in the worst case scenario the optimization performs the same number of link followings as the original algorithm. That is because the original algorithm performs duplicative work as the turtle has to follow the same links the hare did. But of course if following a link was that expensive, one would modify the original algorithm to save all the links that the hare traversed so that one does not have to pay for the turtle to follow them. This will result in the original algorithm being faster in certain circumstances than the optimisation (although it may use a bit more memory). Well anyways I was wrong at the top, I am sorry if I offended anyone by stating that they had bugs in their pseudocode. I should not argue with stuff that has been obviously academically developed and argued and double checked to death before i have seen it.
- barrkel 17y agoIn terms of saving the links, I think it's not necessarily the wisest course for scenarios like PRNGs etc., where that may mean saving millions or billions of intermediate number results. The TH algorithm is Floyd's algorithm, while the TT algorithm is Brent's algorithm in the Wikipedia cycle detection link.
- rwolf 17y agoReading the article, I too felt that another check was needed, to prevent the hare from sometimes leapfrogging eternally. While drafting a snappy comeback to your comment that there was no such loop, I tried to find the smallest loop that demonstrated the bug, and came across a very nice pattern: 1: (1,1),(1,1) 2: (1,1),(1,2),(1,1) 3: (1,1),(3,2),(2,3),(1,1) 4: (1,1),(3,2),(1,3),(3,4),(1,1) 5: (1,1),(3,2),(5,3),(2,4),(4,5),(1,1) 6: (1,1),(3,2),(5,3),(1,4),(3,5),(5,6),(1,1) ... Put another way, once the tortoise enters the loop, it will take <=n-1 steps (where n is the size of the loop) for them to come together (without teleportation). This problem seems like way too much fun to use in an interview!
- gjm11 17y agoThe point is that (hare position minus tortoise position, modulo loop size if there is a loop) increases by exactly 1 every time. So if there is a loop it will eventually reach 0, fewer than (loop size) steps after entering the loop.