position equivalent for multi-d arrays

[trilepton]

hi there,
Is there something like the position function but for multidimensional arrays? Something that takes the array and another argument, if the argument is an element of the array, it would return its index.

Any help would be appreciated.

[Jasper]

I don't think that is possible, i think implementations are not guaranteed to 'know' it. For instance, if you have declared the types of the array to be an integer, a value from the array is an integer, not a pointer you can subtract with to get an index.

What do you want to use it for? Maybe you either want to carry around vectors with indices, or put your value in an struct/class/list so you can write to it. I have made iterator classes, but the problem with those is that people might be tempted to use them imperatively, when the functional approach is better.

[smithzv]

Is there something like the position function but for multidimensional arrays? Something that takes the array and another argument, if the argument is an element of the array, it would return its index.

If I understand you right, no, I don't think there is for the built in arrays in CL; but you could write one. Only thing is you would have to iterate over the array which means your function would be O(m1*m2*...*mn) for a n-dimensional array where each extent is m1, m2, ..., mn, i.e. (dimensions array) => (m1 m2 ... mn). Since we normally think of arrays as constant time data structures, that might not be acceptable. You would also want to supply an equality test to your function, that way you can tweak what constitutes an equivalent statement.

If the linear time is a problem, you could pair your array with a dictionary (like a hash table) that stores the reverse mappings, (i.e. element to index mapping). So anytime you modify the array you need to modify the dictionary to keep it consistent. I think this last bit is non-trivial but doable.

Zach S

[Jasper]

@smithzv: that assumes all the elements in the array are different, though.

[Tom]

Lightly tested code cobbled together from some other code.

Code: Select all

(defun array-indices (row-major-index dimensions)
  "Recursively calculate the indices from the row major index."
  (let ((remaining (rest dimensions)))
    (if remaining
        (multiple-value-bind (index remainder)
            (floor row-major-index (reduce #'* remaining))
          (cons index (array-indices remainder remaining)))
        (cons row-major-index nil))))

(defun array-position (item array &key (test #'eql))
  "Return the position of the first occurrence of item in array."
  (check-type array array)
  (dotimes (index (array-total-size array))
    (when (funcall test item (row-major-aref array index))
      (return-from array-position
        (array-indices index (array-dimensions array))))))


Compared to POSITION, there is no key :FROM-END, :TEST-NOT, :START or :END. :TEST-NOT is deprecated and I'll leave :FROM-END, :START and :END as exercises for the reader. This is an example of where it would be nice if POSITION was a generic function that could be specialized for user data. Anyway, hope this helps.

~ Tom

[Ramarren]

You can also do:

Code: Select all

(defun array-position (item array &rest position-parameters)
  (let ((temp-array (make-array (reduce #'* (array-dimensions array)) :displaced-to array)))
    (array-indices (apply #'position item temp-array position-parameters)
                   (array-dimensions array))))

Not that this is a very good idea, but really, how often does searching in an array makes sense?

[gugamilare]

You can also do:

Code: Select all

(defun array-position (item array &rest position-parameters)
  (let ((temp-array (make-array (reduce #'* (array-dimensions array)) :displaced-to array)))
    (array-indices (apply #'position item temp-array position-parameters)
                   (array-dimensions array))))

Not that this is a very good idea, but really, how often does searching in an array makes sense?

Why isn't it a good idea? Well, this is exactly how I would implement, it is very flexible. If you are saying this because of the garbage produced, I don't think this is a problem, since, as you say, this is a function you will use eventually, if ever, so it shouldn't be fast.

[findinglisp]

...so it shouldn't be fast.

Just a quibble, but I don't know of any function that "shouldn't be fast." There are many that are not required to be fast because they are only used infrequently, but that's not quite the same thing.

[gugamilare]

Just a quibble, but I don't know of any function that "shouldn't be fast." There are many that are not required to be fast because they are only used infrequently, but that's not quite the same thing.

I wrote it on purpose. I was wondering who would be the first to notice this.
Actually, what I thought is that you shouldn't waste your time making it faster...

[trilepton]

Thank you all for your helpful suggestions. Considering that I'm planning on calling this function many many times, I don't think arrays in general are an effective implementation. I'm working on a program to solve logic puzzles, and I think property lists are much better than arrays for this project.