# Dynamic array?

**URL:** <https://rubytalk.org/t/dynamic-array/56289>\
**Category:** ruby-talk\
**Created:** [19 November 2009 13:06 UTC](https://rubytalk.org/t/dynamic-array/56289 "2009-11-19T13:06:07Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![Freak\_Guard](https://avatars.discourse-cdn.com/v4/letter/f/e8c25b/32.png) [@Freak\_Guard](https://rubytalk.org/u/Freak_Guard)\
**Post date:** [19 November 2009 13:06 UTC](https://rubytalk.org/t/dynamic-array/56289/1 "2009-11-19T13:06:07Z")

</div>

I'd like to store 2d-data into an dynamic Array. The Matrix class got  
the problem of being static sized and the other solution does not work:

You can pass a block to Hash#new which gets called if the key does not  
exist

> > hsh = Hash.new {}

=\> {}

> > hsh[3]

=\>

But this does not seem to work with Arrays...

> > ary = Array.new {}

=\>

> > ary[2]

=\> nil

Grettings  
FreakGuard

> **···**
>
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![Robert\_K1](https://yyz1.discourse-cdn.com/flex029/user_avatar/rubytalk.org/robert_k1/32/1830_2.png) [@Robert\_K1](https://rubytalk.org/u/Robert_K1)\
**Post date:** [19 November 2009 14:02 UTC](https://rubytalk.org/t/dynamic-array/56289/2 "2009-11-19T14:02:14Z")

</div>

So basically you need a lazy Matrix? Or do you need a matrix which  
accepts arbitrary indexes?

In 1.8.7 and newer this is as easy as

class LazyM  
&nbsp;&nbsp;def initialize(default = nil)  
&nbsp;&nbsp;&nbsp;&nbsp;@h = Hash.new(default)  
&nbsp;&nbsp;end

&nbsp;&nbsp;def (x,y)  
&nbsp;&nbsp;&nbsp;&nbsp;@h[[x,y]]  
&nbsp;&nbsp;end

&nbsp;&nbsp;def =(x,y,z)  
&nbsp;&nbsp;&nbsp;&nbsp;@h[[x,y]]=z  
&nbsp;&nbsp;end

&nbsp;&nbsp;def clear  
&nbsp;&nbsp;&nbsp;&nbsp;@h.clear  
&nbsp;&nbsp;end  
end

Kind regards

robert

> **···**
>
> 2009/11/19 Freak Guard \<freakguard@gmail.com\>:
> 
> > I'd like to store 2d-data into an dynamic Array. The Matrix class got  
> > the problem of being static sized and the other solution does not work:
> > 
> > You can pass a block to Hash#new which gets called if the key does not  
> > exist
> > 
> > > > hsh = Hash.new {}
> > 
> > =\> {}
> > 
> > > > hsh[3]
> > 
> > =\>
> > 
> > But this does not seem to work with Arrays...
> > 
> > > > ary = Array.new {}
> > 
> > =\>
> > 
> > > > ary[2]
> > 
> > =\> nil
> 
> --  
> remember.guy do |as, often| as.you\_can - without end  
> [http://blog.rubybestpractices.com/](http://blog.rubybestpractices.com/)

---

<div class="post-metadata">

**Author:** ![Marnen\_Laibow-Koser](https://avatars.discourse-cdn.com/v4/letter/m/a587f6/32.png) [@Marnen\_Laibow-Koser](https://rubytalk.org/u/Marnen_Laibow-Koser)\
**Post date:** [19 November 2009 14:02 UTC](https://rubytalk.org/t/dynamic-array/56289/3 "2009-11-19T14:02:14Z")

</div>

Freak Guard wrote:

> I'd like to store 2d-data into an dynamic Array. The Matrix class got  
> the problem of being static sized and the other solution does not work:
> 
> You can pass a block to Hash#new which gets called if the key does not  
> exist
> 
> > > hsh = Hash.new {}
> 
> =\> {}
> 
> > > hsh[3]
> 
> =\>
> 
> But this does not seem to work with Arrays...
> 
> > > ary = Array.new {}
> 
> =\>
> 
> > > ary[2]
> 
> =\> nil
> 
> Grettings  
> FreakGuard

So reopen, extend, or subclass Array to get the desired behavior.  
What's the problem?

Best,

> **···**
>
> --  
> Marnen Laibow-Koser  
> [http://www.marnen.org](http://www.marnen.org)  
> marnen@marnen.org  
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![Marnen\_Laibow-Koser](https://avatars.discourse-cdn.com/v4/letter/m/a587f6/32.png) [@Marnen\_Laibow-Koser](https://rubytalk.org/u/Marnen_Laibow-Koser)\
**Post date:** [19 November 2009 14:49 UTC](https://rubytalk.org/t/dynamic-array/56289/4 "2009-11-19T14:49:07Z")

</div>

Freak Guard wrote:

> I'd like to store 2d-data into an dynamic Array. The Matrix class got  
> the problem of being static sized and the other solution does not work:
> 
> You can pass a block to Hash#new which gets called if the key does not  
> exist
> 
> > > hsh = Hash.new {}
> 
> =\> {}
> 
> > > hsh[3]
> 
> =\>
> 
> But this does not seem to work with Arrays...
> 
> > > ary = Array.new {}
> 
> =\>
> 
> > > ary[2]
> 
> =\> nil
> 
> Grettings  
> FreakGuard

Hmmm...another approach:

class DynamicArray \< Hash  
&nbsp;&nbsp;attr\_reader :length

&nbsp;&nbsp;def initialize(length)  
&nbsp;&nbsp;&nbsp;&nbsp;@length = length  
&nbsp;&nbsp;&nbsp;&nbsp;super() {}  
&nbsp;&nbsp;end

&nbsp;&nbsp;def =(i, value)  
&nbsp;&nbsp;&nbsp;&nbsp;super  
&nbsp;&nbsp;&nbsp;&nbsp;@length = [i + 1, length].max  
&nbsp;&nbsp;end

&nbsp;&nbsp;def to\_a  
&nbsp;&nbsp;&nbsp;&nbsp;(0..length).to\_a.collect{|i| self[i]}  
&nbsp;&nbsp;end

&nbsp;&nbsp;def each(&block)  
&nbsp;&nbsp;&nbsp;&nbsp;self.to\_a.each block  
&nbsp;&nbsp;end  
end

...and delegate everything else to self.to\_a.

Best,

> **···**
>
> --  
> Marnen Laibow-Koser  
> [http://www.marnen.org](http://www.marnen.org)  
> marnen@marnen.org
> 
> &nbsp;&nbsp;end
> 
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![Freak\_Guard](https://avatars.discourse-cdn.com/v4/letter/f/e8c25b/32.png) [@Freak\_Guard](https://rubytalk.org/u/Freak_Guard)\
**Post date:** [19 November 2009 14:19 UTC](https://rubytalk.org/t/dynamic-array/56289/5 "2009-11-19T14:19:39Z")

</div>

> So reopen, extend, or subclass Array to get the desired behavior.  
> What's the problem?

class DefaultArray \< Array

&nbsp;&nbsp;attr\_accessor :default\_value

&nbsp;&nbsp;def initialize  
&nbsp;&nbsp;&nbsp;&nbsp;super  
&nbsp;&nbsp;&nbsp;&nbsp;@default\_value = nil  
&nbsp;&nbsp;end

&nbsp;&nbsp;def (idx)  
&nbsp;&nbsp;&nbsp;&nbsp;super || @default\_value  
&nbsp;&nbsp;end  
end

... and writing all the iterators I need which will be dead slow I  
assume 😕

Greetings  
FreakGuard

> **···**
>
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![Freak\_Guard](https://avatars.discourse-cdn.com/v4/letter/f/e8c25b/32.png) [@Freak\_Guard](https://rubytalk.org/u/Freak_Guard)\
**Post date:** [19 November 2009 15:59 UTC](https://rubytalk.org/t/dynamic-array/56289/6 "2009-11-19T15:59:14Z")

</div>

Marnen Laibow-Koser wrote:

> Hmmm...another approach:
> 
> class DynamicArray \< Hash  
> &nbsp;&nbsp;attr\_reader :length
> 
> &nbsp;&nbsp;def initialize(length)  
> &nbsp;&nbsp;&nbsp;&nbsp;@length = length  
> &nbsp;&nbsp;&nbsp;&nbsp;super() {}  
> &nbsp;&nbsp;end

... which doesn't fulfull the inital target of to not have to set the  
length static 🙂

> &nbsp;&nbsp;def =(i, value)  
> &nbsp;&nbsp;&nbsp;&nbsp;super  
> &nbsp;&nbsp;&nbsp;&nbsp;@length = [i + 1, length].max  
> &nbsp;&nbsp;end
> 
> &nbsp;&nbsp;def to\_a  
> &nbsp;&nbsp;&nbsp;&nbsp;(0..length).to\_a.collect{|i| self[i]}  
> &nbsp;&nbsp;end
> 
> &nbsp;&nbsp;def each(&block)  
> &nbsp;&nbsp;&nbsp;&nbsp;self.to\_a.each block  
> &nbsp;&nbsp;end  
> end
> 
> ...and delegate everything else to self.to\_a.

Probably I'll just implement length as a method and it should work.

> **···**
>
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![Freak\_Guard](https://avatars.discourse-cdn.com/v4/letter/f/e8c25b/32.png) [@Freak\_Guard](https://rubytalk.org/u/Freak_Guard)\
**Post date:** [19 November 2009 16:00 UTC](https://rubytalk.org/t/dynamic-array/56289/7 "2009-11-19T16:00:28Z")

</div>

Robert Klemme wrote:

> **···**
>
> > 2009/11/19 Freak Guard \<freakguard@gmail.com\>:
> > 
> > So basically you need a lazy Matrix? Or do you need a matrix which  
> > accepts arbitrary indexes?
> > 
> > In 1.8.7 and newer this is as easy as
> > 
> > class LazyM  
> > ...  
> > end
> 
> Interessting approach. I'll try that one too, let's see which one  
> performs better 🙂  
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![Robert\_K1](https://yyz1.discourse-cdn.com/flex029/user_avatar/rubytalk.org/robert_k1/32/1830_2.png) [@Robert\_K1](https://rubytalk.org/u/Robert_K1)\
**Post date:** [19 November 2009 16:17 UTC](https://rubytalk.org/t/dynamic-array/56289/8 "2009-11-19T16:17:50Z")

</div>

What are you trying to achieve with this? As far as I can see you are  
mimicking Array behavior with a Hash. So you have created a sparse  
array but not a two dimensional array - which was what the OP wanted  
if I understand him properly.

As a side note: I'd rather delegate to instead of inherit from Hash.  
The DynamicArray is not a Hash. For example, method #size remains in  
the interface which might lead to surprises.

Kind regards

robert

> **···**
>
> 2009/11/19 Marnen Laibow-Koser \<marnen@marnen.org\>:
> 
> > Freak Guard wrote:
> > 
> > > I'd like to store 2d-data into an dynamic Array. The Matrix class got  
> > > the problem of being static sized and the other solution does not work:
> > > 
> > > You can pass a block to Hash#new which gets called if the key does not  
> > > exist
> > > 
> > > > > hsh = Hash.new {}
> > > 
> > > =\> {}
> > > 
> > > > > hsh[3]
> > > 
> > > =\>
> > > 
> > > But this does not seem to work with Arrays...
> > > 
> > > > > ary = Array.new {}
> > > 
> > > =\>
> > > 
> > > > > ary[2]
> > > 
> > > =\> nil
> > > 
> > > Grettings  
> > > FreakGuard
> > 
> > Hmmm...another approach:
> > 
> > class DynamicArray \< Hash  
> > attr\_reader :length
> > 
> > def initialize(length)  
> > @length = length  
> > super() {}  
> > end
> > 
> > def =(i, value)  
> > super  
> > @length = [i + 1, length].max  
> > end
> > 
> > def to\_a  
> > (0..length).to\_a.collect{|i| self[i]}  
> > end
> > 
> > def each(&block)  
> > self.to\_a.each block  
> > end  
> > end
> > 
> > ...and delegate everything else to self.to\_a.
> 
> --  
> remember.guy do |as, often| as.you\_can - without end  
> [http://blog.rubybestpractices.com/](http://blog.rubybestpractices.com/)

---

<div class="post-metadata">

**Author:** ![Marnen\_Laibow-Koser](https://avatars.discourse-cdn.com/v4/letter/m/a587f6/32.png) [@Marnen\_Laibow-Koser](https://rubytalk.org/u/Marnen_Laibow-Koser)\
**Post date:** [19 November 2009 14:31 UTC](https://rubytalk.org/t/dynamic-array/56289/9 "2009-11-19T14:31:51Z")

</div>

Freak Guard wrote:

> > So reopen, extend, or subclass Array to get the desired behavior.  
> > What's the problem?
> 
> class DefaultArray \< Array
> 
> &nbsp;&nbsp;attr\_accessor :default\_value
> 
> &nbsp;&nbsp;def initialize  
> &nbsp;&nbsp;&nbsp;&nbsp;super  
> &nbsp;&nbsp;&nbsp;&nbsp;@default\_value = nil  
> &nbsp;&nbsp;end
> 
> &nbsp;&nbsp;def (idx)  
> &nbsp;&nbsp;&nbsp;&nbsp;super || @default\_value  
> &nbsp;&nbsp;end  
> end
> 
> ... and writing all the iterators I need which will be dead slow I  
> assume 😕

I'm not sure you'll need to rewrite the iterators. You may need to  
store length separately, though, since counting the elements won't do  
the trick.

> Greetings  
> FreakGuard

Best,

> **···**
>
> --  
> Marnen Laibow-Koser  
> [http://www.marnen.org](http://www.marnen.org)  
> marnen@marnen.org  
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![Shot\_Piotr\_Szotkowsk](https://avatars.discourse-cdn.com/v4/letter/s/c5a1d2/32.png) [@Shot\_Piotr\_Szotkowsk](https://rubytalk.org/u/Shot_Piotr_Szotkowsk)\
**Post date:** [19 November 2009 14:35 UTC](https://rubytalk.org/t/dynamic-array/56289/10 "2009-11-19T14:35:38Z")

</div>

Freak Guard:

> class DefaultArray \< Array

> &nbsp;&nbsp;attr\_accessor :default\_value

> &nbsp;&nbsp;def initialize  
> &nbsp;&nbsp;&nbsp;&nbsp;super  
> &nbsp;&nbsp;&nbsp;&nbsp;@default\_value = nil  
> &nbsp;&nbsp;end

> &nbsp;&nbsp;def (idx)  
> &nbsp;&nbsp;&nbsp;&nbsp;super || @default\_value  
> &nbsp;&nbsp;end  
> end

> ... and writing all the iterators I need

You can always delegate them (or, as  
suggested, reopen Array or extend it).

> which will be dead slow I assume 😕

Don’t assume, benchmark it (it’s fairly trivial to do).

You can see the following thread for inspiration – and  
an example when a Hash-based custom set is (or at least  
seems to be) sometimes faster than the underlying Hash:  
[http://groups.google.com/group/ruby-talk-google/browse\_thread/thread/478a5ddded16da09](http://groups.google.com/group/ruby-talk-google/browse_thread/thread/478a5ddded16da09)

— Shot

> **···**
>
> --  
> If you program and want any longevity to your work, make a game. All  
> else recycles, but people rewrite architectures to keep games alive.  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[\_why]

---

<div class="post-metadata">

**Author:** ![Marnen\_Laibow-Koser](https://avatars.discourse-cdn.com/v4/letter/m/a587f6/32.png) [@Marnen\_Laibow-Koser](https://rubytalk.org/u/Marnen_Laibow-Koser)\
**Post date:** [19 November 2009 16:53 UTC](https://rubytalk.org/t/dynamic-array/56289/11 "2009-11-19T16:53:57Z")

</div>

Robert Klemme wrote:

> > > =\>
> > 
> > �def =(i, value)  
> > �end  
> > end
> > 
> > ...and delegate everything else to self.to\_a.
> 
> What are you trying to achieve with this? As far as I can see you are  
> mimicking Array behavior with a Hash. So you have created a sparse  
> array but not a two dimensional array - which was what the OP wanted  
> if I understand him properly.

Right. The idea was to create a sparse one-dimensional array for the  
major axis, then populate it with (sparse or not) one-dimensional arrays  
for the minor axis as necessary. Perhaps I should have explained that  
in the first place. 🙂

I was trying to avoid the pitfall of your LazyM solution, which appears  
to use matrix[i, j] instead of matrix[i][j] to address a cell. To my  
mind this violates POLS.

> As a side note: I'd rather delegate to instead of inherit from Hash.  
> The DynamicArray is not a Hash. For example, method #size remains in  
> the interface which might lead to surprises.

Probably not a bad idea. This was seat-of-the-pants code. 🙂

> Kind regards
> 
> robert

Best,

> **···**
>
> > 2009/11/19 Marnen Laibow-Koser \<marnen@marnen.org\>:
> 
> --  
> Marnen Laibow-Koser  
> [http://www.marnen.org](http://www.marnen.org)  
> marnen@marnen.org  
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![Robert\_K1](https://yyz1.discourse-cdn.com/flex029/user_avatar/rubytalk.org/robert_k1/32/1830_2.png) [@Robert\_K1](https://rubytalk.org/u/Robert_K1)\
**Post date:** [20 November 2009 07:25 UTC](https://rubytalk.org/t/dynamic-array/56289/12 "2009-11-20T07:25:10Z")

</div>

> Robert Klemme wrote:

> > What are you trying to achieve with this? As far as I can see you are  
> > mimicking Array behavior with a Hash. So you have created a sparse  
> > array but not a two dimensional array - which was what the OP wanted  
> > if I understand him properly.
> 
> Right. The idea was to create a sparse one-dimensional array for the major axis, then populate it with (sparse or not) one-dimensional arrays for the minor axis as necessary. Perhaps I should have explained that in the first place. 🙂
> 
> I was trying to avoid the pitfall of your LazyM solution, which appears to use matrix[i, j] instead of matrix[i][j] to address a cell. To my mind this violates POLS.

I don't find that particularly violating POLS. If you want Arrays nested in a Hash you can do this as well

irb(main):001:0\> matrix = Hash.new {|h,k| h[k] = }  
=\> {}  
irb(main):002:0\> matrix[10][2]=13  
=\> 13  
irb(main):003:0\> matrix[10][2]  
=\> 13  
irb(main):004:0\> matrix  
=\> {10=\>[nil, nil, 13]}  
irb(main):005:0\>

However, this has bad memory characteristics, especially with large second index values.

You could of course instead do

irb(main):005:0\> matrix = Hash.new {|h,k| h[k] = {}}  
=\> {}  
irb(main):006:0\> matrix[10][2]  
=\> nil  
irb(main):007:0\> matrix[10][2]=13  
=\> 13  
irb(main):008:0\> matrix[10][2]  
=\> 13  
irb(main):009:0\> matrix  
=\> {10=\>{2=\>13}}  
irb(main):010:0\>

I tend to believe that my solution with a single Hash and arrays as indexes is more efficient although I cannot prove it right now. Personally I would prefer having a single object that encapsulates the storage mechanism away (so you can even change it later). That's more difficult with the addressing scheme (two sets of brackets) you seem to favor:

class LazyM2  
&nbsp;&nbsp;&nbsp;Proxy = Struct.new :m, :x do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def (y); m.get(x,y) end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def =(y,v); m.set(x,y,v) end  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;def initialize(default = nil)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@h = Hash.new(default)  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;def (x)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Proxy.new self, x  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;def get(x,y)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@h[[x,y]]  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;def set(x,y,z)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@h[[x,y]]=z  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;def clear  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@h.clear  
&nbsp;&nbsp;&nbsp;end  
end

matrix = LazyM2.new

matrix[1][20]=123  
p matrix

> > As a side note: I'd rather delegate to instead of inherit from Hash.  
> > The DynamicArray is not a Hash. For example, method #size remains in  
> > the interface which might lead to surprises.
> 
> Probably not a bad idea. This was seat-of-the-pants code. 🙂

I didn't knew \_that\_ category of software. Learn something new every day. 🙂

Cheers

&nbsp;&nbsp;robert

> **···**
>
> On 19.11.2009 17:53, Marnen Laibow-Koser wrote:
> 
> --  
> remember.guy do |as, often| as.you\_can - without end  
> [http://blog.rubybestpractices.com/](http://blog.rubybestpractices.com/)