Quantcast

Length implementation

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Length implementation

Soni L.
Lua has O(logn) length and searches from the end:

$ lua
Lua 5.3.4  Copyright (C) 1994-2017 Lua.org, PUC-Rio
> t={1,2,3,4,5,6,7,8}
> for i,v in ipairs(t) do t[i]=nil end
> #t
0
> for i=8,1,-1 do t[i]=1 print(#t) t[i]=nil end
8
0
0
0
4
0
2
1

Pretty, isn't it?

I'm not sure what the time complexity of t[#t+1]=v vs t[i]=v is... I
know the latter is O(n), but the former doesn't seem to be O(n log n)...
O(n log log n) maybe?

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


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Length implementation

Pierpaolo Bernardi
On Fri, May 12, 2017 at 9:39 PM, Soni L. <[hidden email]> wrote:

> Pretty, isn't it?

Hasn't this been hashed to death several times, including 10 or 15
times in the last year?

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Length implementation

Soni L.


On 2017-05-12 07:48 PM, Pierpaolo Bernardi wrote:
> On Fri, May 12, 2017 at 9:39 PM, Soni L. <[hidden email]> wrote:
>
>> Pretty, isn't it?
> Hasn't this been hashed to death several times, including 10 or 15
> times in the last year?
>

Nah, everyone loves to complain about length but nobody likes to
appreciate it. So why not change that?

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


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Length implementation

Pierpaolo Bernardi
On Sat, May 13, 2017 at 3:39 AM, Soni L. <[hidden email]> wrote:
>
> Nah, everyone loves to complain about length but nobody likes to appreciate
> it. So why not change that?

Because everyone likes O(1) for table update and retrieval and O(log
n) for length.

Loading...