Re: Speed of # operator (Was: ipairs in Lua 5.3.0-alpha)

[Coda Highland <chighland@...>]

On Fri, Aug 15, 2014 at 8:35 AM, Anton Titov <anton@titov.net> wrote:
> On 15.08.2014 17:52, Coda Highland wrote:
>>
>> On Fri, Aug 15, 2014 at 5:01 AM, Roberto Ierusalimschy
>> <roberto@inf.puc-rio.br> wrote:
>>
>>> This is not correct, as Dirk already pointed out. (You do not move n/2
>>> elements log(n) times; you move 1 element, then 2 elements, then 4
>>> elements, etc.  The lenght of that sequence is log(n), but you should
>>> not mulitply that by n.)
>>>
>>> -- Roberto
>>
>> To clarify -- the sum of that sequence is:
>>
>> sum[i=0..log_2(n)](2^i)
>>
>> Which, plugged into WolframAlpha, yields 2n-1, which is O(n).
>>
>> That is, in the worst case scenario where you're copying the contents
>> every time you have to expand, it's still just O(n) total copies!
>>
>> /s/ Adam
>>
>>
>
> You are both right. I somehow assumed that if you scan the array log(n) of
> times, this makes n*log(n), but since the array is growing
> it seems to be 2*n.
>
> Best,
> Anton
>

This is exactly the rationale for exponential growth in a dynamic
array implementation. Other growth schemes do worse.

/s/ Adam