lua-users home
lua-l archive

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

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. ;-)


> 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


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.

penitent, a.  undergoing or awaiting punishment (Bierce)