position equivalent for multi-d arrays

Discussion of Common Lisp
trilepton
Posts: 2
Joined: Sun May 03, 2009 2:06 pm
Contact:

position equivalent for multi-d arrays

Post by trilepton » Sun May 03, 2009 2:18 pm

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
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

Re: position equivalent for multi-d arrays

Post by Jasper » Tue May 05, 2009 6:49 am

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
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

Re: position equivalent for multi-d arrays

Post by smithzv » Tue May 05, 2009 8:11 am

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

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

Re: position equivalent for multi-d arrays

Post by Jasper » Tue May 05, 2009 10:34 am

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

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

Re: position equivalent for multi-d arrays

Post by Tom » Tue May 05, 2009 10:43 am

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
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: position equivalent for multi-d arrays

Post by ramarren » Tue May 05, 2009 1:41 pm

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
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: position equivalent for multi-d arrays

Post by gugamilare » Tue May 05, 2009 3:37 pm

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.

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: position equivalent for multi-d arrays

Post by findinglisp » Tue May 05, 2009 4:34 pm

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

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

Re: position equivalent for multi-d arrays

Post by gugamilare » Tue May 05, 2009 5:15 pm

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. :D
I wrote it on purpose. I was wondering who would be the first to notice this. :lol:
Actually, what I thought is that you shouldn't waste your time making it faster...

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

Re: position equivalent for multi-d arrays

Post by trilepton » Wed May 06, 2009 1:40 pm

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.

Post Reply