[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: Sorting part of a list
- From: Dirk Laurie <dirk.laurie@...>
- Date: Wed, 18 Apr 2012 12:57:01 +0200
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.