[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: table / array sort and API annoyance
- From: Philipp Janda <siffiejoe@...>
- Date: Thu, 9 Jun 2016 16:56:10 +0200
Am 09.06.2016 um 09:46 schröbte Volker Eckert:
hi,
Hi!
as a relative new user of lua, only a couple of months ago i stumbled
upon the fact that non-contiguous arrays/tables can't be used with
table.sort(). granted, it is not always clear for arbitrary keys,
what the result would look like, but in this case it was an array
with integer indices with a gap (or two), so i'd argue it's not too
far out to want it sorted.
Of course not. But where do you want the gaps to go? You'll have to tell
`table.sort` by supplying a custom comparator function. And you'll have
to tell Lua how many elements you want sorted, because the built-in
heuristic is not unambiguous when gaps are involved. You can do that
using the `__len` metamethod:
local t2 = { [1] = 1, [4] = 3, [5] = 4, [8] = 2 }
setmetatable( t2, { __len = function() return 9 end } )
local function cmp( a, b )
if a == nil then
return false
elseif b == nil then
return true
else
return a < b
end
end
table.sort( t2, cmp )
for i = 1, #t2 do
print( i, t2[ i ] )
end
the annoying thing is that under lua it only fails if it is not the
first entry that's missing (whereas under luajit it always fails):
That's coincidence. E.g. sorting the table `{ [2]=2, [3]=3 }` will
silently do nothing on Lua *and* LuaJIT.
i was wondering why table.sort() isn't written so that it always
fails if the table/array is non-contiguous (because even in the case
where it doesn't, it doesn't actually sort).
In the specific case of `table.sort` it's probably consistency. In
general it's performance reasons. To detect whether a table is a proper
sequence (contiguous) is O(n) while the current length operator is
O(log(n)).
so, instead of the length check, just let it always auxsort() (like
luajit does), which will then fail.
The difference is not whether `auxsort()` is called or not. The
difference is that for this specific array LuaJIT thinks the length is 4
while PUC-Rio Lua thinks it is 0. Both assumptions are reasonable.
further, i think either all the functions from the table [sic!]
namespace that only work with arrays
That would be most of them.
should fail if used on a non-contiguous table/array (probably quite
straightforward to implement, like ... maybe remove __len from them?)
or they should do what it says on the tin (probably more tedious to
implement).
Again, detecting a proper sequence (contiguous array) is costly (and has
nothing to do with removing `__len`). And `__len` actually allows you to
work with non-contiguous arrays in newer Lua versions.
thanks,
volker
Philipp