0

I am trying to think of an implementation of a two dimensional matrix-like data type.
Normally I would take an array of arrays but I'm bound to a relatively low language level which only provides lists and mutable lists, because this is part of (but not an exercise itself, I could simply use an inefficient solution) a software project at university. In this, we are only allowed to use a specific language level.
So of cause I could take a list of mutable lists and, in search of an item in row n and column m, get the m-th mutable list and go throught it until position n. But isn't there a better solution than going through the whole list?

6
  • Do you want just to put/retrieve elements with certain indexes? Are there any other requirements or use cases, like searching by value?
    – scriptin
    Commented Feb 28, 2015 at 12:21
  • No, just put/retrieve. Forgot to mention that.
    – Benjoyo
    Commented Feb 28, 2015 at 12:22
  • And one more question: does it have to be constant size or resizable? Like you create it without specifying the size, and then you put elements it just automatically allocates the space.
    – scriptin
    Commented Feb 28, 2015 at 12:26
  • The size can stay the same after creation.
    – Benjoyo
    Commented Feb 28, 2015 at 12:27
  • I would think that lists are a higher level language feature. At the lowest level, memory is just a flat set of memory locations that are read/written by specifying the addresses of the locations. 1-d arrays are a fairly simple abstraction over that memory space. Lists are a more complex abstraction beyond arrays.
    – poke
    Commented Feb 28, 2015 at 14:08

1 Answer 1

2

Since you need constant size, and access elements by their indexes, I'd say go with 1-dimensional array of WIDTH*HEIGHT size. You can just translate indexes like matrix[x+y*WIDTH] or build a wrapper class to do it like matrix.get(x, y) - that way you don't have to track width, and you can add boundary checks.

Access by index will have a constant time (O(1)) performance.

9
  • That is pretty clever, thanks. But the problem is that I don't have arrays, but only (mutable) lists, which only can be accessed via first and rest. So I'd need to go through the whole list in worst case.
    – Benjoyo
    Commented Feb 28, 2015 at 12:52
  • Than maybe there is a better solution. What language is it?
    – scriptin
    Commented Feb 28, 2015 at 13:09
  • It's Racket/Scheme.
    – Benjoyo
    Commented Feb 28, 2015 at 13:10
  • @Benjoyo: Racket has Vectors, which behave similarly to non-resizeable arrays: docs.racket-lang.org/reference/vectors.html
    – poke
    Commented Feb 28, 2015 at 13:24
  • @poke yes, but I'm bound to lists.
    – Benjoyo
    Commented Feb 28, 2015 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.