[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: LIST-LENGTH & circular lists

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