[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: Improving the efficiency of next
- From: Reuben Thomas <rrt@...>
- Date: Wed, 26 Nov 2003 10:51:01 +0000 (GMT)
Edgar pointed out (by private email, but I hope he won't mind me copying
to the list, since my mistake was egregious):
> Sure, linear - you're not using next. ;-)
Rats.
> Meant was a special use of next where it's linear runtime is exposed:
>
> i = next(t)
> while i do
> t[i] = nil
> i = next(t) -- always starts at the beginning of t
> end
Rats.
I was being fantastically stupid. Can't explain why. Not a generator
function in sight in my code. Definitely a "could the earth please swallow
me now?" moment.
And of course I understand why it's quadratic: if you will insist on
changing the table, you can't iterate over the whole thing, and must
instead restart every time.
Sigh. I think I need a new brain.
Only thing that really confuses me is that I thought this was all
explained at the time, but I can't find it in the archives. Again, I was
probably just not doing the right search.
--
http://www.mupsych.org/~rrt/
penitent, a. undergoing or awaiting punishment (Bierce)