4 ms·

First of all there is a bug in his first pseudocode set. As listed, the hare can easily skip past the turtle unnoticed. If the loop is a particular size, the ha

by hristov 17y ago

First of all there is a bug in his first pseudocode set. As listed, the hare can easily skip past the turtle unnoticed. If the loop is a particular size, the hare can keep skipping past the turtle forever, and the algorithm will operate forever without indicating there is a loop. He needs to perform a comparison after each step of the hare. Regarding the teleporting turtle optimisation, I am not convinced it is an actual optimisation. It will work faster in certain cases, but not in others. For example, imagine there is a big loop in the list. Lets say the hare is halfway through the loop when the turtle just enters the beginning of the loop. At this point, the hare needs to catch up to the turtle and is only half a loop behind. However, imagine that the algorithm decides to teleport the turtle to the hare precisely in this point in time. Then the hare is an entire loop behind the turtle, which means it will be twice as slow to catch up with it just because of the teleporting. So the "optimisation" is faster than the classic algorithm for some types of lists and slower for others. So you cannot say whether it is an optimisation unless you know something about the lists you will have to handle. So it is not really an optimisation per se. I suspect the teleporting turtle algorithm may be considered an optimisation because people assume that most lists will not have a loop and a list with a loop is a rare anomaly. In that case it is in fact an optimisation because it will verify a large non-looped list faster than the classic algorithm.

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 ago
  Actually 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 ago
    In 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 ago
  Reading 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!
  - 17y ago

by hristov 17y ago

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 ago
Actually 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 ago
  In 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 ago
Reading 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!
- 17y ago