3 ms·

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.

• 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.
  • keefe 17y ago
    >...destroyed the performance. Interesting point about APIs. Did you try doing one O(n) pass to dump the list into a secondary format? Just walk the list, creating a new list of your own with the new field and then walk it again to do cycle detection? That's two O(n) walks, still O(n) and should take like an hour to implement. I'm assuming you can get some unique ID for each node from the API, which seems reasonable. Could you give some more insights into the scenarios where you don't know the size of the data? I agree it is an interesting algorithm and I would like to have a better grasp over use cases. >you wouldn't have a linked list to start with In my mind I don't typically turn up linked lists in the wild, just relationships which means graphs and some of them have a structure which maps onto a linked list. I find myself thinking more about the general problem of cycle detection in graphs - a linked list is after all only a special case of a graph. Any relationship-centric data can be scraped and end up with this big pile of data where you want to find cycles. I guess my thinking was colored by the start of the article - "It's a classic interview question: Given a (singly-)linked list, determine whether or not it has a cycle." If the question had said, given an immense linked list or in constant space or without knowing the size, I would have thought differently. If someone gives me a linked list, I assume I have the whole thing. I work with large databases fairly regularly myself. These usually come from some data collection effort (e.g. scraping) and I end up with a pile of data I need to make sense of. In my experience, identifiers are typically a relatively small amount of data compared to the rest. Just as a concrete example, I'm currently forklifting about 4.5M entities in 22GB, with the largest set of identifiers coming out to about 250M. So, with long identifiers that means about 2GB of identifiers for the largest entity class - a relatively easy to deal with number.
    • RiderOfGiraffes 17y ago
      > Did you try doing one O(n) pass to dump the > list into a secondary format? In this case it wasn't a list, and there was the problem of knowing if I'd already walked the entire structure, because there may have been loops, and it's the entire loop detection problem all over again. That was one problem with trying to build the subsidiary structure. We had to do it lazily, and, oh, it's too complex to try to obfuscate what we were doing, and I can't tell you the details because it's commercial in confidence. Sorry. I should add that a lot of my contexts are semi-embedded systems, so limitations in memory, disk, CPU and bandwidths are all unsual. > Could you give some more insights into the scenarios > where you don't know the size of the data? Sadly, no, sorry. In some sense the original problem really encapsulates the essence. Your ideas are valid in many, perhaps virtually all cases, but sometimes you need to solve the problem as given without finding tricks to get around them. I come across problems like that, which is why I like to have a wide range of techniques. > I guess my thinking was colored by the start of the > article - "It's a classic interview question: Given > a (singly-)linked list, determine whether or not it > has a cycle." Noted - I'll look at putting a side note to put it into the more general context to help avoid putting people's thoughts into a smaller box. Thank you.