Removing the last element of an ArrayBuffer

[nicola...@gmail.com]

Dear all,

I am looking for a function to remove the last element of an array
buffer with a constant time.
The documentation is not clear on wether this is the case for remove(size-1).

Is it the case? Is there another more efficient function for that?


Best regards,

Nicolas.

[HamsterofDeath]

it's a constant time operation. it just sets a reference to null and
decreases an int.

[Alex Cruise]

On Thu, Aug 30, 2012 at 12:32 PM, nicola...@gmail.com <nicola...@gmail.com> wrote:

I am looking for a function to remove the last element of an array
buffer with a constant time.

The classic method for everything-but-last is "init".  Whether this is constant-time in the case of ArrayBuffer is a different question...

In 2.9.2, ArrayBuffer.init comes from IndexedSeqOptimized:

  def init: Repr = if (length > 0) slice(0, length - 1) else super.init

It looks like ArrayBuffer's slice is also inherited from IndexedSeqOptimized:

  def slice(from: Int, until: Int): Repr = {

    val lo    = math.max(from, 0)

    val hi    = math.min(until, length)

    val elems = math.max(hi - lo, 0)

    val b     = newBuilder

    b.sizeHint(elems)

    var i = lo

    while (i < hi) {

      b += self(i)

      i += 1

    }

    b.result

  }

Sadly, init is linear in 2.9.  I just checked 2.10, and it looks the same there: https://github.com/scala/scala/blob/v2.10.0-M7/src/library/scala/collection/IndexedSeqOptimized.scala#L105

> The documentation is not clear on wether this is the case for remove(size-1).

Now, remove claims that it's linear time, but a lot of the work is done by System.arraycopy, which is really, really fast, and the rest of the work is in reduceToSize, which is linear, but your n is 1.

-0xe1a

[HamsterofDeath]

creating a new buffer with all elements except the last one is obviously much more expensive than removing the last element of an existing buffer. i was assuming the question was about the mutable way.

[Alex Cruise]

On Thu, Aug 30, 2012 at 1:15 PM, HamsterofDeath <h-s...@gmx.de> wrote:

creating a new buffer with all elements except the last one is obviously much more expensive than removing the last element of an existing buffer. i was assuming the question was about the mutable way.

Whoops, yes, you're right.  I'm going native and losing my ability to think imperatively. ;)

-0xe1a

[nicola...@gmail.com]

On Thu, Aug 30, 2012 at 9:15 PM, HamsterofDeath <h-s...@gmx.de> wrote:
> creating a new buffer with all elements except the last one is obviously
> much more expensive than removing the last element of an existing buffer. i
> was assuming the question was about the mutable way.
>

Well assumed.
Sorry for the ambiguity.