Dynamic array?

ruby-talk
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

···

--
Posted via http://www.ruby-forum.com/\.

2

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 (x,y)
    @h[[x,y]]
  end

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

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

3

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
marnen@marnen.org
--
Posted via http://www.ruby-forum.com/\.

4

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.

Best,

···

--
Marnen Laibow-Koser
http://www.marnen.org
marnen@marnen.org

  end

--
Posted via http://www.ruby-forum.com/\.

5

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 (idx)
    super || @default_value
  end
end

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

Greetings
FreakGuard

···

--
Posted via http://www.ruby-forum.com/\.

6

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.

···

--
Posted via http://www.ruby-forum.com/\.

7

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 :slight_smile:
--
Posted via http://www.ruby-forum.com/\.

8

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/

9

Freak Guard 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 (idx)
    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
marnen@marnen.org
--
Posted via http://www.ruby-forum.com/\.

10

Freak Guard:

class DefaultArray < Array

  attr_accessor :default_value

  def initialize
    super
    @default_value = nil
  end

  def (idx)
    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

···

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

11

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

···

2009/11/19 Marnen Laibow-Koser <marnen@marnen.org>:

--
Marnen Laibow-Koser
http://www.marnen.org
marnen@marnen.org
--
Posted via http://www.ruby-forum.com/\.

12

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

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 (y); 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 (x)
     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

···

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

--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/