This page is part of the web mail archives of SRFI 1 from before July 7th, 2015. The new archives for SRFI 1 contain all messages, not just those from before July 7th, 2015.
Noah Friedman <friedman@xxxxxxxxxx> writes: > But since a couple of people made remarks on this list to effect > that this looked like an "expensive" problem, I just wanted to > point out that it's not especially so. Its complexity isn't higher, but it's still more work. You have two additional variables you're maintaining & and two additional tests per loop. It's not clear whether the extra work is worth it. Its cost on lists with loops ends up being proportional to 2 * (length up to loop) + (2 or 3) * length of loop (depending on how many times the loop is initially traversed). Incidentally, another algorithm for length which doesn't go into an infinite loop on circular lists is to reverse the pointers as you walk the list. If you get back to the head then you encountered a circular list. This one ends up (for lists with loops) being proportional to 4 * (length up to loop) + 2 * length of loop. But I wouldn't recommend it for lots of reasons... -- Harvey Stein Bloomberg LP hjstein@xxxxxxxxxxxxx