Re: Unexpected table.remove behaviour.

[lostgallifreyan <lostgallifreyan@...>]

Doug Currie <doug.currie@gmail.com> wrote:
(24/06/2009 22:22)

>Your solution(s) using table.remove do a quadratic number of table  
>moves. Here's an approach that's linear, scans in the forward  
>direction, and doesn't leave any holes in X or Y:
>
>function t2()
>     local  
>X 
>= 
>{0,0,0,0,0,1,1,1,1,2,2,3,4,5,5,5,5,5,6,6,6,6,6,6,6,6,7,8,8,8,8,8,8,8,8,8,9,9,9,9 
>}
>     local Y={}
>     local k = #X -- initial size
>     local i = 1  -- insert point
>     for n = 1, k do
>         local e = X[n]
>         X[n] = nil
>         if e ~= X[i-1] then Y[i] = n; X[i] = e; i = i + 1 end
>     end
>     print(i-1)
>     print(unpack(X))
>     print(unpack(Y))
>end
>


Nice. I think I've used something like it before, but I forget, because I've always had some blind faith in Lua's inbuilt methods in C doing things faster than anything I try to replace them with in what is interpreted language and runs slower. In this case I guess it's not slower. If it isn't I'll certainly change to this. Thankyou. I especially like it because it doesn't depend on behaviour specific to Lua or any other language. At some point I want to learn C and port my program to it, and this will help a lot then.