3 ms·

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

by 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
To some extent, yes. Suppose you want to use the technique of running around, remembering everything you've seen, then spotting the first duplication. If you're not allowed to mark the nodes then you need to create and maintain some sort of external data structure to remember everything you've seen. Space complexity O(n), time complexity depends on the techniques, but since you have no information about the size then you can assume O(n log n). But the space complexity is the killer, so let's assume you can mark each node. If the mark starts off in a known state then you're OK and the algorithm is trivial. So what if you don't know the starting state of the mark on each node? That means you have to run around the list once, setting each mark to a known state. But how do you know when you're done? There might be a loop, so you need a loop detection algorithm. So even if you're allowed to mark the nodes this is non-trivial.
- keefe 17y ago
  Space complexity is the issue for only a subset of problems, those with extremely large input sets. I think those cases are the exception rather than the rule. I certainly agree that special techniques are required with gigantic or streaming data sets. Finding that size limit is probably interesting... I guess my inclination is to go for either the hash table or search tree solution unless I really, really have to implement some special algorithm. How would you ever not know the start state of the mark on each node? It's a field you invented, null field = not seen. If you are talking about a very large list, it's not going to fit into memory - things tend to get extremely tricky with really big data sets like that. It could be perhaps a node per file ? File where you can add an additional field?
  - RiderOfGiraffes 17y ago
    Your comments are interesting, it shows just how much my background has colored my thinking and caused me to take for granted situations that other people just don't think of. > Space complexity is the issue for only a subset of problems ... Hmm. I deal on a daily basis with datasets that are several GB in size, and don't regard them as especially large. If I wanted to find a loop in a linked list, I'd worry about allocating memory to a subsidiary data structure that was subsequently going to be thrown away. Given that I often don't know the size of the data set, I can't easily create a hash structure, so having a wide selection of algorithms like this immediately to hand gives me a good chance of finding something that will work. My first application of this technique was in an implementation of a variation on the Pollard Rho method of factoring. In that case it's impossible to create a parallel data structure - the teleporting turtle-type of technique is essential. > my inclination is to go for either the hash table > or search tree solution unless I really, really > have to implement some special algorithm. It seems to me that in most of the cases you're considering you wouldn't have a linked list to start with. I get the feeling that the situations where one would seriously consider using a linked list as opposed to a hash table or tree search are those situations where you do have to worry about these issues. As usual the answer is really to question why there's a linked list to start with. > How would you ever not know the start state > of the mark on each node? It's a field you > invented, ... Again, not always the case. I regularly deal with libraries and I'm given an API, but I don't get to define the fields. This happened to me recently where I had a complex data structure and I wanted a flag on each node, but couldn't have it. The solution we thought of first built a subsidiary data structure to keep the additional information, but that destroyed the performance. In the end we used a trick like the teleporting turtle, that reminded me of Floyd's algorithm, and so I wrote it up.
jemfinch 17y ago
> If the list size is known, it's very easy to construct a hash table or hash set If the list size is known, you already know there's not a cycle.
- keefe 17y ago
  not necessarily : here's a file or chunk of memory that's 10MB in size representing a list, is there a cycle? that's a different problem than an infinite sequence of integers.
  - jemfinch 17y ago
    (I know this was 17 days ago, but I just noticed this comment). Being contained in a finite amount of memory does not give a list a size. Lists with cycles may take up a number of nodes, but saying they have a "size," despite the fact that you can iterate over them infinitely and never reach the end, is oxymoronic. An infinite sequence (which a list with a cycle is) has no size.

by keefe 17y ago

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

To some extent, yes. Suppose you want to use the technique of running around, remembering everything you've seen, then spotting the first duplication. If you're not allowed to mark the nodes then you need to create and maintain some sort of external data structure to remember everything you've seen. Space complexity O(n), time complexity depends on the techniques, but since you have no information about the size then you can assume O(n log n). But the space complexity is the killer, so let's assume you can mark each node. If the mark starts off in a known state then you're OK and the algorithm is trivial. So what if you don't know the starting state of the mark on each node? That means you have to run around the list once, setting each mark to a known state. But how do you know when you're done? There might be a loop, so you need a loop detection algorithm. So even if you're allowed to mark the nodes this is non-trivial.

keefe 17y ago
Space complexity is the issue for only a subset of problems, those with extremely large input sets. I think those cases are the exception rather than the rule. I certainly agree that special techniques are required with gigantic or streaming data sets. Finding that size limit is probably interesting... I guess my inclination is to go for either the hash table or search tree solution unless I really, really have to implement some special algorithm. How would you ever not know the start state of the mark on each node? It's a field you invented, null field = not seen. If you are talking about a very large list, it's not going to fit into memory - things tend to get extremely tricky with really big data sets like that. It could be perhaps a node per file ? File where you can add an additional field?
- RiderOfGiraffes 17y ago
  Your comments are interesting, it shows just how much my background has colored my thinking and caused me to take for granted situations that other people just don't think of. > Space complexity is the issue for only a subset of problems ... Hmm. I deal on a daily basis with datasets that are several GB in size, and don't regard them as especially large. If I wanted to find a loop in a linked list, I'd worry about allocating memory to a subsidiary data structure that was subsequently going to be thrown away. Given that I often don't know the size of the data set, I can't easily create a hash structure, so having a wide selection of algorithms like this immediately to hand gives me a good chance of finding something that will work. My first application of this technique was in an implementation of a variation on the Pollard Rho method of factoring. In that case it's impossible to create a parallel data structure - the teleporting turtle-type of technique is essential. > my inclination is to go for either the hash table > or search tree solution unless I really, really > have to implement some special algorithm. It seems to me that in most of the cases you're considering you wouldn't have a linked list to start with. I get the feeling that the situations where one would seriously consider using a linked list as opposed to a hash table or tree search are those situations where you do have to worry about these issues. As usual the answer is really to question why there's a linked list to start with. > How would you ever not know the start state > of the mark on each node? It's a field you > invented, ... Again, not always the case. I regularly deal with libraries and I'm given an API, but I don't get to define the fields. This happened to me recently where I had a complex data structure and I wanted a flag on each node, but couldn't have it. The solution we thought of first built a subsidiary data structure to keep the additional information, but that destroyed the performance. In the end we used a trick like the teleporting turtle, that reminded me of Floyd's algorithm, and so I wrote it up.

jemfinch 17y ago

> If the list size is known, it's very easy to construct a hash table or hash set If the list size is known, you already know there's not a cycle.

keefe 17y ago
not necessarily : here's a file or chunk of memory that's 10MB in size representing a list, is there a cycle? that's a different problem than an infinite sequence of integers.
- jemfinch 17y ago
  (I know this was 17 days ago, but I just noticed this comment). Being contained in a finite amount of memory does not give a list a size. Lists with cycles may take up a number of nodes, but saying they have a "size," despite the fact that you can iterate over them infinitely and never reach the end, is oxymoronic. An infinite sequence (which a list with a cycle is) has no size.