A question about table's length

classic Classic list List threaded Threaded
30 messages Options
12
Reply | Threaded
Open this post in threaded view
|

A question about table's length

h visli
Hello all,

I'm a newbie of the Lua world. Here is my code:

a = {}
a[1] = 1
a[2] = nil
a[3] = 3
print('Length of a: ' .. #a)

b = {1, nil, 3}
print('Length of b: ' .. #b)

The result:
Length of a: 1
Length of b: 3
Why the length of b is not equal to 1?

Thank you!
Visli


      ___________________________________________________________
  好玩贺卡等你发,邮箱贺卡全新上线!
http://card.mail.cn.yahoo.com/
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

Klaus Ripke
On Tue, Dec 29, 2009 at 05:03:12PM +0800, h visli wrote:
> b = {1, nil, 3}
...
> Why the length of b is not equal to 1?

http://www.lua.org/manual/5.1/manual.html#2.5.5


happy new year
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

h visli
>
http://www.lua.org/manual/5.1/manual.html#2.5.5


With the description of manual.html#2.5.5 , the length of b should be 1 rather than 3. Because b[2]'s value is nil, so the array has "holes".



      ___________________________________________________________
  好玩贺卡等你发,邮箱贺卡全新上线!
http://card.mail.cn.yahoo.com/
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

Duboucher Thomas-2
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

h visli a écrit :
> http://www.lua.org/manual/5.1/manual.html#2.5.5
>
> With the description of manual.html#2.5.5 , the length of b should be 1 rather than 3. Because b[2]'s value is nil, so the array has "holes".
>

        That's what I thought too, but the manual says
"If the array has "holes" [...], then #t can be any of the indices that
directly precedes a nil value [...]."
        So the result for #a and #b can be *either* 1 or 3, which is what
you've got.

        Thomas.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAks50foACgkQBV7eXqefhqgKYQCfQEpoTOIu3/NEB6AWfbwFmwXU
ylcAoKq1sKwvmB9fTP1LYgY2Mqmi2vZG
=J4R7
-----END PGP SIGNATURE-----


Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

Klaus Ripke
In reply to this post by h visli
Hello visli


On Tue, Dec 29, 2009 at 05:34:48PM +0800, h visli wrote:
> With the description of manual.html#2.5.5 , the length of b should be 1 rather than 3. Because b[2]'s value is nil, so the array has "holes".

please take the time to read all five sentences of 2.5.5,
especially before assuming Lua does not work properly
and/or other people write nonsense.

The fifth sentence is:
"
If the array has "holes" (that is, nil values between other non-nil values),
then #t CAN BE ANY of the indices that directly precedes a nil value
(that is, it may consider any such nil value as the end of the array).
"

So 3 is perfectly ok.


thank you very much
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

h visli
Hello Ripke,
 

Yes, I also noticed those words, but it still confusing me, maybe my English is poor, can you put more detailed explanation? Thanks In Advance!


>please take the time to read all five sentences of 2.5.5,
>especially before assuming Lua does not work properly
>and/or other people write nonsense.

>The fifth sentence is:
>"
>If the array has "holes" (that is, nil values between other non-nil values),
>then #t CAN BE ANY of the indices that directly precedes a nil value
>(that is, it may consider any such nil value as the end of the array).
>"

>So 3 is perfectly ok.


>thank you very much



      ___________________________________________________________
  好玩贺卡等你发,邮箱贺卡全新上线!
http://card.mail.cn.yahoo.com/
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

steve donovan
2009/12/29 h visli <[hidden email]>:
> Yes, I also noticed those words, but it still confusing me, maybe my English is poor, can you put more detailed explanation? Thanks In Advance!

Reading manuals can be hard, especially since they only say the
important things once!

Look at this case
{10,nil,20,nil}
  1   2   3  4

So the values preceding the 'hole' are 10 (at 1) and 20 (at 3). So #
can report a length of either 1 or 3.

Moral of story: don't trust # for a table with holes.  Keep the actual
count and use that:

t = {n=4,10,nil,20,nil}
for i = 1,t.n do print(t[i]) end  -- will print out all values, even if nil

If you need to put nil in a table, think of using a 'placeholder'
value which shall represent nil

NIL = {}
t = {10,NIL,20,NIL}

and then convert any NIL values into actual nils.

steve d.


steve d.
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

Klaus Ripke
In reply to this post by h visli
On Tue, Dec 29, 2009 at 06:22:23PM +0800, h visli wrote:
> Yes, I also noticed those words, but it still confusing me, maybe my English is poor, can you put more detailed explanation? Thanks In Advance!

hmm, how to explain "can be any"?
Does this make any sense to you?
http://translate.google.de/translate_t?hl=&ie=UTF-8&text=x+CAN+BE+ANY+of+the+indices+that+directly+precedes+a+nil+value&sl=en&tl=zh-CN#

Anyway, another attempt using different words:
The implementation is allowed to return an arbitrary
"index n such that t[n] is not nil and t[n+1] is nil".

In your example both 1 and 3 are allowed.
The definition does not say it must be the lowest or largest such n
to allow an efficient implementation.
Still it's well defined for arrays without holes.


best
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

Cosmin Apreutesei
In reply to this post by steve donovan
> Moral of story: don't trust # for a table with holes.

moral #2: manuals are poor teachers, combine them with proper learning
books[1]... which gives me the idea of an unofficial Lua manual made
only of straight talk like the above sentence.

[1] http://www.lua.org/pil/
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

Vaughan McAlley
In reply to this post by Klaus Ripke
It allows for an efficient implementation of the # operator. What
happens (I think) is that as positive indices are added to the table,
Lua searches for any index where t[index] exists and t[index + 1] is
nil. This saves traversing the whole table when adding one element,
which would be a performance hit.

As everyone says, keep your table hole-free and there will be no
problems. An alternative is table.maxn(): see
http://www.lua.org/manual/5.1/manual.html#pdf-table.maxn

Vaughan

2009/12/29 Klaus Ripke <[hidden email]>:

> On Tue, Dec 29, 2009 at 06:22:23PM +0800, h visli wrote:
>> Yes, I also noticed those words, but it still confusing me, maybe my English is poor, can you put more detailed explanation? Thanks In Advance!
>
> hmm, how to explain "can be any"?
> Does this make any sense to you?
> http://translate.google.de/translate_t?hl=&ie=UTF-8&text=x+CAN+BE+ANY+of+the+indices+that+directly+precedes+a+nil+value&sl=en&tl=zh-CN#
>
> Anyway, another attempt using different words:
> The implementation is allowed to return an arbitrary
> "index n such that t[n] is not nil and t[n+1] is nil".
>
> In your example both 1 and 3 are allowed.
> The definition does not say it must be the lowest or largest such n
> to allow an efficient implementation.
> Still it's well defined for arrays without holes.
>
>
> best
>
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

David Manura
On Tue, Dec 29, 2009 at 7:48 AM, Vaughan McAlley wrote:
> It allows for an efficient implementation of the # operator.

I thought I would mention that the following two loops do not have the
same output:

  t = {1,nil,2}
  for i,v in ipairs(t) do print(v) end  --> 1
  for i=1,#t do print(t[i]) end --> 1 nil 2 (maybe)

This leads to an open question if you want to implement a function
like [1] that is to separately deal with the array and hash parts of a
table.  To implement such functions robustly and generally, we need to
specify whether values like 2 above are to be considered in the hash
part or array part, and we need to be careful how we iterate.

[1] http://snippets.luacode.org/sputnik.lua?p=snippets/Iterating_over_the_hash_part_of_a_table_6
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

steve donovan
On Wed, Dec 30, 2009 at 5:45 AM, David Manura <[hidden email]> wrote:
> table.  To implement such functions robustly and generally, we need to
> specify whether values like 2 above are to be considered in the hash
> part or array part, and we need to be careful how we iterate.

Ah, yes, because the array part is (naively) assumed to be between 1
and #t.  Looks like I did not read the famous Fifth Sentence carefully
enough.

So, what ultimately _is_ the array part?  What is the least suprising
definition?
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

Philippe Lhoste
On 30/12/2009 08:52, steve donovan wrote:
> So, what ultimately _is_ the array part?  What is the least suprising
> definition?

Perhaps the comment from ltable.c:

<<
Implementation of tables (aka arrays, objects, or hash tables).
Tables keep its elements in two parts: an array part and a hash part.
Non-negative integer keys are all candidates to be kept in the array
part. The actual size of the array is the largest `n' such that at
least half the slots between 0 and n are in use.
Hash uses a mix of chained scatter table with Brent's variation.
A main invariant of these tables is that, if an element is not
in its main position (i.e. the `original' position that its hash gives
to it), then the colliding element is in its own main position.
Hence even when the load factor reaches 100%, performance remains good.
 >>

On 29/12/2009 13:48, Vaughan McAlley wrote:
 > As everyone says, keep your table hole-free and there will be no
 > problems.

Good advice, we rarely need holes in plain arrays, or manage them
differently (as Steve shown). After all, we have to do it this way in
plain C...

That said, what h visli shown is the kind of code we write when
exploring the language and asking some questions ("what if..."). :)

--
Philippe Lhoste
--  (near) Paris -- France
--  http://Phi.Lho.free.fr
--  --  --  --  --  --  --  --  --  --  --  --  --  --

Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

steve donovan
On Wed, Dec 30, 2009 at 12:05 PM, Philippe Lhoste <[hidden email]> wrote:
> Perhaps the comment from ltable.c:

Which is a clear statement about the current implementation. All in
all, it's best to avoid holes. We could go to a lot of trouble to
handle holey arrays, but their behaviour is not fully determined.

BTW, Lua iterator sequences have the same problems with nil values,
since they end the iteration.

A map() function could easily generate lots of holes:

map(tonumber,{'10','x','20','y'})  --> {10,nil,20,nil}

I would suggest that the result here should actually be {10,20}, that
is, if the function called by map() returns nil, then it should not be
part of the result array.  We avoid holes, and get a convenient
filter-map idiom.

steve d.
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

Mark Hamburg
On Dec 30, 2009, at 9:36 PM, steve donovan wrote:

> On Wed, Dec 30, 2009 at 12:05 PM, Philippe Lhoste <[hidden email]> wrote:
>> Perhaps the comment from ltable.c:
>
> Which is a clear statement about the current implementation. All in
> all, it's best to avoid holes. We could go to a lot of trouble to
> handle holey arrays, but their behaviour is not fully determined.
>
> BTW, Lua iterator sequences have the same problems with nil values,
> since they end the iteration.
>
> A map() function could easily generate lots of holes:
>
> map(tonumber,{'10','x','20','y'})  --> {10,nil,20,nil}
>
> I would suggest that the result here should actually be {10,20}, that
> is, if the function called by map() returns nil, then it should not be
> part of the result array.  We avoid holes, and get a convenient
> filter-map idiom.

Yes, that's been my conclusion as well though I don't really like it. I'd like to have filters that might produce nil -- particularly when dealing with multivalued iterators -- and handle the filtering separately but this seems the best compromise.

Lua iterations could have been defined as terminating upon receipt of no values from the iterator, but this has the problem that it's actually  bit more expensive to detect in Lua since you need to pass ... to select to count the number of values.

Mark

Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

Shmuel Zeigerman
In reply to this post by David Manura
David Manura wrote:
>
> [1] http://snippets.luacode.org/sputnik.lua?p=snippets/Iterating_over_the_hash_part_of_a_table_6

This particular snippet doesn't take into account that keys can be
non-integer numbers, e.g. 1.234

--
Shmuel
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

Leo Razoumov
In reply to this post by steve donovan
On 2009-12-31, steve donovan <[hidden email]> wrote:

> On Wed, Dec 30, 2009 at 12:05 PM, Philippe Lhoste <[hidden email]> wrote:
>  > Perhaps the comment from ltable.c:
>
> [..snip..]
>
>  A map() function could easily generate lots of holes:
>
>  map(tonumber,{'10','x','20','y'})  --> {10,nil,20,nil}
>
>  [..snip..]
>  steve d.
>

I wish that "map" would convert nil to false before pushing it into
resultant array so that it becomes {10, false, 20, false} avoiding
holes and preserving the length. Within conditionals like "if",
"while" etc nil and false are equivalent.

--Leo--
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

Florian Weimer
In reply to this post by steve donovan
* steve donovan:

> So, what ultimately _is_ the array part?  What is the least suprising
> definition?

Arrays ae nil-terminated tables, with indices starting at 1 (not
entirely unlike C strings).  Storing a nil value into an array has
undefined results.

A couple of weeks ago, I caught up with several months of mailing list
postings, and I noticed that this particular topic (storing nils in
arrays) reoccurred pretty often.  I don't think that Lua's behavior is
improper, but it seems to puzzle users quite a bit.  In this light,
more predictable behavior would likely make the language easier to
use.
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

steve donovan
In reply to this post by Leo Razoumov
On Thu, Dec 31, 2009 at 3:44 PM, Leo Razoumov <[hidden email]> wrote:
> I wish that "map" would convert nil to false before pushing it into
> resultant array so that it becomes {10, false, 20, false} avoiding
> holes and preserving the length.

So 'false' becomes a way to represent holes? But I don't see why it is
crucial to preserve length of the result. Also, even if in principle
the result is all of one type, it ends up in general as a mixture of
booleans and that type.  There could be another operation which will
explicitly remove all occurances of a value, so my desired result is
something like map(strs,tonumber):remove_values(false)

steve d.
Reply | Threaded
Open this post in threaded view
|

Re: A question about table's length

Mark Hamburg
In reply to this post by Florian Weimer
On Dec 31, 2009, at 9:05 AM, Florian Weimer wrote:

> A couple of weeks ago, I caught up with several months of mailing list
> postings, and I noticed that this particular topic (storing nils in
> arrays) reoccurred pretty often.  I don't think that Lua's behavior is
> improper, but it seems to puzzle users quite a bit.  In this light,
> more predictable behavior would likely make the language easier to
> use.

I agree that the behavior is appropriate and well-defined. Complaints that #t doesn't have a specified result if t has holes do not indicate a problem with the definition. The definition bounds the results in that case but does not specify them because doing so would have performance costs elsewhere.

I also agree that this bites people more than is perhaps desirable and creates a pitfall for which the work arounds are vague and/or require extra care. Arguably something like the old setn/getn behavior was clearer. I don't have an exact prescription for what would need to happen to Lua to make this work, but if one could simply tell people "you need to use table.setn to set the length of the table if the table has holes"  that might help. Alternatively, this might also be addressable with a standard array userdata type once things like ipairs virtualization is in.

Side note to Mike Pall on that subject: You mentioned the possibility of teaching LuaJIT about a matrix userdata type so that it could optimize it. How hard is it to teach LuaJIT about specific userdata types?

Mark

12