Re: New array type? (was: 'table' as fallback for tables)

["Thomas Jericke" <tjericke@...>]

-----Original Message----- 
> From: "Dirk Laurie" <dirk.laurie@gmail.com> 
> To: "Lua mailing list" <lua-l@lists.lua.org> 
> Date: 08-07-2016 13:22 
> Subject: Re: New array type? (was: 'table' as fallback for tables) 
> 
> 2016-07-08 11:51 GMT+02:00 Thomas Jericke <tjericke@indel.ch>:
> > On 07/08/2016 09:07 AM, Dirk Laurie wrote:
> >>
> >> 2016-07-08 4:01 GMT+02:00 William Ahern <william@25thandclement.com>:
> >>
> >>> I can't think of a scenario where relying on the #t+1
> >>> guarantee alone is either more concise or more performant.
> >>
> >> Suppose you have coroutines 'producer' and 'consumer' accessing
> >> the same table. 'consumer' has some capricious way of choosing
> >> an item and removing it. 'producer' has no way of knowing what
> >> 'consumer' has been doing and now needs to put a new item in.
> >>
> >>      t[#t+1] = newitem
> >>
> >> seems to me to be unbeatably concise, and needs only O(log n)
> >> time, but with the present Lua documentation is unsound code.
> >> You can make it sound by sacrificing both conciseness and
> >> performance:
> >>
> >>     local k=#t+1; while t[k] do k=k+1 end; t[k]=newitem
> >>
> >> which may take O(n) time.
> >>
> 
> > Why not use a binary search in your example code?
> 
> Actually, #t does.

I am not talking about # but about your example code: 

local k=#t+1; while t[k] do k=k+1 end; t[k]=newitem

could be replaced by 

local k=#t+1
while t[k] ~= nil do k=k*2 end
local i = k/2
while k - i > 1 do
  local m = (k+i)//2
  if t[m] == nil then k = m else i = m
end
t[k+1]=newitem

This is still O(log n)

(It may has typos in this code)

> 
> > Also, while I think your example is legit, I don't think it's such a common
> > use case that it deserves its own operator.
> 
> It happens to _have_ its own operator, but that feature is no
> longer documented.

I thought we are talking about hypothetical future Lua versions here.

> 
> > The current implementation of # could easily just be moved to
> > a function of the table library.
> 
> 
> Darn! These long threads let things slip under the carpet.
> 

It is really too large for me to remember every post, sorry.

> About 30 messages ago, I posted this:
> 
> ~~~
> 1. Make the intuitive Lua 5.0 behaviour (to use the largest numeric
> key of tbl as #tbl) the default. No presently documented property of
> the # operator is violated.
> 
> 2. Instead of 'n', which offends some people, use a secret key
> which a modified 'next' (and therefore 'pairs') will not show.
> 
> 3. New table functions:
> 
> table.frontier(tbl[,k])  Returns the k-th frontier of tbl, that is,
> an integer n>=0 such that t[n+1] is nil but either n=0 or t[n]
> is not nil. If k is omitted, any frontier of t may be returned.
> 
> table.getlength(tbl)  Returns the value, if any, to be returned
> by #tbl when no __len metamethod has been specified.
> 
> table.setlength(tbl,n) Sets n as the value to be returned by
> #tbl when no __len metamethod has been specified.
> 
> The current O(log n) but nondeterministic #t is obtained by
> 
>    setmetatable(tbl,table.frontier)
> ~~~
> 
> So I agree with you on this point :-)

You even have a nice name for it :-)

--
Thomas