position equivalent for multi-d arrays

Discussion of Common Lisp

position equivalent for multi-d arrays

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

Posts: 2
Joined: Sun May 03, 2009 2:06 pm

Re: position equivalent for multi-d arrays

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

Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands

Re: position equivalent for multi-d arrays

trilepton wrote: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
smithzv

Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

Re: position equivalent for multi-d arrays

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

Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands

Re: position equivalent for multi-d arrays

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
Tom

Posts: 22
Joined: Sat Jun 28, 2008 12:52 pm
Location: Wichita, KS

Re: position equivalent for multi-d arrays

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?
Ramarren

Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

Re: position equivalent for multi-d arrays

Ramarren wrote: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.
gugamilare

Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil

Re: position equivalent for multi-d arrays

gugamilare wrote:...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.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/
findinglisp

Posts: 440
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX

Re: position equivalent for multi-d arrays

findinglisp wrote: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...
gugamilare

Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil

Re: position equivalent for multi-d arrays

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

Posts: 2
Joined: Sun May 03, 2009 2:06 pm

Next