Finding the minimum element in a list

Discussion of Common Lisp

Finding the minimum element in a list

Postby I X Code X 1 » Mon Jun 20, 2011 11:53 am

Hello,

Here's a basic looping question and what I thought was going to be a trivial problem. I want to find the smallest number in a list. The function min does not take a list, so I tried loop through it:

Code: Select all
(defun select (a)
  (let ((x 0))
    (loop for i from 1 to (length a) do
          (if (< i x)
              (print (setf x i))))))


Could someone please point me in the right direction? This is definitely not returning what I want it to. Is there a simple way to find the smallest element in a list? If not, how might I alter my program to get the expected results?

This is what I am getting:

CG-USER(42): (SELECT '(1 2 3))
NIL

Thanks in advance!
User avatar
I X Code X 1
 
Posts: 59
Joined: Sun May 29, 2011 8:52 pm
Location: NY

Re: Finding the minimum element in a list

Postby Joe Taylor » Mon Jun 20, 2011 1:02 pm

The simplest option is probably to apply the list of numbers as arguments to min.

Code: Select all
(apply #'min '(6 85 34 9 2 98))
Last edited by Joe Taylor on Mon Jun 20, 2011 8:35 pm, edited 1 time in total.
Joe Taylor
 
Posts: 1
Joined: Mon Jun 20, 2011 12:58 pm

Re: Finding the minimum element in a list

Postby I X Code X 1 » Mon Jun 20, 2011 2:16 pm

Code: Select all
(defparameter *y* 0)
(defun select (a)
  (let ((x 10))
    (loop for i from 1 to (length a) do
          (if (< (nth *y* a) x)
              (setf x (nth *y* a))
            (setf x x))
          (setf *y* (1+ *y*)))
    x))



Okay, so I was able to find the minimum of a list this way. But it's quite verbose and sloppy. I'd also like to avoid using global variables if at all possible. Is there anyway to do this within a let? It seems that I cannot update y if it's inside the let. It stays at 0 the entire time. Also, for now just assume the numbers are all under 10 (x 10).

Any tips on cleaning this function up?


EDIT:

Okay, I was being a bit dumb here. I can easily do it without a global variable using let. Just need to use setf :oops:

Though, I still would like to make it a bit more clean, and I have my first number being 10. How can I make it so the first number in the list is assigned to x no matter what? Setting x to nil to begin was my first idea, but you cannot say is 1 < nil. Any ideas? Here's what I got:

Code: Select all
(defun select (a)
  (let ((x 10)
        (y 0))
    (loop for i from 1 to (length a) do
          (if (< (nth y a) x)
              (setf x (nth y a))
            (setf x x))
          (setf y (1+ y)))
    x))
User avatar
I X Code X 1
 
Posts: 59
Joined: Sun May 29, 2011 8:52 pm
Location: NY

Re: Finding the minimum element in a list

Postby I X Code X 1 » Mon Jun 20, 2011 2:39 pm

Cleaned it up again :P

It now does everything I want it to do: it doesn't have to have a predefined "high-number" and it returns the correct results every time. Only thing I want to know now is, any better ways to do this? To reiterate, I am finding the smallest number in a list. As far as I know there is no built-in function that works with lists. min does not take a list.

My result:

Code: Select all
(defun select (a)
  (let ((x (first a))
        (y 1))
    (loop for i from 2 to (length a) do
          (if (< (nth y a) x)
              (setf x (nth y a))
            (setf x x))
          (setf y (1+ y)))
    x))



Your result:

Let me know! lol


Thanks!
User avatar
I X Code X 1
 
Posts: 59
Joined: Sun May 29, 2011 8:52 pm
Location: NY

Re: Finding the minimum element in a list

Postby crabbe » Mon Jun 20, 2011 3:48 pm

Is there a reason you don't want to use apply?

* (defun select (l)
(apply #'min l))
SELECT
* (SELECT '(1 2 3))
1
* (select '(3 1 2))
1

-r
crabbe
 
Posts: 2
Joined: Mon Jun 20, 2011 3:42 pm

Re: Finding the minimum element in a list

Postby ander-skirnir » Mon Jun 20, 2011 4:58 pm

Code: Select all
(reduce #'min list)


or

Code: Select all
(apply #'min list)


first is better
ander-skirnir
 
Posts: 2
Joined: Tue May 17, 2011 11:16 am

Re: Finding the minimum element in a list

Postby I X Code X 1 » Mon Jun 20, 2011 5:09 pm

Haha well that's a bit less complex than what I did. Well, at least I got some more experience playing around with some of the lisp language. :geek:

Thanks for the help!
User avatar
I X Code X 1
 
Posts: 59
Joined: Sun May 29, 2011 8:52 pm
Location: NY

Re: Finding the minimum element in a list

Postby I X Code X 1 » Mon Jun 20, 2011 7:49 pm

crabbe wrote:Is there a reason you don't want to use apply?

* (defun select (l)
(apply #'min l))
SELECT
* (SELECT '(1 2 3))
1
* (select '(3 1 2))
1

-r



To answer this question: I did consider using apply but for some reason (which I can't remember now) something was not working. Probably was just me being tired at the moment. As for reduce, I completely forgot about it. Really shouldn't have slipped from my mind so easily.
User avatar
I X Code X 1
 
Posts: 59
Joined: Sun May 29, 2011 8:52 pm
Location: NY

Re: Finding the minimum element in a list

Postby Duke » Mon Jun 20, 2011 9:03 pm

I X Code X 1 wrote:Your result:

Let me know! lol


Here's my solution and a little test I did:
Code: Select all
(defun generate-list (n)
  (labels ((rec (lst n)
             (if (> n 0)
                 (rec (cons (random 10000) lst) (1- n))
                 lst)))
    (rec nil n)))

(defun my-min (lst)
  (labels ((rec (lst min)
             (cond ((null lst) min)
                   ((< (car lst) min) (rec (cdr lst) (car lst)))
                   (t (rec (cdr lst) min)))))
    (rec lst (car lst))))


I do like me some tail recursion...

For n=1000

CL-USER> (time (my-min sample-list))
43,008 processor cycles

CL-USER> (time (apply #'min sample-list))
53,184 processor cycles

n=10000

CL-USER> (time (my-min sample-list))
459,144 processor cycles

CL-USER> (time (apply #'min sample-list))
810,024 processor cycles

n=100000

CL-USER> (time (my-min sample-list))
3,511,728 processor cycles

CL-USER> (time (apply #'min sample-list))
36,217,608 processor cycles


The exact numbers vary drastically between runs, but APPLY is clearly slower, and also runs out of stack frames when n = 1000000, so there's nothing wrong with rolling your own solution when you need to. You might refer to your Lisp implementation's own MIN function and see what it does differently to your attempt.
"If you want to improve, be content to be thought foolish and stupid." -Epictetus
Duke
 
Posts: 38
Joined: Sat Oct 17, 2009 10:40 pm

Re: Finding the minimum element in a list

Postby Ramarren » Mon Jun 20, 2011 10:07 pm

Using REDUCE is obviously best, but some notes about LOOP (although I personally prefer iterate, same principles apply).

LOOP has a number of finders/collectors, and you should check if what you want to do can be done with them. Looking at LOOP CLHS page and searching for "mini" or something like that would reveal

Code: Select all
(let ((list '(5 4 2 3 6 1))) (loop for x in list minimizing x))


Also in most cases you shouldn't bind variables outside the loop and modify anything with SETF. When using LOOP it is best to use it as a self contained construct. LOOP has also sequence iterators. If you are using NTH on a list in a loop then something is definitely wrong. Using LOOP a minimization function could be defined as:

Code: Select all
(defun select (list)
  (loop for l in (cdr list)
        for x = (first list) then (min x l)
        finally (return x)))
Ramarren
 
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

Next

Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 3 guests

cron