Sorting part of a list

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Sorting part of a list

Daniel Slaney
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.

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.


Daniel Slaney

Reply | Threaded
Open this post in threaded view
|

Re: Sorting part of a list

Dirk Laurie-2
Op 18 april 2012 12:18 heeft Daniel Slaney
<[hidden email]> 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.

Reply | Threaded
Open this post in threaded view
|

Re: Sorting part of a list

David Manura
On Wed, Apr 18, 2012 at 6:57 AM, Dirk Laurie <[hidden email]> wrote:
> Op 18 april 2012 12:18 heeft Daniel Slaney het volgende geschreven:
>> I've recently tried to implement an algorithm that requires sorting just
>> a section of an array at a time.
> You could make a proxy table for the subarray.[...
> it will not work] for the routines in the table library since
> "For performance reasons, all table accesses (get/set)
> performed by these functions are raw. "

The following actually does work in Lua 5.2:

$ lua52
Lua 5.2.0  Copyright (C) 1994-2011 Lua.org, PUC-Rio
> t = {10,9,8,7,6,5,4,3,2,1}
> setmetatable(t, {__len = function() return 5 end})
> table.sort(t)
> for _,v in ipairs(t) do print(v) end
6 7 8 9 10 5 4 3 2 1

but it is only able to set the upper bound, not the lower bound, on
the sort, so it's of limited use.

Observe that the table.* functions do honor the __len operator in 5.2.
 This change between 5.1 and 5.2 was for reasons that remain unclear
to me [1-3].  I'm not aware of a serious argument or use case for it,
so I'm a bit puzzled by it.  I would be interested if anyone relies on
that behavior in production.

BTW, you can reimpement the table.sort function in pure Lua.
Performance can actually be quite good [4].  I recently used a form of
[4] to sort two arrays in parallel, which is another case that
table.sort itself doesn't support well.

[1] http://lua-users.org/lists/lua-l/2010-12/msg00653.html
[2] http://lua-users.org/lists/lua-l/2011-11/msg01003.html
[3] http://lua-users.org/lists/lua-l/2011-11/msg00992.html
[4] http://lua-users.org/wiki/LuaSorting

Reply | Threaded
Open this post in threaded view
|

Re: Sorting part of a list

Miles Bader-2
David Manura <[hidden email]> writes:
> Observe that the table.* functions do honor the __len operator in
> 5.2.  This change between 5.1 and 5.2 was for reasons that remain
> unclear to me [1-3].  I'm not aware of a serious argument or use
> case for it, so I'm a bit puzzled by it.

It looks to me like it was the result of a general cleanup of
length-calculating stuff in 5.2, more than an explicit change to
table.sort.

-Miles

--
Somebody has to do something, and it's just incredibly pathetic that it
has to be us.  -- Jerry Garcia