David Brady <ruby_talk / shinybit.com> writes:

> Daniel Brockman wrote:
>
>> Why not use String#shift, which is O(1)?
>
> EDIT: Daniel later redacted this to Array#shift.  My question
> remains, however.

Well, not really.  My answer is unaffected, however. :-)

> Many times when I hear an answer, I am more interested in how the
> answer was obtained than the answer itself, so that I can go find
> the answers to related questions myself.  This is a perfect example
> of this.

I'm sorry.  Had there not been a thread about this particular subject
only a week ago, I would have explained.

> How do you know Array#shift is O(1)?  I'm not challenging you; I'm
> asking because I really want to know how to find this out.

I appreciate you making this clear. :-)

> Is it documented somewhere?  Did you profile it?  Did you read the
> source code?

I did not profile it, and I don't think it's documented --- although I
would agree that it should be.

I know because Eric Mahurin posted about this a week ago in

   <20050629195248.75747.qmail / web41115.mail.yahoo.com>,

and a quick glance at the source confirms it:

   VALUE
   rb_ary_shift(ary)
       VALUE ary;
   {
       VALUE top;
   
       rb_ary_modify_check(ary);
       if (RARRAY(ary)->len == 0) return Qnil;
       top = RARRAY(ary)->ptr[0];
       ary_make_shared(ary);
       RARRAY(ary)->ptr++;		/* shift ptr */
       RARRAY(ary)->len--;
   
       return top;
   }

Note also that Array#unshift is amortized O(1); it allocates new
memory in chunks (allocating one additional byte would be insane).

Eric's thread was about similar calls, such as Array#slice!(0, n),
having needlessly large O(n) complexity.

-- 
Daniel Brockman <daniel / brockman.se>

    So really, we all have to ask ourselves:
    Am I waiting for RMS to do this?   --TTN.