Re: The many lengths of Lua

[Steve Litt <slitt@...>]

On Wed, 14 Sep 2016 16:00:03 -0300
"Soni L." <fakedme@gmail.com> wrote:

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


The description and list of lengths given by Soni L above should be
copied, verbatim, into some easy to find and easy to search Lua
documentation. There have been many times I could have used Soni's
description.

SteveT