[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: New array type? (was: 'table' as fallback for tables)
- From: "Soni L." <fakedme@...>
- Date: Thu, 7 Jul 2016 09:57:54 -0300
On 07/07/16 09:22 AM, Peter Aronoff wrote:
"Soni L." <fakedme@gmail.com> wrote:
You need to think of Lua tables as C strings.
Two comments:
1. I have no idea at this point if this is sarcasm or not. But either way,
isn’t this tantamount to saying that they are a mistake in the
language’s design?
I don't consider C to be a mistake, no. C strings and Lua tables are
both NUL/nil-terminated sequences. The main difference is that the
algorithm for Lua table length is O(log n) depending on the
implementation, while the one for C string length is always O(n).
C strings are good for iteration, but poor for length calculation.
They're also very efficient in terms of space, however this doesn't
apply to Lua tables.
Unlike C strings, Lua tables are a general-purpose mutable data
structure, and this is where nil-terminated really shines. Lua tables
are efficient whether you use them as arrays or as maps, this wouldn't
be possible if they weren't nil-terminated. If they weren't nil-terminated:
- #t would return a number directly. This is the only good point.
- t[#t+1]=v would:
- check if the key is an integer (1 op)
- check if the value is not nil (1 op)
- check if the key is greater than the current length (2 ops, as it
has to retrieve the current length)
- set the length to the value of the key (1 op)
- t[#t]=nil would:
- check if the key is an integer (1 op)
- check if the value is nil (1 op)
- check if the key is equal to the current length (2 ops)
- check if how much before the key is empty (O(n))
- imagine setting t[#t-10] to t[#t-1] to nil, then setting
t[#t] to nil.
- set the length to the index of the last nonnil followed by nil (1
op, we find this in the previous step)
- t[huge_number]=v would potentially cause Lua to run out of memory.
- table.remove and table.insert would have to do all checks t[#t+1]=v
and t[#t]=nil have to do, as well as being O(n) by themselves, as they
have to shift elements around.
Alternatively, length could be fixed, having to be manually set. That
would be even less intuitive than what we currently have.
Overall, this would either cause a huge slowdown in the general case for
little to no benefit, or be more of a pain than what we currently have.
What we currently have is a pretty good compromise between intuitiveness
and efficiency.
2. Your reply style (quote everything and add your replies immediately
below whatever you’re replying to without any extra space) is pretty
painful to read. Would you consider adding in some linebreaks, please?
(As an example, I had to scan this reply three or four times before
I could find your reply. Trimming down what you’re quoting to the
relevant bit and adding some whitespace would go a long way.) Thanks for
considering it.
Sorry about that.
P
--
Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.
- References:
- Re: New array type? (was: 'table' as fallback for tables), Hisham
- Re: New array type? (was: 'table' as fallback for tables), steve donovan
- Re: New array type? (was: 'table' as fallback for tables), steve donovan
- Re: New array type? (was: 'table' as fallback for tables), Soni L.
- Re: New array type? (was: 'table' as fallback for tables), Tim Hill
- Re: New array type? (was: 'table' as fallback for tables), Soni L.
- Re: New array type? (was: 'table' as fallback for tables), Tim Hill
- Re: New array type? (was: 'table' as fallback for tables), Coda Highland
- Re: New array type? (was: 'table' as fallback for tables), Tim Hill
- Re: New array type? (was: 'table' as fallback for tables), Soni L.
- Re: New array type? (was: 'table' as fallback for tables), Peter Aronoff