4 ms·

>...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, crea

by 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.
- keefe 17y ago
  Thanks for the comments and the interesting article. I can see your point about how traversing the structure can result in the same cycle detection issue. I'm actually very interested in algorithms, but lately I try to do everything I can to avoid implementing them basically for maintenance reasons, just because I am totally in a get the thing out the door mindset. I guess my typical problem solving philosophy is to try the laziest practical solution just off having too much to do. gluck in your work!

by keefe 17y ago

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.

keefe 17y ago
Thanks for the comments and the interesting article. I can see your point about how traversing the structure can result in the same cycle detection issue. I'm actually very interested in algorithms, but lately I try to do everything I can to avoid implementing them basically for maintenance reasons, just because I am totally in a get the thing out the door mindset. I guess my typical problem solving philosophy is to try the laziest practical solution just off having too much to do. gluck in your work!