Question: Time efficiency of Array <<

ruby-talk
1

Forgive the newbie-ish question. I have been playing around with Array, and discovered the << operator:

irb(main):001:0> array = [1, 2, 3, 4]
=> [1, 2, 3, 4]
irb(main):002:0> array2 = array << 5
=> [1, 2, 3, 4, 5]
irb(main):003:0> array
=> [1, 2, 3, 4, 5]
irb(main):004:0> array2
=> [1, 2, 3, 4, 5]
irb(main):005:0>

I am curious about the time & space complexity of n << operations to an array. Is it O(n^2) or is it O(n)? Is there a doubling of allocated space going on behind the scenes?

--Peter

···

--
There's neither heaven nor hell, save what we grant ourselves.
There's neither fairness nor justice, save what we grant each other.

2

Take a look at rb_ary_store in array.c...

It looks like an Array grows by half of its current capacity when an index is larger than the current capacity, but by no less than ARY_DEFAULT_SIZE (16 elements).

PGP.sig (194 Bytes)

···

On 22 Apr 2005, at 17:31, Peter Suk wrote:

Forgive the newbie-ish question. I have been playing around with Array, and discovered the << operator:

irb(main):001:0> array = [1, 2, 3, 4]
=> [1, 2, 3, 4]
irb(main):002:0> array2 = array << 5
=> [1, 2, 3, 4, 5]
irb(main):003:0> array
=> [1, 2, 3, 4, 5]
irb(main):004:0> array2
=> [1, 2, 3, 4, 5]
irb(main):005:0>

I am curious about the time & space complexity of n << operations to an array. Is it O(n^2) or is it O(n)? Is there a doubling of allocated space going on behind the scenes?

--
Eric Hodel - drbrain@segment7.net - http://segment7.net
FEC2 57F1 D465 EB15 5D6E 7C11 332A 551C 796C 9F04

3

so i guess it's since that's the worst case. note that one can avoid via

   a = Array::new(mb = 2 ** 20)
   a.size.times{|i| a[i] = method i}

unless storing nil is required...

interestingly real-world time with largish values is better for array than a
container with O(log n) performance:

   harp:~ > cat a.rb
   require 'rbtree'
   def time label
     a = Time::now.to_f
     fork{ yield } and Process::wait
     b = Time::now.to_f
     puts "#{ label } @ #{ b - a }"
   end

   n = 2 ** 20

   time('rbtree2array') do
     rbtree = RBTree::new
     n.times{|i| rbtree[i] = rand}
     array = rbtree.values
   end

   time('array <<') do
     array =
     n.times{|i| array << rand}
   end

   harp:~ > ruby a.rb
   rbtree2array @ 8.43025994300842
   array << @ 1.26344704627991

who knew. perhaps function call overhead ends up being responsible for the
difference.

-a

···

On Sat, 23 Apr 2005, Eric Hodel wrote:

--Apple-Mail-8-618338431
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset=US-ASCII; format=flowed

On 22 Apr 2005, at 17:31, Peter Suk wrote:

Forgive the newbie-ish question. I have been playing around with
Array, and discovered the << operator:

irb(main):001:0> array = [1, 2, 3, 4]
=> [1, 2, 3, 4]
irb(main):002:0> array2 = array << 5
=> [1, 2, 3, 4, 5]
irb(main):003:0> array
=> [1, 2, 3, 4, 5]
irb(main):004:0> array2
=> [1, 2, 3, 4, 5]
irb(main):005:0>

I am curious about the time & space complexity of n << operations to
an array. Is it O(n^2) or is it O(n)? Is there a doubling of
allocated space going on behind the scenes?

Take a look at rb_ary_store in array.c...

It looks like an Array grows by half of its current capacity when an
index is larger than the current capacity, but by no less than
ARY_DEFAULT_SIZE (16 elements).

--

email :: ara [dot] t [dot] howard [at] noaa [dot] gov
phone :: 303.497.6469
although gold dust is precious, when it gets in your eyes, it obstructs
your vision. --hsi-tang

===============================================================================

4

--Apple-Mail-8-618338431
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset=US-ASCII; format=flowed

Forgive the newbie-ish question. I have been playing around with
Array, and discovered the << operator:

irb(main):001:0> array = [1, 2, 3, 4]
=> [1, 2, 3, 4]
irb(main):002:0> array2 = array << 5
=> [1, 2, 3, 4, 5]
irb(main):003:0> array
=> [1, 2, 3, 4, 5]
irb(main):004:0> array2
=> [1, 2, 3, 4, 5]
irb(main):005:0>

I am curious about the time & space complexity of n << operations to
an array. Is it O(n^2) or is it O(n)? Is there a doubling of
allocated space going on behind the scenes?

Take a look at rb_ary_store in array.c...

It looks like an Array grows by half of its current capacity when an
index is larger than the current capacity, but by no less than
ARY_DEFAULT_SIZE (16 elements).

so i guess it's since that's the worst case. note that one can avoid via

  a = Array::new(mb = 2 ** 20)
  a.size.times{|i| a[i] = method i}

unless storing nil is required...

interestingly real-world time with largish values is better for array than a
container with O(log n) performance:

I think it is a bit of a stretch to call the following test
'real-world' :slight_smile: That being said, Array does perform well.

Remember that an rb-tree is O(log n) for insertion, deletion
_and_ search, and it can be treated as sparse.

  harp:~ > cat a.rb
  require 'rbtree'
  def time label
    a = Time::now.to_f
    fork{ yield } and Process::wait
    b = Time::now.to_f
    puts "#{ label } @ #{ b - a }"
  end

  n = 2 ** 20

  time('rbtree2array') do
    rbtree = RBTree::new
    n.times{|i| rbtree[i] = rand}
    array = rbtree.values
  end

  time('array <<') do
    array =
    n.times{|i| array << rand}
  end

  harp:~ > ruby a.rb
  rbtree2array @ 8.43025994300842
  array << @ 1.26344704627991

As a sidenote, you can use Benchmark for convenient timing:

require 'benchmark'
Benchmark.bm do |bench|
  # Setup
  # ...
  bench.report { # test1 }
  bench.report { # test2 }
  # ...
end

who knew. perhaps function call overhead ends up being responsible for the
difference.

In your test, it most likely suffers from allocating
memory piecemeal rather than in chunks. Not sure how
effectively one could preallocate for a tree.

-a

E

···

Le 23/4/2005, "Ara.T.Howard@noaa.gov" <Ara.T.Howard@noaa.gov> a écrit:

On Sat, 23 Apr 2005, Eric Hodel wrote:

On 22 Apr 2005, at 17:31, Peter Suk wrote:

--
template<typename duck>
void quack(duck& d) { d.quack(); }

5

I think it is a bit of a stretch to call the following test 'real-world' :slight_smile:
That being said, Array does perform well.

true true. by that i meant more that just big O analysis.

Remember that an rb-tree is O(log n) for insertion, deletion _and_ search,
and it can be treated as sparse.

oh i know - i use rbtree all the time and can't imagine why it's not in the
core. on the other hand i also have bsearch code for Arrays that makes them
O(log n) for searching in most (pre-sorted) cases.

As a sidenote, you can use Benchmark for convenient timing:

require 'benchmark'
Benchmark.bm do |bench|
# Setup
# ...
bench.report { # test1 }
bench.report { # test2 }
# ...
end

i prefer to fork and (tho i forgot in this case) kill the CG - i like
factoring out threads and eliminating any possible memory clashes.

In your test, it most likely suffers from allocating memory piecemeal rather
than in chunks. Not sure how effectively one could preallocate for a tree.

yes that's true too. i've done tests in the past comparing bdb, gperf, and
other hashing type look ups against a bsearch and found them to be quite a bit
slower. on closer analysis it turned out that, although hashing is O(1), the
call stack is so much deeper for each search as compared to a non-recursive
bsearch that it predominates - i was suprised.

thanks for the info.

cheers.

-a

···

On Sat, 23 Apr 2005, Saynatkari wrote:
--

email :: ara [dot] t [dot] howard [at] noaa [dot] gov
phone :: 303.497.6469
although gold dust is precious, when it gets in your eyes, it obstructs
your vision. --hsi-tang

===============================================================================

6

The key here is "real world." Array's trick of doubling its allocation gives us an "Amortized" time of O(2n) = O(n) which beats n insertions into a structure like a Binary Tree, which is O(n*log n).

One of the handful of truly useful things I learned from Algorithms.

A good summary for the Array trick:

  CS660: Amortized Analysis

Some more:

  http://www.cs.duke.edu/~mlittman/courses/Archive/cps130-97/lectures/lect10/node14.html

You can think of it as the "reverse Zeno's paradox."

  1 + 2 + 4 + 8 + ....
  2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(n-1) = 2^n - 1

Or visually:

X
XX
XXXX
XXXXXXXX
XXXXXXXXXXXXXXXX

You'll always be able to stack the smaller levels into the missing space on the next to the last level and still have 1 empty space left over.

So, Ruby's Array = Smalltalk's OrderedCollection.

--Peter

···

On Apr 22, 2005, at 9:48 PM, Saynatkari wrote:

I think it is a bit of a stretch to call the following test
'real-world' :slight_smile: That being said, Array does perform well.

Remember that an rb-tree is O(log n) for insertion, deletion
_and_ search, and it can be treated as sparse.

--
There's neither heaven nor hell, save what we grant ourselves.
There's neither fairness nor justice, save what we grant each other.

7

Excerpts from Ara.T.Howard@noaa.gov's mail of 22 Apr 2005 (EDT):

yes that's true too. i've done tests in the past comparing bdb,
gperf, and other hashing type look ups against a bsearch and found
them to be quite a bit slower. on closer analysis it turned out that,
although hashing is O(1), the call stack is so much deeper for each
search as compared to a non-recursive bsearch that it predominates - i
was suprised.

Just goes to show that theoretic bounds on worst case performance are
sometimes just that....

···

--
William <wmorgan-ruby-talk@masanjin.net>

8

It's actually that the upper bounds are too loose in the naive analysis. Amortized worst-case bounds on the doubling re-allocation are O(n) for n insertions, or the same O(1) per insertion as hashing. Then, it should become clear that the constant is bigger for hashing.

--Peter

···

On Apr 22, 2005, at 11:02 PM, William Morgan wrote:

Excerpts from Ara.T.Howard@noaa.gov's mail of 22 Apr 2005 (EDT):

yes that's true too. i've done tests in the past comparing bdb,
gperf, and other hashing type look ups against a bsearch and found
them to be quite a bit slower. on closer analysis it turned out that,
although hashing is O(1), the call stack is so much deeper for each
search as compared to a non-recursive bsearch that it predominates - i
was suprised.

Just goes to show that theoretic bounds on worst case performance are
sometimes just that....

--
There's neither heaven nor hell, save what we grant ourselves.
There's neither fairness nor justice, save what we grant each other.

9

Excerpts from Peter Suk's mail of 23 Apr 2005 (EDT):

>Excerpts from Ara.T.Howard@noaa.gov's mail of 22 Apr 2005 (EDT):
>>yes that's true too. i've done tests in the past comparing bdb,
>>gperf, and other hashing type look ups against a bsearch and found
>>them to be quite a bit slower. on closer analysis it turned out that,
>>although hashing is O(1), the call stack is so much deeper for each
>>search as compared to a non-recursive bsearch that it predominates - i
>>was suprised.
>
>Just goes to show that theoretic bounds on worst case performance are
>sometimes just that....

It's actually that the upper bounds are too loose in the naive
analysis. Amortized worst-case bounds on the doubling re-allocation
are O(n) for n insertions, or the same O(1) per insertion as hashing.
Then, it should become clear that the constant is bigger for hashing.

In this case he's talking about lookups and call stack depth.

···

--
William <wmorgan-ruby-talk@masanjin.net>

10

Hi all,

My question is very "simple" ... how to define an abstract class (or method) in ruby?

···

--
Paulo S Medeiros - B.Sc Student - DCC/COPPE/UFRJ - Brazil

11

Paulo Sérgio schrieb:

Hi all,

My question is very "simple" ... how to define an abstract class (or method) in ruby?

How about

a) just define a module

b)

class MyAbstractClass
    private_class_method :new
end

or c)

class MyAbstractClass
  def self.new
      raise TypeError, "I am an abstract class"
   end
end

/Christoph

12

Le 23/4/2005, "Paulo Sérgio" <psm041@ig.com.br> a écrit:\

Hi all,

My question is very "simple" ... how to define an abstract class (or
method) in ruby?

Usually one does not need an abstract class in ruby, if you are
thinking along the lines of C++ or Java. Reason for this is that
ruby is not strictly typed so any class with a conforming interface
can be used where that interface is expected. This is the concept
of 'duck-typing'.

Could you describe your situation in more detail?

Paulo S Medeiros

E

···

--
template<typename duck>
void quack(duck& d) { d.quack(); }

13

Paulo brings up a key issue. We should have a standard "subclass_responsibility" method to denote this for methods. If there is s standard idiom for Ruby, then code tools will be able to identify purely abstract classes. (Classes that have no concrete methods at all.)

But to elaborate, nothing prevents someone from putting concrete methods into an abstract class. Ruby is not about enforcement. If you want to communicate this, there is an idiom in Smalltalk where people define a class-side method isAbstract like:

---- code follows ----
class Node
  def Node.abstract?
    return self == Node
  end
end
---- end code ----

Now you can make subclasses of Node and they will automatically return false when asked "abstract?" If one of your subclasses also turns out to be abstract, just write a similar method. Now if you want to know if a class is abstract, you can just ask.

--Peter

···

On Apr 23, 2005, at 2:14 PM, Paulo Sérgio wrote:

Hi all,

My question is very "simple" ... how to define an abstract class (or method) in ruby?

--
There's neither heaven nor hell, save what we grant ourselves.
There's neither fairness nor justice, save what we grant each other.

14

Saynatkari wrote:

Le 23/4/2005, "Paulo Sérgio" <psm041@ig.com.br> a écrit:\

Hi all,

My question is very "simple" ... how to define an abstract class (or
method) in ruby?
   
Usually one does not need an abstract class in ruby, if you are
thinking along the lines of C++ or Java. Reason for this is that
ruby is not strictly typed so any class with a conforming interface
can be used where that interface is expected. This is the concept
of 'duck-typing'.

Could you describe your situation in more detail?

Hey thanks, but i figured out the ruby way :slight_smile:

···

Paulo S Medeiros
   
E

--
template<typename duck>
void quack(duck& d) { d.quack(); }

--
Paulo S Medeiros - B.Sc Student - DCC/COPPE/UFRJ - Brazil

15

Hi all, again,
I have a simple piece of code thats returning a unexpected result (to me).

def successors(state) #state is an integer array equal to, for example, [0,0,0,0]
    successorsStates = []
    for i in 0...state.length
        break if state[i] != 0
        for j in 1..4
            stateAux = state
            stateAux[i] = j
            puts stateAux.inspect #(ive put the "puts" methods just to ilustrate what is happening)
            successorsStates.push(stateAux) # i've tried "successorsStates << stateAux" and "successorsStates.concat([stateAux])" too puts successorsStates.inspect #(ive put the "puts" methods just to ilustrate what is happening)
        end
    end
    return successorsStates
end

···

=================================================================================================

I was expecting for successorsStates value:
[[1,0,0,0],[2,0,0,0],[3,0,0,0],[4,0,0,0],[0,1,0,0],[0,2,0,0],[0,3,0,0],[0,4,0,0],
  [0,0,1,0],[0,0,2,0],[0,0,3,0],[0,0,4,0],[0,0,0,1],[0,0,0,2],[0,0,0,3],[0,0,0,4]]

but it returns (look at how its concatenates)

[1, 0, 0, 0]
[[1, 0, 0, 0]]
[2, 0, 0, 0]
[[2, 0, 0, 0], [2, 0, 0, 0]]
[3, 0, 0, 0]
[[3, 0, 0, 0], [3, 0, 0, 0], [3, 0, 0, 0]]
[4, 0, 0, 0]
[[4, 0, 0, 0], [4, 0, 0, 0], [4, 0, 0, 0], [4, 0, 0, 0]]
[4, 1, 0, 0] ---*why here the result isn't [0,1,0,0], since stateAux = state and then stateAux[i] = j (state = [0,0,0,0])*
[[4, 1, 0, 0], [4, 1, 0, 0], [4, 1, 0, 0], [4, 1, 0, 0], [4, 1, 0, 0]]
[4, 2, 0, 0]
[[4, 2, 0, 0], [4, 2, 0, 0], [4, 2, 0, 0], [4, 2, 0, 0], [4, 2, 0, 0], [4, 2, 0, 0]]
[4, 3, 0, 0]
[[4, 3, 0, 0], [4, 3, 0, 0], [4, 3, 0, 0], [4, 3, 0, 0], [4, 3, 0, 0], [4, 3, 0, 0], [4, 3, 0, 0]]
[4, 4, 0, 0]
[[4, 4, 0, 0], [4, 4, 0, 0], [4, 4, 0, 0], [4, 4, 0, 0], [4, 4, 0, 0], [4, 4, 0, 0], [4, 4, 0, 0], [4, 4, 0, 0]]
[4, 4, 1, 0]
[[4, 4, 1, 0], [4, 4, 1, 0], [4, 4, 1, 0], [4, 4, 1, 0], [4, 4, 1, 0], [4, 4, 1, 0], [4, 4, 1, 0], [4, 4, 1, 0], [4, 4, 1, 0]]
[4, 4, 2, 0]
[[4, 4, 2, 0], [4, 4, 2, 0], [4, 4, 2, 0], [4, 4, 2, 0], [4, 4, 2, 0], [4, 4, 2, 0], [4, 4, 2, 0], [4, 4, 2, 0], [4, 4, 2, 0], [4, 4, 2, 0]]
[4, 4, 3, 0]
[[4, 4, 3, 0], [4, 4, 3, 0], [4, 4, 3, 0], [4, 4, 3, 0], [4, 4, 3, 0], [4, 4, 3, 0], [4, 4, 3, 0], [4, 4, 3, 0], [4, 4, 3, 0], [4, 4, 3, 0], [4, 4, 3, 0]]
[4, 4, 4, 0]
[[4, 4, 4, 0], [4, 4, 4, 0], [4, 4, 4, 0], [4, 4, 4, 0], [4, 4, 4, 0], [4, 4, 4, 0], [4, 4, 4, 0], [4, 4, 4, 0], [4, 4, 4, 0], [4, 4, 4, 0], [4, 4, 4, 0], [4, 4, 4, 0]]
[4, 4, 4, 1]
[[4, 4, 4, 1], [4, 4, 4, 1], [4, 4, 4, 1], [4, 4, 4, 1], [4, 4, 4, 1], [4, 4, 4, 1], [4, 4, 4, 1], [4, 4, 4, 1], [4, 4, 4, 1], [4, 4, 4, 1], [4, 4, 4, 1], [4, 4, 4, 1], [4, 4, 4, 1]]
[4, 4, 4, 2]
[[4, 4, 4, 2], [4, 4, 4, 2], [4, 4, 4, 2], [4, 4, 4, 2], [4, 4, 4, 2], [4, 4, 4, 2], [4, 4, 4, 2], [4, 4, 4, 2], [4, 4, 4, 2], [4, 4, 4, 2], [4, 4, 4, 2], [4, 4, 4, 2], [4, 4, 4, 2], [4, 4, 4, 2]]
[4, 4, 4, 3]
[[4, 4, 4, 3], [4, 4, 4, 3], [4, 4, 4, 3], [4, 4, 4, 3], [4, 4, 4, 3], [4, 4, 4, 3], [4, 4, 4, 3], [4, 4, 4, 3], [4, 4, 4, 3], [4, 4, 4, 3], [4, 4, 4, 3], [4, 4, 4, 3], [4, 4, 4, 3], [4, 4, 4, 3], [4, 4, 4, 3]]
[4, 4, 4, 4]
*[[4, 4, 4, 4], [4, 4, 4, 4], [4, 4, 4, 4], [4, 4, 4, 4], [4, 4, 4, 4], [4, 4, 4, 4], [4, 4, 4, 4], [4, 4, 4, 4], [4, 4, 4, 4], [4, 4, 4, 4], [4, 4, 4, 4], [4, 4, 4, 4], [4, 4, 4, 4], [4, 4, 4, 4], [4, 4, 4, 4], [4, 4, 4, 4]] *this is the WRONG final state of successorsStates**

16

Paulo Sérgio wrote:

def successors(state) #state is an integer array equal to, for
example, [0,0,0,0]
   successorsStates =
   for i in 0...state.length
       break if state[i] != 0
       for j in 1..4
           stateAux = state

stateAux = state.dup

···

--
Florian Frank

17

You post using the "Reply" function of your Thunderbird.
This makes it and its answers appear within another thread
everywhere thread view is turned on.

Please use the "New Message" Button instead of "Reply" on a
mail your post will have nothing to do with. Thanks.

Probably you like to turn on the thread view feature of your
Thunderbird, too.

Bertram

···

Am Sonntag, 24. Apr 2005, 07:06:48 +0900 schrieb Paulo Sérgio:

Subject: Re: What im doing WRONG?!?!?!

--
Bertram Scharpf
Stuttgart, Deutschland/Germany
http://www.bertram-scharpf.de

18

Florian Frank wrote:

Paulo Sérgio wrote:

def successors(state) #state is an integer array equal to, for
example, [0,0,0,0]
  successorsStates =
  for i in 0...state.length
      break if state[i] != 0
      for j in 1..4
          stateAux = state
   
stateAux = state.dup

Yeah, thanks, it really worked. The dup method creates a new copy of the object, correct?
But i can't figure out why without dup it not worked since state variable never change.

···

--
Paulo S Medeiros - B.Sc Student - DCC/COPPE/UFRJ - Brazil

19

Yeah, thanks, it really worked. The dup method creates a new copy of the
object, correct?

yep

But i can't figure out why without dup it not worked since state
variable never change.

stateAux changes, and because stateAux = state, state does change.

Douglas

···

On 4/23/05, Paulo Sérgio <psm041@ig.com.br> wrote:

20

Douglas Livingstone wrote:

···

On 4/23/05, Paulo Sérgio <psm041@ig.com.br> wrote:

Yeah, thanks, it really worked. The dup method creates a new copy of the
object, correct?
   
yep

But i can't figure out why without dup it not worked since state
variable never change.

stateAux changes, and because stateAux = state, state does change.

Douglas

of cooouuurrsee ... how i cant see that :slight_smile:
thanks for the help!

--
Paulo S Medeiros - B.Sc Student - DCC/COPPE/UFRJ - Brazil