This page is part of the web mail archives of SRFI 1 from before July 7th, 2015. The new archives for SRFI 1 are here. Eventually, the entire history will be moved there, including any new messages.
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