Dynamic array?

Ruby
1

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

2

Freak G. 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
[email protected]

3

2009/11/19 Freak G. [email protected]:

But this does not seem to work with Arrays…

ary = Array.new {[]}
=> []
ary[2]
=> nil

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
def initialize(default = nil)
@h = Hash.new(default)
end

def
@h[[x,y]]
end

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

def clear
@h.clear
end
end

Kind regards

robert

4

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

class DefaultArray < Array

attr_accessor :default_value

def initialize
super
@default_value = nil
end

def
super || @default_value
end
end

… and writing all the iterators I need which will be dead slow I
assume :confused:

Greetings
FreakGuard

5

Freak G. wrote:

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

class DefaultArray < Array

attr_accessor :default_value

def initialize
super
@default_value = nil
end

def
super || @default_value
end
end

… and writing all the iterators I need which will be dead slow I
assume :confused:

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
[email protected]

6

Freak G.:

class DefaultArray < Array

attr_accessor :default_value

def initialize
super
@default_value = nil
end

def
super || @default_value
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 :confused:

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

— Shot

7

Marnen Laibow-Koser wrote:

Hmmm…another approach:

class DynamicArray < Hash
attr_reader :length

def initialize(length)
@length = length
super() {[]}
end

… which doesn’t fulfull the inital target of to not have to set the
length static :slight_smile:

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.

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

8

Freak G. 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.

Best,

Marnen Laibow-Koser
http://www.marnen.org
[email protected]

end

9

Robert K. wrote:

2009/11/19 Freak G. [email protected]:

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 :slight_smile:

10

2009/11/19 Marnen Laibow-Koser [email protected]:

=> []

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.

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

11

Robert K. wrote:

2009/11/19 Marnen Laibow-Koser [email protected]:

=> []

�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. :slight_smile:

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. :slight_smile:

Kind regards

robert

Best,

Marnen Laibow-Koser
http://www.marnen.org
[email protected]

12

On 19.11.2009 17:53, Marnen Laibow-Koser wrote:

Robert K. wrote:

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
Proxy = Struct.new :m, :x do
def ; m.get(x,y) end
def []=(y,v); m.set(x,y,v) end
end

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

def
Proxy.new self, x
end

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

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

def clear
@h.clear
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. :slight_smile:

I didn’t knew that category of software. Learn something new every
day. :slight_smile:

Cheers

robert