Re: Improving the efficiency of next

[Reuben Thomas <rrt@...>]

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)