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?

  • Do you want just to put/retrieve elements with certain indexes? Are there any other requirements or use cases, like searching by value? – scriptin Feb 28 '15 at 12:21
  • No, just put/retrieve. Forgot to mention that. – Benjoyo Feb 28 '15 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 Feb 28 '15 at 12:26
  • The size can stay the same after creation. – Benjoyo Feb 28 '15 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 Feb 28 '15 at 14:08
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.

  • 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 Feb 28 '15 at 12:52
  • Than maybe there is a better solution. What language is it? – scriptin Feb 28 '15 at 13:09
  • It's Racket/Scheme. – Benjoyo Feb 28 '15 at 13:10
  • @Benjoyo: Racket has Vectors, which behave similarly to non-resizeable arrays: docs.racket-lang.org/reference/vectors.html – poke Feb 28 '15 at 13:24
  • @poke yes, but I'm bound to lists. – Benjoyo Feb 28 '15 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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