Re: Sorting part of a list

[Dirk Laurie <dirk.laurie@...>]

Op 18 april 2012 12:18 heeft Daniel Slaney
<Daniel.Slaney@lockwood-studios.com> het volgende geschreven:
> I've recently tried to implement an algorithm that requires sorting just
> a section of an array at a time.
>
> Unless I'm missing something this requires making copies of the
> sub-array in Lua which is sub-optimal.
>

You could make a proxy table for the subarray.

function slice(tbl,i,j)
   local t={}
   local origin=i-1
   setmetatable(t,{
__len=function(self) return j-origin end;
__index=function(self,k) return tbl[k+origin] end;
__newindex=function(self,k,v) tbl[k+origin]=v end;
})
   return t
end

That will work for Lua-based routines but
not for the routines in the table library since
"For performance reasons, all table accesses (get/set)
performed by these functions are raw. "

> Would it be possible to change (using the syntax from the reference
> manual):
>
> table.sort(list [, comp])
>
>  to
>
> table.sort(list, [, comp [, i [, j]]])
>
> Where i and j are the first and last indexes to sort between and they
> default to 1 and #list respectively.

It would be trivial in the C source for Lua.  There is already a function
`auxsort` that does just that, called as` auxsort(L, 1, n)` from `sort`.
You just need a couple of extra statements to pop i and j from the stack.

I'll support a proposal for this change to be mainstream.

1. Generalizes an existing feature without breaking anything.
2. No performance hit.