batteries icon indicating copy to clipboard operation
batteries copied to clipboard

table.rotate should use the triple reverse method.

Open Parakleta opened this issue 3 years ago • 1 comments

The existing shift/push method touches every element in the table once per step. The triple reverse method touches every element exactly twice.

function tablex.rotate(t, n)
    local tlen = #t
    local mid = -n % tlen
    tablex.reverse(t)
    tablex.reverse(t, 1, mid)
    tablex.reverse(t, mid+1, tlen)
end

For this to work your tablex.reverse needs to take optional bound arguments. Note that tablex.reverse should also be caching the length value rather than recalculating it in the loop.

Parakleta avatar Mar 25 '22 12:03 Parakleta

should probably branch on n being 1 or not, because that's the most common case in my experience and it'd be strictly slower there.

i think i'd probably prefer tablex.reverse_span rather than reverse itself taking optional arguments, so the intent is clear.

i'm fine with this change otherwise :+1:

1bardesign avatar Mar 30 '22 22:03 1bardesign