Create two-dimensional arrays and access sub-arrays in Ruby

Question

I wonder if there's a possibility to create a two dimensional array and to quickly access any horizontal or vertical sub array in it?

I believe we can access a horizontal sub array in the following case:

x = Array.new(10) { Array.new(20) }

x[6][3..8] = 'something'

But as far as I understand, we cannot access it like this:

x[3..8][6]

How can I avoid or hack this limit?

Solution 1

There are some problems with 2 dimensional Arrays the way you implement them.

a= [[1,2],[3,4]]
a[0][2]= 5 # works
a[2][0]= 6 # error

Hash as Array

I prefer to use Hashes for multi dimensional Arrays

a= Hash.new
a[[1,2]]= 23
a[[5,6]]= 42

This has the advantage, that you don't have to manually create columns or rows. Inserting into hashes is almost O(1), so there is no drawback here, as long as your Hash does not become too big.

You can even set a default value for all not specified elements

a= Hash.new(0)

So now about how to get subarrays

(3..5).to_a.product([2]).collect { |index| a[index] }
[2].product((3..5).to_a).collect { |index| a[index] }

(a..b).to_a runs in O(n). Retrieving an element from an Hash is almost O(1), so the collect runs in almost O(n). There is no way to make it faster than O(n), as copying n elements always is O(n).

Hashes can have problems when they are getting too big. So I would think twice about implementing a multidimensional Array like this, if I knew my amount of data is getting big.

Solution 2

rows, cols = x,y  # your values
grid = Array.new(rows) { Array.new(cols) }

As for accessing elements, this article is pretty good for step by step way to encapsulate an array in the way you want:

How to ruby array

Solution 3

You didn't state your actual goal, but maybe this can help:

require 'matrix'  # bundled with Ruby
m = Matrix[
 [1, 2, 3],
 [4, 5, 6]
]

m.column(0) # ==> Vector[1, 4]

(and Vectors acts like arrays)

or, using a similar notation as you desire:

m.minor(0..1, 2..2) # => Matrix[[3], [6]]

Solution 4

Here's a 3D array case

class Array3D
   def initialize(d1,d2,d3)
    @data = Array.new(d1) { Array.new(d2) { Array.new(d3) } }
   end

  def [](x, y, z)
    @data[x][y][z]
  end

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

You can access subsections of each array just like any other Ruby array. @data[0..2][3..5][8..10] = 0 etc

Solution 5

x.transpose[6][3..8] or x[3..8].map {|r| r [6]} would give what you want.

Example:

a = [ [1,  2,  3,  4,  5],
      [6,  7,  8,  9,  10],
      [11, 12, 13, 14, 15],
      [21, 22, 23, 24, 25]
    ]

#a[1..2][2]  -> [8,13]
puts a.transpose[2][1..2].inspect   # [8,13]
puts a[1..2].map {|r| r[2]}.inspect  # [8,13]

View more solutions

Comments

[gmile]

Oh, Array inherited transpose? Great!

[johannes]

The problem with this is: transpose is O(n*m), but retrieving a subarray in one direction can be in O(n+m)

[glenn jackman]

using collect instead of map adds a bit of clarity here.

[johannes]

As I understood it, map and collect are the same. It's just which name you prefer for this task.

[bta]

If you need additional functionality or prefer to use the x[6][3..8] notation, you can always subclass Matrix and extend it.

[vol7ron]

This is old but is a[2][0] an error because the 3rd element hasn't been created yet? Meaning a[1][0]=6 would work? I know this is old... just now looking at Ruby.

[sage]

I believe you are correct @vol7tron and a[1][0] = 6 does work. You can create the third row with a[2], but you cannot index into it until after you create it. E.g., a[2] = [] followed by a[2][0] = 6 will work.

[gregoltsov]

I started using Matrix after reading this answer, and it was great. However, there is a big limitation that is better to keep in mind before moving to Matrix - they are immutable. So, there is no way to modify a single element, i.e. m(0, 0) = 0 # => error

[Boris Stitnicky]

@GregoryGoltsov: +1 to Marc-André for writing Matrix. As for their immutability, I wouldn't call it a limitation, but rather a feature. Apparently, Marc-Anré is not only making life easier for himself, but also presenting matrices as a generalization of numbers.

[Marc-André Lafortune]

@BorisStitnicky: For the record, the original author of the library is Keiju Ishitsuka, not me. I also really need to look into making matrices mutable for next version :-)

[Boris Stitnicky]

@Marc-AndréLafortune: I came to appreciate immutability in my YPetri::Simulation class to such extent, that I even dup the inputs. Immutability of Matrix, that I use in it, comes handy. Please, if you make the matrices mutable, make sure that they are either a separate subclass (OpenMatrix for instance, like OpenStruct and Struct), or that user first has to do something like Matrix#open or #unlock or what.

[Marc-André Lafortune]

@BorisStitnicky: Isn't freeze enough? I'll open a redmine issue in a month or two and we can discuss further

[Ich]

What do you mean with [...] almost O(1) [...]?

[Kevin C.]

the array created in this approach refers to the same 1 dimension array, i.e., changing one value will affect the others, e.g., a[0][0] = 1 will make a[1][0] becomes 1 too.

[sahilbathla]

Although its an interesting solution, you will be using a lot of space creating arrays as keys. for numbers there is no memory allocation but for array there is.

[complistic]

This creates an array(3) of references to a single new array(3). That's a total of 2 Arrays and 1 Boolean objects. I think you want something like m=Array.new(3){Array.new(3, true)}. That would give you 4 Arrays and 3 Boolean objects.

[Don Giulio]

neat trick, it has one drawback though, you can't infer the size of the matrix by looking at it. in case all your values are zero there is no way for you to know the size if the multidimensional array

[ahnbizcad]

but you can't make rows with identical keys... =(

[Simone]

You don't have to assign x as [0] will be returned anyway

[Alex Moore-Niemi]

note Array.new can take a block directly, no need for map: Array.new(5) {|x| x = [0] } => [[0], [0], [0], [0], [0]] or even simpler: Array.new(5,[0]) => [[0], [0], [0], [0], [0]]