lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


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