8 ms·

The Tale of the Teleporting Turtle (algorithm)

abscondment 17y ago
Cool. Bonus points for alliteration.
argv_empty 17y ago
To say, "now on every clock tick we only take one step, not three," seems to imply that the optimized version takes 1/3 as many steps. The mammal still doesn't catch the reptile without doing two full laps while the reptile does one. For an n-entry loop: The original version has the tortoise take n steps and the hare take 2n steps. The optimized version has the rabbit take 2n steps and the turtle take lg(n) steps. For an n-entry line: The original version has the tortoise take n/2 steps and the hare take n steps. The optimized version has the rabbit take n steps and the turtle take lg(n) steps. Or did I misread the algorithm?
- barrkel 17y ago
  Your misreading: the turtle doesn't move at all. It teleports to the rabbit's location. (Counting following a link as a move, which seems to be the costly operation being optimized for.) For every full iteration of the loop, TH (tortoise and hare) follows 3 links, while TT (teleporting turtle) follows 1 link. In the loop case, where the loop of length n is linked in at k steps, the there must be at least k iterations of both loops (the turtle or tortoise must reach the loop). In the no-loop case, there must be at least n iterations of the TT case but TH can get away with n/2 iterations. Unfortunately, each iteration of TH has more than twice the cost of an iteration of TT, when optimizing for following loops.
  - argv_empty 17y ago
    * For every full iteration of the loop, TH (tortoise and hare) follows 3 links, while TT (teleporting turtle) follows 1 link.* Except the TT loop iterations accomplish half as much in terms of covering ground, so TH and TT don't take the same number of iterations.
    - JoachimSchipper 17y ago
      If both Tortoise and Hare have just entered a cycle of length n, the original algorithm takes n iterations before the Tortoise is caught (2n steps for the Hare, n steps for the Tortoise). Likewise, TT takes n steps (although it may take some additional steps before the turtle is teleported into the loop; once this has happened, it's n steps.)
      - argv_empty 17y ago
        * once this has happened, it's n steps* Unless the turtle teleports some time during those n steps. The only way the turtle won't teleport during that time is if the rabbit has already taken at least n steps to get to the loop, in which case, it only eliminates up to 1/4 of the mammal moves.
keefe 17y ago
Certainly an interesting discussion of some algorithms here, however... "In fact the number of checks grows quadratically with the length of your list" No, no this is not necessarily true at all? If you are talking about an interview-style question where we are discussing a linked list in memory not some giant implicit list of integers, then it is very easy to beat O(n^2). If the list size is known, it's very easy to construct a hash table or hash set where collisions are extremely low and O(1) lookups are expected, giving an O(n) algorithm. A binary search tree would give O(n log n)
- lmkg 17y ago
  Part of the problem is that the list size is not known. If the list size where known to be N, then you simply traverse N elements and check if the tail is null or not.
  - keefe 17y ago
    I think this is clever <notes>
- cabalamat 17y ago
  > If the list size is known, it's very easy to construct a hash table or hash set where collisions are extremely low and O(1) lookups are expected If the list size isn't known, you can still do this, by doubling the size of the hash table whenever there are too many entries in it.
  - RiderOfGiraffes 17y ago
    > doubling the size of the hash table whenever > there are too many entries in it. And then re-hashing and dealing with all that implies. Surely all of that is much harder than chasing a pair of pointers down the list. Also, it doesn't work in the case of, say, Pollard's Rho method of factoring. I really need to change the original article to make it clear that that's a case I'm interested in.
- RiderOfGiraffes 17y ago
rflrob 17y ago
I don't understand... why does the turtle need to move at all?
- Batsu 17y ago
  If you have the tortoise and hare start at 1, but there is a loop going 2 -> 3 -> 2 -> ... then, without moving the tortoise, the hare will never find the tortoise or the end of the list.
- mbrubeck 17y ago
  The cycle might not include the head of the list. You need to keep moving the turtle until it is in the cycle. Otherwise the rabbit will enter the circle and keep running around and never see the turtle again. Crude ASCII art version: TURTLE-->--+--->--+ / \ | RABBIT \ / +---<--+
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.
barrkel 17y ago
Odd. The "teleporting turtle" was the first solution to this problem that I thought I had recalled after being reminded of it in this link, but when I read the tortoise / hare solution, I knew this was the original solution I had read when I first heard about this problem. In other words, while trying to remember the details of the tortoise and hare solution, I turned it into the described teleporting turtle solution, the intuition being that doubling the length of the cycle check would amortize to constant time per link.
Retric 17y ago
It's not bad, but due to memory access latency, keeping a short list of "rabbit droppings" is going to be faster on long lists.

Cool. Bonus points for alliteration.

To say, "now on every clock tick we only take one step, not three," seems to imply that the optimized version takes 1/3 as many steps. The mammal still doesn't catch the reptile without doing two full laps while the reptile does one. For an n-entry loop: The original version has the tortoise take n steps and the hare take 2n steps. The optimized version has the rabbit take 2n steps and the turtle take lg(n) steps. For an n-entry line: The original version has the tortoise take n/2 steps and the hare take n steps. The optimized version has the rabbit take n steps and the turtle take lg(n) steps. Or did I misread the algorithm?

barrkel 17y ago
Your misreading: the turtle doesn't move at all. It teleports to the rabbit's location. (Counting following a link as a move, which seems to be the costly operation being optimized for.) For every full iteration of the loop, TH (tortoise and hare) follows 3 links, while TT (teleporting turtle) follows 1 link. In the loop case, where the loop of length n is linked in at k steps, the there must be at least k iterations of both loops (the turtle or tortoise must reach the loop). In the no-loop case, there must be at least n iterations of the TT case but TH can get away with n/2 iterations. Unfortunately, each iteration of TH has more than twice the cost of an iteration of TT, when optimizing for following loops.
- argv_empty 17y ago
  * For every full iteration of the loop, TH (tortoise and hare) follows 3 links, while TT (teleporting turtle) follows 1 link.* Except the TT loop iterations accomplish half as much in terms of covering ground, so TH and TT don't take the same number of iterations.
  - JoachimSchipper 17y ago
    If both Tortoise and Hare have just entered a cycle of length n, the original algorithm takes n iterations before the Tortoise is caught (2n steps for the Hare, n steps for the Tortoise). Likewise, TT takes n steps (although it may take some additional steps before the turtle is teleported into the loop; once this has happened, it's n steps.)
    - argv_empty 17y ago
      * once this has happened, it's n steps* Unless the turtle teleports some time during those n steps. The only way the turtle won't teleport during that time is if the rabbit has already taken at least n steps to get to the loop, in which case, it only eliminates up to 1/4 of the mammal moves.

keefe 17y ago

Certainly an interesting discussion of some algorithms here, however... "In fact the number of checks grows quadratically with the length of your list" No, no this is not necessarily true at all? If you are talking about an interview-style question where we are discussing a linked list in memory not some giant implicit list of integers, then it is very easy to beat O(n^2). If the list size is known, it's very easy to construct a hash table or hash set where collisions are extremely low and O(1) lookups are expected, giving an O(n) algorithm. A binary search tree would give O(n log n)

lmkg 17y ago
Part of the problem is that the list size is not known. If the list size where known to be N, then you simply traverse N elements and check if the tail is null or not.
- keefe 17y ago
  I think this is clever <notes>
cabalamat 17y ago
> If the list size is known, it's very easy to construct a hash table or hash set where collisions are extremely low and O(1) lookups are expected If the list size isn't known, you can still do this, by doubling the size of the hash table whenever there are too many entries in it.
- RiderOfGiraffes 17y ago
  > doubling the size of the hash table whenever > there are too many entries in it. And then re-hashing and dealing with all that implies. Surely all of that is much harder than chasing a pair of pointers down the list. Also, it doesn't work in the case of, say, Pollard's Rho method of factoring. I really need to change the original article to make it clear that that's a case I'm interested in.
RiderOfGiraffes 17y ago

rflrob 17y ago

I don't understand... why does the turtle need to move at all?

Batsu 17y ago
If you have the tortoise and hare start at 1, but there is a loop going 2 -> 3 -> 2 -> ... then, without moving the tortoise, the hare will never find the tortoise or the end of the list.
mbrubeck 17y ago
The cycle might not include the head of the list. You need to keep moving the turtle until it is in the cycle. Otherwise the rabbit will enter the circle and keep running around and never see the turtle again. Crude ASCII art version: TURTLE-->--+--->--+ / \ | RABBIT \ / +---<--+

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.

barrkel 17y ago

Odd. The "teleporting turtle" was the first solution to this problem that I thought I had recalled after being reminded of it in this link, but when I read the tortoise / hare solution, I knew this was the original solution I had read when I first heard about this problem. In other words, while trying to remember the details of the tortoise and hare solution, I turned it into the described teleporting turtle solution, the intuition being that doubling the length of the cycle check would amortize to constant time per link.

Retric 17y ago

It's not bad, but due to memory access latency, keeping a short list of "rabbit droppings" is going to be faster on long lists.