A very basic thing I don't get

classic Classic list List threaded Threaded
51 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Philippe Lhoste
On 01/10/2011 20:43, Stefan Reich wrote:
> Putting lists and maps in one structure is a little weird. It tends to
> favor the maps I'd say. Arrays, technically, are usually things that
> take a linear space in memory. Processors understand arrays easily.
> However, the Lua structure for arrays is more like a map with
> integers. It's a really different thing, and sometimes it shows in its
> handling.

Pure linear arrays in Lua are implemented with just a linear space in
memory.

> I find the relation between nil and lists also confusing.

As often advised in the list, just don't put nils in an array if you
don't want holes. You can use any marker value if you want to indicate
the absence of value. The logic is the same (I never use nils as false
value like 'if something then' when something isn't explicitly a
boolean, anyway) so in general you keep a consistent data structure like
you wish.

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


Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

steve donovan
On Sun, Oct 2, 2011 at 9:58 AM, Philippe Lhoste <[hidden email]> wrote:
> Pure linear arrays in Lua are implemented with just a linear space in
> memory.

It's a bit like the famous wave/particle duality of quantum mechanics;
is an electron a particle (defined position, uncertain momentum) or a
wave (defined momentum, uncertain position)? The answer of course is
neither.

A common conceptual mistake with Lua tables is to see them as arrays
or hash maps. They have limits where they behave like one or the
other, sure, but thinking of them as _either_ a linear O(1) structure
_or_ a O(N log N) map is a mistake. In practice they are implemented
as having a hash-part and an array-part, but this is an implementation
detail and it isn't always obvious in what part a key/value is kept.

One of the casualties of this flexibility is the length operator #
which is only useful for tables used strictly as arrays.

steve d.

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Roberto Ierusalimschy
> [...] but thinking of them as _either_ a linear O(1) structure
> _or_ a O(N log N) map is a mistake. [...]

Just a detail: both arrays and maps are O(1) in space, and both are
O(1) in time for the average case.

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Axel Kittenberger
> Just a detail: both arrays and maps are O(1) in space, and both are
> O(1) in time for the average case.

And this equivalence is IMHO essential. In the past I've read one or
the other message saying what O() a specific function/interface has is
some  (undocumented) "implementation detail". However, that must not
be, O() anything is never a "detail" for any serious coder working
with either larger sets of data or caring about performance in
general.

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Pascal J. Bourguignon
In reply to this post by Roberto Ierusalimschy
Roberto Ierusalimschy <[hidden email]> writes:

>> [...] but thinking of them as _either_ a linear O(1) structure
>> _or_ a O(N log N) map is a mistake. [...]
>
> Just a detail: both arrays and maps are O(1) in space, and both are

So when I add one million entries to an array it still takes the same
space as when I have only one entry.  Interesting.  Perhaps I'll have an
entry for each star in the universe...


> O(1) in time for the average case.


--
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.


Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

David Kastrup
"Pascal J. Bourguignon" <[hidden email]> writes:

> Roberto Ierusalimschy <[hidden email]> writes:
>
>>> [...] but thinking of them as _either_ a linear O(1) structure
>>> _or_ a O(N log N) map is a mistake. [...]
>>
>> Just a detail: both arrays and maps are O(1) in space, and both are
>
> So when I add one million entries to an array it still takes the same
> space as when I have only one entry.  Interesting.  Perhaps I'll have an
> entry for each star in the universe...

Where else but in the same space would the stars be?

--
David Kastrup


Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Dirk Laurie
In reply to this post by Pascal J. Bourguignon
On Sun, Oct 02, 2011 at 11:33:50PM +0200, Pascal J. Bourguignon wrote:

> Roberto Ierusalimschy <[hidden email]> writes:
>
> >> [...] but thinking of them as _either_ a linear O(1) structure
> >> _or_ a O(N log N) map is a mistake. [...]
> >
> > Just a detail: both arrays and maps are O(1) in space, and both are
>
> So when I add one million entries to an array it still takes the same
> space as when I have only one entry.  Interesting.  Perhaps I'll have an
> entry for each star in the universe...
>

For the sake of the poor newbies who do not realize that Pascal is
being sarcastic: Roberto means "O(1) per item", of course.

D.

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Axel Kittenberger
> For the sake of the poor newbies who do not realize that Pascal is
> being sarcastic: Roberto means "O(1) per item", of course.

In the same sake, expressing O() for space hardly makes sense. I don't
know any datastructure where this isn't 1 and suppose any other than 1
would be ridiculous. Expressed as constant factor I estimate Lua
varies between 1-1.5 (everything in array part, maybe add 1,5 for Lua
type headers), and 4 (*1,5) (everything in hash part, 2 for storing
keys, 2 for the hashtable just having load of 50%).

Reply | Threaded
Open this post in threaded view
|

RE: A very basic thing I don't get

Julien Duminil
> > For the sake of the poor newbies who do not realize that Pascal is
> > being sarcastic: Roberto means "O(1) per item", of course.
>
> In the same sake, expressing O() for space hardly makes sense. I don't
> know any datastructure where this isn't 1 and suppose any other than 1
> would be ridiculous.

Storing a sparse matrix can be done in O(rows*cols) or in O(n) (where n is the number of entries).


Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Pierpaolo Bernardi
In reply to this post by Axel Kittenberger
On Mon, Oct 3, 2011 at 10:34, Axel Kittenberger <[hidden email]> wrote:
>> For the sake of the poor newbies who do not realize that Pascal is
>> being sarcastic: Roberto means "O(1) per item", of course.
>
> In the same sake, expressing O() for space hardly makes sense. I don't
> know any datastructure where this isn't 1 and suppose any other than 1
> would be ridiculous.

So, say, you never heard of trees, which btw are ridiculous data
structures.  8^)

P.

Reply | Threaded
Open this post in threaded view
|

Why take out remaining arguments when not last (was: A very basic thing I don't get)

Cuero Bugot-2
Thanks guys for raising this very flammable subject that is table as list and holes, etc...
Once again few where able to divert the subject :).
I love Lua table approach and it's well defined # operator (that was for the troll part).


That said I was very interested in the first question: why the returned values of called function are trimmed to one value, unless it is the last one. I mean: I would like to understand the rational behind it.

If the answer is 'limit weird behavior' then it appears that it might seem that this trimming is also considered weird by some.
I would think that trimming is actually redundant with the () operator that does the job as well.

Would not it be plainer to actually not trim the extra returned values unless asked for it with the () operator ?


So:
(1) t = { getvalues(), "some", "other", "values"}
would be different from
(2) t = { (getvalues()), "some", "other", "values"}

(1) would not trim returned values of getvalues() function, (2) would do it as specified by the embracing ().


Note: changing that would be a major incompatibility and would certainly break a lot of existing code. Not sure is this is easily catchable before hand...

Cuero



Reply | Threaded
Open this post in threaded view
|

Re: Why take out remaining arguments when not last (was: A very basic thing I don't get)

steve donovan
On Mon, Oct 3, 2011 at 11:43 AM, Cuero Bugot <[hidden email]> wrote:
> Would not it be plainer to actually not trim the extra returned values unless asked for it with the () operator ?

Oh yes, but make it explicit, e.g:

http://lua-users.org/lists/lua-l/2009-08/msg00242.html

> Note: changing that would be a major incompatibility and would certainly break a lot of existing code. Not sure is this is easily catchable before hand...

That's the problem; better to have an explicit operator.

steve d.

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Axel Kittenberger
In reply to this post by Pierpaolo Bernardi

> So, say, you never heard of trees, which btw are ridiculous data
> structures.  8^)

They have O(1) per item for space, a tree which load would reduce even by O(log(n)) would be ridiculous.

Reply | Threaded
Open this post in threaded view
|

Re: Why take out remaining arguments when not last

David Kastrup
In reply to this post by Cuero Bugot-2
Cuero Bugot <[hidden email]> writes:

> Thanks guys for raising this very flammable subject that is table as
> list and holes, etc...
> Once again few where able to divert the subject :).
> I love Lua table approach and it's well defined # operator (that was
> for the troll part).
>
>
> That said I was very interested in the first question: why the
> returned values of called function are trimmed to one value, unless it
> is the last one. I mean: I would like to understand the rational
> behind it.

They are not only _trimmed_ to one value, but also _extended_ to one
value if necessary.

If I write
a,b,c = f(), g(), h()
do I want to think about whether a will be set to the result of h()
because f and g choose to return nothing?  Or c be set to the value of
g() because a returned nil and an error string?

> If the answer is 'limit weird behavior' then it appears that it might
> seem that this trimming is also considered weird by some.

It is "limit", not "eliminate".

--
David Kastrup


Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Pierpaolo Bernardi
In reply to this post by Axel Kittenberger
On Mon, Oct 3, 2011 at 12:02, Axel Kittenberger <[hidden email]> wrote:
>> So, say, you never heard of trees, which btw are ridiculous data
>> structures.  8^)
>
> They have O(1) per item for space, a tree which load would reduce even by
> O(log(n)) would be ridiculous.

You are right that some tree representation are O(1) per item.
Others, perfectly sensible representations, are not.

E.g. representations in which not every node contains an item,
an example of which is the representation of sexpr as usually
implemented in lisp-like languages.

Other examples are common in functional programming, where
the overhead in space is compensated by other nice properties.

P.

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Axel Kittenberger

Just because not every slot is filled doesn't yet mean that O() isn't 1.Eg a btree will never go below ~50% load.

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

David Kastrup
Axel Kittenberger <[hidden email]> writes:

> Just because not every slot is filled doesn't yet mean that O() isn't
> 1.Eg a btree will never go below ~50% load.

Radix trees fan out according to the size of the data, not just its
amount.  Unbalanced trees can have less that 50% load.

--
David Kastrup


Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

Pierpaolo Bernardi
In reply to this post by Axel Kittenberger
On Mon, Oct 3, 2011 at 12:30, Axel Kittenberger <[hidden email]> wrote:
> Just because not every slot is filled doesn't yet mean that O() isn't 1.Eg a
> btree will never go below ~50% load.

So btrees are O(1). Other structures are not.

Trees where information is kept only at the terminal leaves are a fairly
common components of many data structures. These are not O(1).

(Since this is not anymore lua related I won't reply on list, unless
the topic can
be steered again in the lua direction.
I will be happy to continue in private).

Cheers
P.

Reply | Threaded
Open this post in threaded view
|

Re: A very basic thing I don't get

David Kastrup
Pierpaolo Bernardi <[hidden email]> writes:

> On Mon, Oct 3, 2011 at 12:30, Axel Kittenberger <[hidden email]> wrote:
>> Just because not every slot is filled doesn't yet mean that O() isn't 1.Eg a
>> btree will never go below ~50% load.
>
> So btrees are O(1). Other structures are not.
>
> Trees where information is kept only at the terminal leaves are a fairly
> common components of many data structures. These are not O(1).

If they have a minimum fanout f>1 (like trees where nodes with one or no
child are collapsed), they are.  It is often possible to make it so, but
by no means mandatory.

--
David Kastrup


Reply | Threaded
Open this post in threaded view
|

RE: Why take out remaining arguments when not last

Cuero Bugot-2
In reply to this post by David Kastrup
> a,b,c = f(), g(), h()
> do I want to think about whether a will be set to the result of h()
> because f and g choose to return nothing?  Or c be set to the value of
> g() because a returned nil and an error string?
>
> It is "limit", not "eliminate".

Well if that's really what you wan to do, they you would write:

a,b,c = (f()), (g()), (h())

And then "limit" would indeed become "eliminate" (the language does what to tell it to do, no more, no less)

123