Hi everyone,
This is my solution for a programming problem we had at school. The
origianl problem was: "Given a list of N elements, find the 2nd largest
element in the list. You should not assume the elements are of a
particular type, but rather use the comparison functions ELT>, ELT<, and
ELT= to compare the elements. You should not destroy the input list
either. You solution will be judged on correctness, number of
comparisons, and run-time speed, in that order. The top-level function
of your solution should be called 2ND-LARGEST, and it takes in a list and
returns the 2nd largest element in the list. (Assume there are no
repetitions in the list)"
I lost the contest, mainly becuase my solution ran slower than the winner.
I think my algorithm is correct though, and I can't think of one that
would make fewer comparisons. So I'm wondering if people have suggestions
on how to make this run faster. I don't know much about optimizing Lisp
code (probably obvious from the code below) but I'm very interested in
learning more.
;; The algorithm is like a basketball tournament, so with n-1 comparisons
;; we can find the largest element. Since the 2nd largest element must
;; have been defeated by the largest element at some point in the
;; tournament (otherwise it wouldn't be the 2nd largest), we only need to
;; make log(n) more comparisons to find it
;; we represent every element by a list, the CAR is the element value itself,
;; the CDR is a list of the values it has defeated in the tournament
;; returns the value of the element
(defun value-of (elt)
(car elt))
;; returns the list of values this element has defeated
(defun defeated-lst (elt)
(cdr elt))
;; updates the defeated list of the winner to include the value of the
;; loser
(defun make-elt (winner loser)
(rplacd winner (cons (value-of loser)
(defeated-lst winner))))
;; the main function, performs n comparisons (a tournament)
(defun tournament (lst start len)
(cond ((= len 1) (list (aref lst start)))
((oddp len)
(let ((oddball (list (aref lst start)))
(the-one (tournament lst (1+ start) (floor (/ len 2))))
(the-other (tournament lst (+ start 1 (floor (/ len 2)))
(floor (/ len 2)))))
(let* ((greater (if (elt> (value-of the-one) (value-of the-other))
(make-elt the-one the-other)
(make-elt the-other the-one)))
(still-greater (if (elt> (value-of greater)
(value-of oddball))
(make-elt greater oddball)
(make-elt oddball greater))))
still-greater)))
(t
(let ((the-one (tournament lst start (/ len 2)))
(the-other (tournament lst (+ start (/ len 2)) (/ len 2))))
(if (elt> (value-of the-one) (value-of the-other))
(make-elt the-one the-other)
(make-elt the-other the-one))))))
;; after running a tournament on the list, returns the second largest
;; element with an additional log(n) comparisons. So the total
;; comparisons is n + log(n)
(defun 2nd-largest (lst)
(let* ((len (length lst))
(array (make-array len :initial-contents lst))
(winner (tournament array 0 len)))
(let ((2nd (car (defeated-lst winner))))
(dolist (elt (cdr (defeated-lst winner)) 2nd)
(if (elt> elt 2nd)
(setq 2nd elt))))))
Kenneth Liu <·····@fas.harvard.edu> writes:
> ;; The algorithm is like a basketball tournament, so with n-1 comparisons
> ;; we can find the largest element. Since the 2nd largest element must
> ;; have been defeated by the largest element at some point in the
> ;; tournament (otherwise it wouldn't be the 2nd largest), we only need to
> ;; make log(n) more comparisons to find it
Your problem, I think, is at the algorithm level rather than the
implementation level, so I'm going to comment on this paragraph.
All you need to do is to find the largest. The second largest will fall out
automatically.
1. Take the first two elements, assume they are the largest and second
largest.
2. Start scanning from the third. If you find a new largest, move the
previous largest to the second largest.
You now need n comparisons, rather than n+log(n).
Sunil
Sunil Mishra wrote:
> 1. Take the first two elements, assume they are the largest and second
> largest.
> 2. Start scanning from the third. If you find a new largest, move the
> previous largest to the second largest.
What happens if the second element is the largest?
Robert
I think some of you are taking statement 1 too literally. Whichever of the
two elements is the largest becomes the largest in the program, and
whichever of the two elements is smaller becomes the second largest in the
program.
Nevertheless, there is still a problem with the algorithm. Every succeeding
element is only checked against the largest. If one of these elements is
larger than the second largest but smaller than the largest, there is no
obvious check in the proposed algorithm which would replace the second
largest element. Thus, the true second largest will usually get missed in
this search.
Robert Monfera wrote in message <·················@fisec.com>...
>Sunil Mishra wrote:
>
>> 1. Take the first two elements, assume they are the largest and second
>> largest.
>> 2. Start scanning from the third. If you find a new largest, move the
>> previous largest to the second largest.
>
>What happens if the second element is the largest?
>
>Robert
"charliew" <········@hal-pc.org> writes:
> Nevertheless, there is still a problem with the algorithm. Every succeeding
> element is only checked against the largest. If one of these elements is
> larger than the second largest but smaller than the largest, there is no
> obvious check in the proposed algorithm which would replace the second
> largest element. Thus, the true second largest will usually get missed in
> this search.
Right. I guess this situation would arise after the true largest is found.
Any simple fix to this would require the algorithm's worst case to go up to
2n. Well, seemed like a good idea...
Sunil
Sunil Mishra wrote in message ...
>"charliew" <········@hal-pc.org> writes:
>
>> Nevertheless, there is still a problem with the algorithm. Every
succeeding
>> element is only checked against the largest. If one of these elements is
>> larger than the second largest but smaller than the largest, there is no
>> obvious check in the proposed algorithm which would replace the second
>> largest element. Thus, the true second largest will usually get missed
in
>> this search.
>
>Right. I guess this situation would arise after the true largest is found.
>
>Any simple fix to this would require the algorithm's worst case to go up to
>2n. Well, seemed like a good idea...
>
>Sunil
Indeed. It seemed like a good idea to me too, at first. Of course, there
is still a possibility here. If the algorithm checks every element against
the second largest, it will be very efficient. The following should work:
Choose a largest element (from the first two elements)
Choose a second largest element (from the first two elements)
Check each succeeding element against the second largest element
If an element is larger than the second largest, check it against the
largest
If this element is smaller than the largest element, replace the second
largest
else, replace the largest element
This algorithm should have most of the efficiency that you intended, without
the hidden assumptions regarding the second largest element.
> Indeed. It seemed like a good idea to me too, at first. Of course, there
> is still a possibility here. If the algorithm checks every element against
> the second largest, it will be very efficient.
Very efficient? In the worst case it does 2n-3 comparisons,
vs. n-2+log_2 n for the optimal algorithm.
Paul
Hi
I am a bit lost. What exactly is the problem again? Isn't it "find the
k-th element"?
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it
> All you need to do is to find the largest. The second largest will fall out
> automatically.
>
> 1. Take the first two elements, assume they are the largest and second
> largest.
> 2. Start scanning from the third. If you find a new largest, move the
> previous largest to the second largest.
>
> You now need n comparisons, rather than n+log(n).
Unfortunately, this algorithm is incorrect. It only works
if the second largest occurs before the first largest in
the list (or occurs in the second position).
The lower bound on the problem is n - 2 + ceiling(log_2 n)
comparisons.
Paul
"Paul F. Dietz" <·····@interaccess.com> writes:
> > All you need to do is to find the largest. The second largest will fall out
> > automatically.
> >
> > 1. Take the first two elements, assume they are the largest and second
> > largest.
> > 2. Start scanning from the third. If you find a new largest, move the
> > previous largest to the second largest.
> >
> > You now need n comparisons, rather than n+log(n).
>
>
> Unfortunately, this algorithm is incorrect. It only works
> if the second largest occurs before the first largest in
> the list (or occurs in the second position).
>
> The lower bound on the problem is n - 2 + ceiling(log_2 n)
> comparisons.
I thought so. Moreover, I believe that the implementation to reach
such a bound is pretty convoluted (yet perfect for LISP style :) ).
I think (if memory does not fail me) that one of the best descriptions
of this class of algorithms is in the Baase's Algorithm
book. (I'm lazy. Fire up Amazon to find the reference :) ).
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it
Yes, Baase's book has a good description (in the
2nd edition, see section 3.3, pages 128-134.)
The book gives the upper and lower bounds.
The algorithm and lower bound are also
given in Horowitz and Sahni "Fundamentals
of Computer Algorithms".
Paul
Sunil Mishra <·······@cleon.cc.gatech.edu> wrote:
> 1. Take the first two elements, assume they are the largest and second
> largest.
> 2. Start scanning from the third. If you find a new largest, move the
> previous largest to the second largest.
I though about this, but it doesn't work if the 2nd largest *is* the second element in the
list...
any thoughts on the level of the code itself?
Kenneth Liu <·····@fas.harvard.edu> writes:
< Hi everyone,
<
< This is my solution for a programming problem we had at school. The
< origianl problem was: "Given a list of N elements, find the 2nd largest
< element in the list. You should not assume the elements are of a
< particular type, but rather use the comparison functions ELT>, ELT<, and
< ELT= to compare the elements. You should not destroy the input list
< either. You solution will be judged on correctness, number of
< comparisons, and run-time speed, in that order. The top-level function
< of your solution should be called 2ND-LARGEST, and it takes in a list and
< returns the 2nd largest element in the list. (Assume there are no
< repetitions in the list)"
<
< I lost the contest, mainly becuase my solution ran slower than the winner.
< I think my algorithm is correct though, and I can't think of one that
< would make fewer comparisons. So I'm wondering if people have suggestions
< on how to make this run faster. I don't know much about optimizing Lisp
< code (probably obvious from the code below) but I'm very interested in
< learning more.
I'm real tired so I'm not too sure if I did this correctly.
;;; The list can only have numbers in it because I don't want to write
;;; the `elt>' function right now.
(defun elt> (x y) (> x y))
(defun find-2nd-largest (list)
(let (max1 max2)
(setq max1 (car list))
(dolist (elt (cdr list))
(cond ((elt> elt max1)
(shiftf max2 max1 elt))
((or (null max2) (elt> elt max2))
(setq max2 elt))))
(values max2 max1)))
The macro shiftf is really neat,
(let ((x 1) (y 2) (z 3))
(shiftf x y z)
(values (cons 'x x) (cons 'y y) (cons 'z z)))
=> (X . 2), (Y . 3), (Z . 3).
I think I lose on the `(null max2)'; I would make it so
elt> always fails for nil, or have it take an optional argument for
auto-failure but that maybe cheating...
Hope this helps some.