Re: The many lengths of Lua

[Russell Haley <russ.haley@...>]

Thanks for the great deep dive! I'm going to save this email for reference. 

Russ

Sent from my BlackBerry 10 smartphone on the Virgin Mobile network.
  Original Message  
From: Soni L.
Sent: Wednesday, September 14, 2016 3:00 PM
To: Lua mailing list
Reply To: Lua mailing list
Subject: The many lengths of Lua

Lua has many lengths. From string lengths to table lengths, from number 
lengths to sequence lengths, from sequence lengths to proper sequence 
lengths. They are the many lengths of Lua.

The # operator returns string lengths and table lengths. It is the 
standard length operator, and it's what you usually use to get the 
length of an object.

The string.len() function returns string lengths. It typechecks the 
argument to make sure it's a string, but otherwise returns the same 
value as #.

There are various types of table length. Some of them are sequences, 
some of them are not. Some have nothing to do with length, but rather 
with count.

The simplest length is the one provided by ipairs(). It only iterates 
the "proper sequence" part of a table. That is, it iterates the set of 
contiguous positive integer keys of a table.[1]
When in doubt, this is the length you should rely on. Don't do `for 
i=1,#t`, but instead use `for i,v in ipairs(t)`.

Another simple length is the one provided by pairs(). This is actually a 
count. If for every iteration of pairs() you increment a counter, you'll 
end up with the number of keys in a table. It is rarely used, but can be 
useful sometimes.

If you want a manual table length, the simplest way to do it is probably 
to just use an `n` field. While Lua supports this usage, the standard 
library doesn't, so you have to deal with it manually. While the 
standard library doesn't natively support the `n` field, some functions, 
such as table.pack(), may emit it.

Another length option is the highest key of a table. You can get this 
length by combining pairs() and math.max(). It can be useful in some 
niche applications but it's quite slow, so consider a manual length (see 
previous paragraph) instead.

By combining pairs() with type(), you can get the number of non-integer 
keys in a table. While this count does exist, I have never seen it used 
in practice.

The length operator, #, can also be applied to tables. If your table has 
a positive integer key, and there's a smaller possitive integer that is 
not a key (i.e. the value associated with it is `nil`), then this 
shouldn't be used. When using a table without manual length, this 
operator is usually faster than any other method[2], but it does have 
the aforementioned drawback. This table length is the only table length 
that is unspecified for some tables.

Finally, you can also use your own length algorithm. Use this if you 
want fast runtime, but the drawbacks of the length operator make it 
unsuitable for your use-case.

And these are the many lengths of Lua!

[1] - I'm not sure how many people know this, but this property 
(stopping on first `nil`) is actually described in the manual. That is, 
ipairs() on a table with "holes" is actually well-defined.
[2] - The Lua manual doesn't guarantee O(log n) time complexity for the 
length operator. If you want guaranteed O(log n) runtime, use your own 
length algorithm. This means # could have O(n) time complexity (i.e. 
equivalent to ipairs()), or even O(m) where m = the number of keys in 
the table (i.e. equivalent to pairs() + math.max()).

PS: Sorry for the wall of text.

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