How to find the rank of nth smallest element

[tachyon]

I was wondering if there is a quick and dirty way to find the rank of
the nth smallest element in lisp. That is for example finding the 2nd
smallest element in a list.

I tried something like this:
The idea is get the minimum, if asked for the 1st smallest stop there,
else throw away the smallest and search the new list for the new
smallest (overall second smallest) and so on until you get the nth
smallest.
The problem that I am having is not getting this number, but knowing
the nth's index (position) relative to the initial list (I will call
the index realtive to the initial list the absolute index and the index
relative to the current list the relative index).

I tried saving the position of the first min relative to the overall
list, then when I find the next min (2nd smallest) I compare this
relative index with the previous (absolute index) if the relative index
is greater or equal that the absolute index add one to the relative
index to make it into the new absolute index (note if the relative
index is smaller than the previous absolute index then the relative
index automatically becomes the new absolute index). The problem is
that this doesn't work if for example say the 4th smallest element
lands in an absolute index after the 1 and 2 smallest, but BEFORE the
third.
Any ideas?

note: getNextBest is 0 for smallest, 1 for second smallest and so on
(defun getMin (children-scores getNextBest)

(setf min 100)
(dotimes (j (+ getNextBest 1)) ; repeat for nth smallest element
(dotimes (i (list-length children))
(when (< (nth i children-scores) min)
(setf min (nth i children-scores))
(if (or (> index temp-index) (= index temp-index))
(setf index (+ i j)) ;; this doesnt work in general
)
(setf index i)
)
) ; end inner dotimes
(if (> getNextBest 0)
(setf temp-index index)
(setf children-scores (remove min children-scores))
)
) ; end outer dotimes
index
)

[Matthias Buelow]

tachyon <pma...@gmail.com> wrote:

>The problem that I am having is not getting this number, but knowing
>the nth's index (position) relative to the initial list (I will call
>the index realtive to the initial list the absolute index and the index
>relative to the current list the relative index).

I'd make a list of pairs (element . rank) from the original list,
and sort that one, keyed by element.

mkb.

[Alan Crowe]

"tachyon" <pma...@gmail.com> writes:

> I was wondering if there is a quick and dirty way to find the rank of
> the nth smallest element in lisp. That is for example finding the 2nd
> smallest element in a list.
>
> I tried something like this:
> The idea is get the minimum, if asked for the 1st smallest stop there,
> else throw away the smallest and search the new list for the new
> smallest (overall second smallest) and so on until you get the nth
> smallest.
> The problem that I am having is not getting this number, but knowing
> the nth's index (position) relative to the initial list (I will call
> the index realtive to the initial list the absolute index and the index
> relative to the current list the relative index).
>
> I tried saving the position of the first min relative to the overall
> list, then when I find the next min (2nd smallest) I compare this
> relative index with the previous (absolute index) if the relative index
> is greater or equal that the absolute index add one to the relative
> index to make it into the new absolute index (note if the relative
> index is smaller than the previous absolute index then the relative
> index automatically becomes the new absolute index). The problem is
> that this doesn't work if for example say the 4th smallest element
> lands in an absolute index after the 1 and 2 smallest, but BEFORE the
> third.
> Any ideas?

Remember that sort is n log n, so sorting the whole list is
competitive with doing a linear scan to find the least
element when you do about log n scans.

Here we test on a list of 100000 random numbers.
Scanning 16 times to find the 16 smallest takes about the
same time as sorting the whole lot

* (time (setf *r* (nth-smallest *t* 16)))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
4.72 seconds of real time
4.686091 seconds of user run time
5.2e-5 seconds of system run time
[Run times include 0.61 seconds GC run time]
0 page faults and
14389248 bytes consed.
((44513 . 2.5510788e-4) (64456 . 4.1604042e-4) (36883 . 5.161762e-4)
(70989 . 5.507469e-4) (14280 . 8.1181526e-4) (99127 . 0.0010204315)
(72454 . 0.0010955334) (22152 . 0.0014972687) (5714 . 0.0015246868)
(79641 . 0.0016987324) ...)

* (time (setf *s* (sort (add-index *t*) #'< :key #'cdr)))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
4.8 seconds of real time
4.697565 seconds of user run time
0.054731 seconds of system run time
[Run times include 0.7 seconds GC run time]
0 page faults and
14112936 bytes consed.
((44513 . 2.5510788e-4) (64456 . 4.1604042e-4) (36883 . 5.161762e-4)
(70989 . 5.507469e-4) (14280 . 8.1181526e-4) (99127 . 0.0010204315)
(72454 . 0.0010955334) (22152 . 0.0014972687) (5714 . 0.0015246868)
(79641 . 0.0016987324) ...)

(defun indexed-min (list)
(reduce (lambda(smallest another)
(if (< (cdr smallest)
(cdr another))
smallest
another))
list))

(defun add-index (list)
(loop for i from 1 and x in list collect (cons i x)))

(defun nth-smallest (list n)
(let ((list (add-index list))
(smallest '()))
(dotimes (i n (reverse smallest))
(setf smallest (cons (indexed-min list)
smallest)
list (remove (caar smallest)
list
:key #'car)))))
(defvar *t*
(loop for i below 100000 collect (random 10.0)))

Alan Crowe
Edinburgh
Scotland

[Paul F. Dietz]

"tachyon" <pma...@gmail.com> writes:

>I was wondering if there is a quick and dirty way to find the rank of
>the nth smallest element in lisp. That is for example finding the 2nd
>smallest element in a list.

Yes, this can be done in time proportional to the length of the list,
for any n.

Here's a simple randomized algorithm (although deterministic
algorithms also exist; look up 'median algorithm', for example
in Aho, Hopcroft and Ullman).

1. Pick a random element x from the list.
2. Traversing the list, count the number of elements <= x.
Call this m.
3. If m >= n, recursively solve the problem on the elements <= x.
4. If m < n, recursively solve the problem of finding the (m - n)th
smallest element among those that were > x.

Each recursion here reduces the size of the list by an expected
constant factor, so the expected total running time is O(length(L)).

Paul

[Marco Antoniotti]

Hi

The easy way is the following (not the most efficient though)

(defun nth-rank (sequence rank)
(let* ((sseq (sort (copy-seq sequence) #'<))
(nth-rank-el (elt sseq rank))
)
(position nth-rank-el sequence :test #'equalp)))

The above uses O(N) memory (the COPY-SEQ operation) and O(N lg(N)) time.
The SORT operation. A better algorithm would use a recursive
rank-finding method (whose implementation is not trivial).

A shorter version (for the brevity fanatics around :) )

(defun nth-rank (s r)
(position (elt (sort (copy-seq s) '<) r) s :test 'equalp))

Cheers
--
Marco

[tachyon]

Thank you all for your attention, its been most helpful.

[justinhj]

I tried to implement this for kicks, I think there's a couple of bits
missing. Is this an exercise for the reader or am I missing something?

In general there seems to be no terminating condition.

Justin

[joseph...@gmail.com]

Alan Crowe wrote:
> "tachyon" <pma...@gmail.com> writes:
>
> > I was wondering if there is a quick and dirty way to find the rank of
> > the nth smallest element in lisp. That is for example finding the 2nd
> > smallest element in a list.

>

> Remember that sort is n log n, so sorting the whole list is
> competitive with doing a linear scan to find the least
> element when you do about log n scans.

Possibly competitive, but certainly slower than the optimal solution.
The key thing to realize is that #'sort is doing work in comparing and
swapping elements that have no chance to be the Nth smallest.

The typical quicksort, for instance, does a partition step to divide
the list into two portions about a pivot. After doing so, you know what
location the pivot should be in; by comparing that to the rank N you
are searching for, you can discard one of the partitions *completely*.

The sort algorithm, however, keeps working on both partitions, even the
ones that are nowhere near the rank of interest.

Look up Floyd & Rivest's SELECT algorithm for an example.

It also matters if you want to select several ranks out of the same
set, in which case you want to preserve some of the partition work that
has already been done.

For "quick and dirty", however, sort & one partial list traversal is
hard to beat.

[joseph...@gmail.com]

It's hard to know what you are referring to without your including
context, but I think you are referring to Paul Dietz's solution.

In particular, he is rather informally stating "count the number of
elements <= x". There is also a need to accumulate the elements in some
way so that you can use that collection (or the other "complement"
collection of elements > x) for the later recursion.

The termination condition will be when you are looking for the
smallest/largest element in a one element list.

Also, if you get to caring about performance, you should be careful
with the step "pick a random element" from the list; you want to avoid
traversing the list all the way to the end to pick a pivot; that
traversal would contribute an O(L) time in addition to the O(L) time
Dietz mentions (I think these algorithms are usually discussed in the
context of array operations, where access to elements is uniform.
Singly-linked lists require more care.) Also, of course, you want to
avoid traversing a list just to see how long it is.

[justinhj]

josephoswaldgg: "It's hard to know what you are referring to without

your including
context, but I think you are referring to Paul Dietz's solution. "

Sorry, I'm using google groups to reply to usenet messages and I don't
think you can quote without doing it manually. I had presumed that my
messages would show up at least in he right place in the thread ;-)

I don't care about performance, and this same issue cropped up in an
earlier post about getting the index of an item in a list...
essentially if you're doing something like

(nth n lst) then you're doing a linear traversal of the list and the
way to get around that is, as you say, to use an array not a list.

"In particular, he is rather informally stating "count the number of
elements <= x". There is also a need to accumulate the elements in some
way so that you can use that collection (or the other "complement"
collection of elements > x) for the later recursion. "

Yeah that bit I had no problem with.

Justin

[justinhj]

Ah here's what Paul was getting at I think... at least this is what I
needed to do to make the algorithm work. The missing part was handling
duplicate items correctly and using that as a terminating condition...

(defun nth-smallest(n lst)
(let* ((len (length lst))
(x (nth (random len) lst))
(less-lst (remove-if #'(lambda(n) (>= n x)) lst))
(same-lst (remove-if #'(lambda(n) (not (eq n x))) lst))
(less-cnt (length less-lst))
(same-cnt (length same-lst)))
(format t "n ~a x ~a less ~a same ~a~%" n x less-lst same-lst)
(cond
((< n less-cnt)
(nth-smallest n less-lst))
((< n (+ less-cnt same-cnt))
(progn
(format t "done answer is ~a~%" x)
x))
(t
(nth-smallest (- n (+ less-cnt same-cnt)) (remove-if
#'(lambda(n) (<= n x)) lst))))))

(nth-smallest 3 '(3 1 4 6 4 2 1))
(nth-smallest 2 '(4 6 7 23 4 6 7 4 3))
(nth-smallest 5 '(3 1 4 6 4 2 1))
(nth-smallest 6 '(4 6 7 23 4 6 7 4 3))

[justinhj]

And in case anyone cares ...

More robust version handles empty lists and lists with less elements
than n

; find the nth smallest item in a list
(defun nth-smallest(n lst)
(if lst
(let ((len (length lst)))
(if (<= n len)
(let*
((x (nth (random len) lst))

(less-lst (remove-if #'(lambda(n) (>= n x)) lst))
(same-lst (remove-if #'(lambda(n) (not (eq n x)))
lst))
(less-cnt (length less-lst))
(same-cnt (length same-lst)))

(cond
((< n less-cnt)
(nth-smallest n less-lst))
((< n (+ less-cnt same-cnt))

x)

(t
(nth-smallest (- n (+ less-cnt same-cnt)) (remove-if
#'(lambda(n) (<= n x)) lst)))))

nil))
nil))

(nth-smallest 3 '(3 1 4 6 4 2 1))
(nth-smallest 2 '(4 6 7 23 4 6 7 4 3))
(nth-smallest 5 '(3 1 4 6 4 2 1))
(nth-smallest 6 '(4 6 7 23 4 6 7 4 3))

(nth-smallest 1 '())
(nth-smallest 2 '())
(nth-smallest 2 '(1))
(nth-smallest 2 '(5 3 1 ))
(nth-smallest 4 '(1 4 4 45 5 6 4 66))

[joseph...@gmail.com]

justinhj wrote:
> josephoswaldgg: "It's hard to know what you are referring to without
> your including
> context, but I think you are referring to Paul Dietz's solution. "
>
> Sorry, I'm using google groups to reply to usenet messages and I don't
> think you can quote without doing it manually. I had presumed that my
> messages would show up at least in he right place in the thread ;-)

Click the "show options" to the right of the author's name on the post.
The "Reply" command in *that* banner will quote the message. That this
is not the default is, IMO, a bug.

[Louis Theran]

It's a recursive algorithm. Here's a simple implementation.

(defun rank (test a s)
(count-if (lambda (x) (funcall test x a)) s))

(defun left (test a s)
(remove-if-not (lambda (x) (funcall test x a)) s))

(defun right (test a s)
(remove-if (lambda (x) (funcall test x a)) s))

(defun random-element (s)
(elt s (random (length s))))

(defun order (o s &optional (test '<=))
(let* ((a (random-element s))
(r (rank test a s)))
(cond ((= (length s) 1) (elt s 0))
((>= r o)
(order o (left test a s) test))
(t (order (- o r) (right test a s) test)))))

(defun median (s &optional (test '<=))
(order (truncate (length s) 2) s test))

[Alan Crowe]

"justinhj" <just...@gmail.com> writes:

> And in case anyone cares ...

I'm following this thread with great interest.

I'm intrigued by the idea of Lisp as runnable pseudo-code,
so when Paul Dietz posted

1. Pick a random element x from the list.
2. Traversing the list, count the number of elements <= x.
Call this m.
3. If m >= n, recursively solve the problem on the elements <= x.
4. If m < n, recursively solve the problem of finding the (m - n)th
smallest element among those that were > x.

I wondered whether I could use this directly as the top
level function definition and then add stuff to make it
go. So I sat and I typed

;; Pseudo code

(defun nth-smallest (list n)
(let* ((pivot (pick-one list))
(analysis (analyse list pivot))) ;Traversing the list
(cond ((<= n (smaller analysis)) ;pivot was too big
;; recursively solve the problem on the elements < x
(nth-smallest (low-set analysis) n))
((<= n (+ (smaller analysis) (same analysis)))
pivot)
(t ; the high set excludes the smaller and equal sets
;; recursively solve the problem of finding the (m - n)th

;; smallest element among those that were > x.

(nth-smallest (high-set analysis)
(- n
(smaller analysis)
(same analysis)))))))

;;; I'm assuming that analyse will traverse the list
;;; and construct an analysis containing the various counts
;;; and subsets as required

;;; picking one is easy enough if we don't mind bumping into worst
;;; case behaviour on a list that is already in order

(defun pick-one (list)
(assert (not (null list)) ())
(car list))

;;; Thinking bottom up, a key concept is having a bag of things
;;; and keeping count as we put things into it

;;; The protocol is to add items with add
;;; then see how many we've got with total
;;; and the list of them with members

(defclass counted-set ()
((count :reader total
:initform 0)
(set :reader members
:initform '())))

(defmethod add ((item t)(bag counted-set))
(push item (slot-value bag 'set))
(incf (slot-value bag 'count)))

;;; Analyse must return an object, an analysis, with the protocol
;;; smaller, same, larger - counts relative to the pivot
;;; low-set, high-set - the partition relative to the pivot

;;; Lets build the analysis object on top of counted-set
;;; Then the analysis object pretty simple and defstruct is
;;; adequate

(defun analyse (list pivot)
(let ((equal (make-instance 'counted-set))
(less (make-instance 'counted-set))
(more (make-instance 'counted-set)))
(dolist (item list (make-analysis :equal equal
:less less
:more more))
(cond ((= item pivot)(add item equal))
((< item pivot)(add item less))
((> item pivot)(add item more))))))

(defstruct analysis equal less more)

(defmethod smaller ((a analysis))
(total (analysis-less a)))

(defmethod larger ((a analysis))
(total (analysis-more a)))

(defmethod same ((a analysis))
(total (analysis-equal a)))

(defmethod high-set ((a analysis))
(members (analysis-more a)))

(defmethod low-set ((a analysis))
(members (analysis-less a)))

Well, by the time I'd finished all this typing I was feeling
that my experiment had failed. Yes, I added stuff to make
the "Psuedo code" go, but I'd worn out my keyboard in the
process, and I still had to debug the code.

So I try it out and it works first time.

I find that a little spooky. I usually write `clever code'
and then have to puzzle over why it doesn't work. (I always
intend to write plain code, but once I get into it I get
carried away.)

Maybe the experiment is a success after all.

Alan Crowe
Edinburgh
Scotland

[justinhj]

Thanks!

[Joe Marshall]

Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

> I'm intrigued by the idea of Lisp as runnable pseudo-code,
> so when Paul Dietz posted

[long story shortened...]

> So I try it out and it works first time.

No doubt the static typing.

> Maybe the experiment is a success after all.

It'd be interesting to give the same problem to some students and have
them solve it in Java, C, or whatever the language of the day is.

[Alan Crowe]

Joe Marshall <jmar...@alum.mit.edu> writes:
> Alan Crowe <al...@cawtech.freeserve.co.uk> writes:
>
> > I'm intrigued by the idea of Lisp as runnable pseudo-code,
> > so when Paul Dietz posted
> [long story shortened...]
>

I'm still struggling to work out what I mean by runnable
pseudo-code. I've tried again starting with this as the
pseudo-code:

(recursive-definition-of (nth-smallest n list)
(chose pivot from list)
(learn
less-than-pivot
less-than-or-equal-pivot
items<pivot
items>pivot
from
traverse list pivot)
(if n <= less-than-pivot recurse-on n items<pivot)
(if less-than-pivot < n <= less-than-or-equal-pivot answer-is pivot)
(otherwise recurse-on (- n less-than-or-equal-pivot) items>pivot))

The challenge I set myself was to get this to run. I thought
that dealing with

less-than-pivot < n <= less-than-or-equal-pivot

was an interesting thing to do because it is not handled
entirely happily in any language that I know.

Having an infix minus instead of

(- n less-than-or-equal-pivot)

seemed less interesting.

Pseudo codes often have a point by point style of
presentation, except that the later points have access to
the results of the earlier points, so there is an implicit
nesting that I wanted to explore

> It'd be interesting to give the same problem to some
> students and have them solve it in Java, C, or whatever
> the language of the day is.

Err, with the code above, that would be a quite a serious
challenge, even if they were allowed to add {,; and } at
helpful points :-)

In Artificial Intelligence: A Modern Approach, Russel and
Norvig use a pseudo code instead of an actual language. It
makes the algorithms seem very simple. I wish that I had
some feel for whether the simplicity of the pseudo code is
because real programming languages are still quite clumsy,
or whether it is because the pseudo code is basically
cheating and sweeping complications under the carpet.

Alan Crowe
Edinburgh
Scotland

PS Here is my CL code, in case any-one wants to see how the
pseudo code can be made to run.

(defun traverse (list pivot)
(let ((less-than (count-if (lambda(x)(< x pivot)) list))
(less-than-or-equal (count-if (lambda(x)(<= x pivot)) list))
(items<pivot (remove-if (lambda(x)(>= x pivot)) list))
(items>pivot (remove-if (lambda(x)(<= x pivot)) list)))
(values less-than
less-than-or-equal
items<pivot
items>pivot)))

(defmacro recursive-definition-of (function-call &body accumulating-clauses)
(let ((function-name (car function-call)))
`(symbol-macrolet ((function-name ,(car function-call)))
(defun ,function-name ,(cdr function-call)
,(nest accumulating-clauses)))))

(defun nest (clauses)
(if (endp (cdr clauses)) ;last one
(cons (look-up (caar clauses))
(cdar clauses))
(assemble (car clauses)
(nest (cdr clauses)))))

(defun assemble (context contents)
(list (look-up (car context))
(cdr context)
contents))

(defun look-up (name)
(let ((translation (assoc name *translations*)))
(if translation (cdr translation) name)))

(defparameter *translations*
`((if . inequality-if)
(otherwise . pseudo-otherwise)))

(defmacro chose ((symbol filler form) body)
(assert (eql filler 'from))
`(let ((,symbol (random-choice ,form))) ,body))

(defun random-choice (list)
;; keep it deterministic for now to ease debugging
(car list))

(defmacro learn (learning-experience body)
(let* ((marker (position 'from learning-experience))
(symbols (subseq learning-experience 0 marker))
(form (subseq learning-experience (+ marker 1))))
`(multiple-value-bind ,symbols ,form ,body)))

(defmacro inequality-if (cond&then else)
`(if ,(extract-condition cond&then)
,(extract-then cond&then)
,else))

(defun extract-condition (code)
(cons 'and (reformat-inequality (take-odd code))))

(defun take-odd (code)
(case (second code)
((< <= = > >=) (list* (first code)
(second code)
(take-odd (cddr code))))
(t (list (car code)))))

(defun reformat-inequality (code)
(if (endp (cdr code))
nil
(cons (list (second code)
(first code)
(third code))
(reformat-inequality (cddr code)))))

(defun extract-then (code)
(case (second code)
((< <= = > >=) (extract-then (cddr code)))
(t (cdr code))))

(defmacro answer-is (form &environment env)
`(return-from ,(macroexpand 'function-name env) ,form))

(defmacro recurse-on (&environment env &rest args)
(let ((function-name (macroexpand 'function-name env)))
(cons function-name args)))

(defmacro pseudo-otherwise (&rest args)
args)

(defun spy (function form env)
(if (and (listp form)
(eql (symbol-package (car form))
(find-package "CL-USER")))
(progn
(terpri)(terpri)
(format t "Expanding ~A~%" form)
(print (funcall function form env)))
(funcall function form env)))

Spy isn't called. I set *macroexpand-hook* to #'spy to help me
debug this.

CL-USER(139): (dotimes (i 10)
(print (nth-smallest (+ i 1) '(5 2 3 3 3 4 1 3 3 3))))
1
2
3
3
3
3
3
3
4
5

[justinhj]

Alan Crowe wrote:
> I'm still struggling to work out what I mean by runnable
> pseudo-code. I've tried again starting with this as the
> pseudo-code:

Some interesting code there

Your post seems to show that the more abstract and simple your starting
point, the more code you need under the scenes to make it work

> In Artificial Intelligence: A Modern Approach, Russel and
> Norvig use a pseudo code instead of an actual language. It
> makes the algorithms seem very simple. I wish that I had
> some feel for whether the simplicity of the pseudo code is
> because real programming languages are still quite clumsy,
> or whether it is because the pseudo code is basically
> cheating and sweeping complications under the carpet.

Good pseudocode should give you everything you need to implement the
solution. Leaving unimportant things for you to do. If the unimportant
things have to be done a certain way, then they become important.

So for example in the AI book a description of the A* search algorithm
would tell you to maintain two lists of nodes, but the actual data type
and algorithm you use would be up to you and irrelevant (apart from
performance concerns.)

[lin8080]

justinhj schrieb:

[1] ;; copy&paste into dosbox on win98, clisp 2.35, code obove
[2]> (nth-smallest 2 '(0.23 0.19 2.38 1.17))
1.17
[3]> (nth-smallest 0 '(-2 2/5 3.49 13 -4))
-4
[4]> (nth-smallest 1/2 '(0.333 0.125 0.745 -2/3 (sqrt 2) 9))

*** - >=: (SQRT 2) is not a real number
The following restarts are available:
USE-VALUE :R1 You may input a value to be used instead.
ABORT :R2 ABORT
Break 1 [5]> :r2
[6]>_

Yes. Great. :)

stefan

[lin8080]

Alan Crowe schrieb:

> (defun traverse (list pivot)
> (let ((less-than (count-if (lambda(x)(< x pivot)) list))
> (less-than-or-equal (count-if (lambda(x)(<= x pivot)) list))

...
[see posting before]
...

> (terpri)(terpri)
> (format t "Expanding ~A~%" form)
> (print (funcall function form env)))
> (funcall function form env)))

> Spy isn't called. I set *macroexpand-hook* to #'spy to help me
> debug this.

> CL-USER(139): (dotimes (i 10)
> (print (nth-smallest (+ i 1) '(5 2 3 3 3 4 1 3 3 3))))
> 1

...
> 5

I missed 1 (one) on win98 clisp 2.35 copy&paste:

[228]> (dotimes (i 9) (print (nth-smallest (+ i 1) '(5 2 3 3 3 4 1 3 3
3))))

2

3
3
3
3
3
3
4
5

NIL
[229]>

With (dotimes (i 10) ...) I get two NIL at the end and no 1 at the
beginn.
I play around a bit, maybe I find why....

stefan

[Pascal Bourguignon]

lin8080 <lin...@freenet.de> writes:
> [4]> (nth-smallest 1/2 '(0.333 0.125 0.745 -2/3 (sqrt 2) 9))
>
> *** - >=: (SQRT 2) is not a real number
> The following restarts are available:
> USE-VALUE :R1 You may input a value to be used instead.
> ABORT :R2 ABORT
> Break 1 [5]> :r2
> [6]>_
>
> Yes. Great. :)

Wbat's the problem with you?

(nth-smallest 1/2 (list 0.333 0.125 0.745 -2/3 (sqrt 2) 9))

--
__Pascal Bourguignon__ http://www.informatimago.com/

In a World without Walls and Fences,
who needs Windows and Gates?

[Frank Buss]

lin8080 wrote:

> I missed 1 (one) on win98 clisp 2.35 copy&paste:

did you copy & paste the definition at the end, too?

(recursive-definition-of (nth-smallest n list)
(chose pivot from list)
(learn
less-than-pivot
less-than-or-equal-pivot
items<pivot
items>pivot
from
traverse list pivot)
(if n <= less-than-pivot recurse-on n items<pivot)
(if less-than-pivot < n <= less-than-or-equal-pivot answer-is pivot)
(otherwise recurse-on (- n less-than-or-equal-pivot) items>pivot))

Perhaps you have some buggy nth-smallest function already defined. I've
tested it with clisp 2.35 on Cygwin Windows XP and it works.

--
Frank Buß, f...@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de

[justinhj]

Thanks Pascal

I was just about to suggest

[4]> (nth-smallest 1/2 `(0.333 0.125 0.745 -2/3 ,(sqrt 2) 9))

Although really the function could enforce an integer value of n, it's
kind of a testament to lisp that it just worked and rounded down to the
nearest integer ;-)

Justin

[Marcin 'Qrczak' Kowalczyk]

Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

> The challenge I set myself was to get this to run. I thought
> that dealing with
>
> less-than-pivot < n <= less-than-or-equal-pivot
>
> was an interesting thing to do because it is not handled
> entirely happily in any language that I know.

In Icon and Python it's written just like the above
(except that you can't use "-" in identifiers).

--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/

[Alan Crowe]

"justinhj" <just...@gmail.com> writes:
> Some interesting code there
>
> Your post seems to show that the more abstract and simple your starting
> point, the more code you need under the scenes to make it work

Agreed, but what does it /really/ show. I wrote it in a
spirit of "lets plunge in and write some code". So I now
have a data point. I'll need some more before I start
reaching broader conclusions.

I've been checking Paul Graham's essay, Beating the
Averages. He says that the Viaweb editor was 20-25%
macros. I use nothing like as many macros in my code and I
don't see how to benefit from using more. I think I am
missing out.

My two point plan is

1)Practise macro writing technique, so that I am able to
write any macros that I think will improve my code

2)??? I'm a bit stuck here. I'm at the stage of playing with
ideas, such as `runnable pseudocode'

Alan Crowe
Edinburgh
Scotland

[A.L.]

On 10 Oct 2005 22:05:50 -0700, "tachyon" <pma...@gmail.com> wrote:

>I was wondering if there is a quick and dirty way to find the rank of
>the nth smallest element in lisp. That is for example finding the 2nd
>smallest element in a list.

You do this in Lisp the same way as in other languages: a) create
heap, b) remove first n-1 elements from the heap top.

A.L.

[Pascal Bourguignon]

Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

I think this "runnable pseudocode" is actually a very good idea.

When I need to write a program in a domain I don't know very well, I
just start to write s-expr trying to express stuff in the domain. I'm
just "inventing" a language for the domain. Then I implement the
needed "words". At this stage, I adopted a pragmatic approach, where
I allowed changes in my domain specific s-expressions, to map them
more easily to lisp constructs (functions, methods). But it may be
worthwhile to follow a more absolute way like you do, keeping the dsl
and implementing it with macros. I've not read yours in details yet,
but perhaps the complexity you see can be managed/reduced with more
experience in this technique.

--
__Pascal Bourguignon__ http://www.informatimago.com/

Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.

[justinhj]

I wondered about that. Retrieving the lowest item would be a log2(l) op
where l is the number of items in the data. You'd repeat that operation
n times giving

n log2(l) runtime

And in the process you'd lose your heap so you'd have to add a copy
operation to the whole heap to keep it as it was before you made the
query.

So which algorithm is better depends on the value of n.

For example with a 100 element array once n>15 its better to use the
O(l) algorithm

[justinhj]

Alan Crowe wrote:

> "justinhj" <just...@gmail.com> writes:
> My two point plan is
>
> 1)Practise macro writing technique, so that I am able to
> write any macros that I think will improve my code
>
> 2)??? I'm a bit stuck here. I'm at the stage of playing with
> ideas, such as `runnable pseudocode'

Yeah it seems like a good plan in that you're at the very least getting
macro practise, and at best it would seem to be a way to learn the
right level of abstraction to begin looking at a solution.

I'll have to try that next time I solve a problem in lisp.

[Peter Seibel]

Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

> I've been checking Paul Graham's essay, Beating the Averages. He
> says that the Viaweb editor was 20-25% macros. I use nothing like as
> many macros in my code and I don't see how to benefit from using
> more. I think I am missing out.
>
> My two point plan is
>
> 1)Practise macro writing technique, so that I am able to
> write any macros that I think will improve my code
>
> 2)??? I'm a bit stuck here. I'm at the stage of playing with
> ideas, such as `runnable pseudocode'

This seems related to the "put parens around the spec and make it
work" strategy. I.e. translate a specification into s-exps and then
make those s-exps the code that implement the specification. I give an
example of this in chapters 24 and 25 of _Practical Common Lisp_:

<http://www.gigamonkeys.com/book/practical-parsing-binary-files.html>
<http://www.gigamonkeys.com/book/practical-an-id3-parser.html>

Another strategy is to start from the other end. Write the ugliest
possible code that does what you want and then distill it down to it's
essence using macros. This one may take more practice since you need
to develop a fine aversion to ugliness so you know when to keep
distilling. You need to constantly be looking not just for literal
code duplication but "conceptual" duplication that you can abstract
away.

-Peter

--
Peter Seibel * pe...@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/

[Alan Crowe]

Marcin 'Qrczak' Kowalczyk <qrc...@knm.org.pl> writes:
> Alan Crowe <al...@cawtech.freeserve.co.uk> writes:
>
> > The challenge I set myself was to get this to run. I thought
> > that dealing with
> >
> > less-than-pivot < n <= less-than-or-equal-pivot
> >
> > was an interesting thing to do because it is not handled
> > entirely happily in any language that I know.
>
> In Icon and Python it's written just like the above
> (except that you can't use "-" in identifiers).

That is interesting. I had never even heard of Icon.

Do they short circuit? That is, does a <= b < c <= d hold
off evaluating c and d until it has checked that a is indeed
less than or equal to b?

What is `the right thing' here?

Alan Crowe
Edinburgh
Scotland

[A.L.]

On 13 Oct 2005 09:04:09 -0700, "justinhj" <just...@gmail.com> wrote:

>
>So which algorithm is better depends on the value of n.
>

This is universally true for all algorithms and languages...

A.L.

[justinhj]

Of course, but I can't see anywhere in my post that I was referring
solely to lisp.

[Marcin 'Qrczak' Kowalczyk]

Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

>> In Icon and Python it's written just like the above
>> (except that you can't use "-" in identifiers).
>
> That is interesting. I had never even heard of Icon.
>
> Do they short circuit? That is, does a <= b < c <= d hold off
> evaluating c and d until it has checked that a is indeed less than
> or equal to b?

Yes in both.

In Icon it relies on the unusual core evaluation rules of the
language, which uses backtracking where an expression can potentially
lazily generate several values, similarly to Prolog. "if" checks
whether the condition succeeds or fails, i.e. whether it produces
any values or not; it doesn't involve materialized Boolean values.
Comparison operators return their right argument if the condition
is true, and fail if it's false. This yields the intended semantics
of chained comparisons when operator calls are nested in the right
direction.

In Python comparison operators are just treated specially by the
compiler. "a <= b < c" generates the short-circuiting code which
evaluates each expression at most once, and is different from
both "(a <= b) < c" and "a <= (b < c)".

[lin8080]

Frank Buss schrieb:
> lin8080 wrote:

> > I missed 1 (one) on win98 clisp 2.35 copy&paste:

> did you copy & paste the definition at the end, too?

> (recursive-definition-of (nth-smallest n list)
...

No I did not. This stands at the beginn of the posting. I copy&paste
only after Alan Crowe PS lines.

.................

PS Here is my CL code, in case any-one wants to see how the
pseudo code can be made to run.

[code]
..................

(In my Browser it is posting-reference 11 and 8, there is no (defun
nth-smallest n list) inside (not even nth-smallest), but clisp session
has (defun nth-smallest (n lst) ...) from justinhj's code before). Mabey
this was used in the second copy&paste?

> Perhaps you have some buggy nth-smallest function already defined. I've
> tested it with clisp 2.35 on Cygwin Windows XP and it works.

I'll do this again, when I find time.

stefan

[justinhj]

lin8080 wrote:
> Frank Buss schrieb:

> No I did not. This stands at the beginn of the posting. I copy&paste
> only after Alan Crowe PS lines.

> I'll do this again, when I find time.
>
> stefan

Just out of interest I copied the code into a window and it gave the
correct output as in Alan's original post. I'm using CLISP 2.35

Justin

[justinhj]

Yeah I see what happened, you got my version of the code which would
give that output, since I use n=0 gives the 1st smallest, n=1 gives the
2nd etc

[Steven M. Haflich]

Paul F. Dietz wrote:
> Yes, this can be done in time proportional to the length of the list,
> for any n.

I'm often perplexed by all the learned scholars who speculate about
the maximal efficiency of an algorithm. It seems to me overly
restrictive and a violation of parity not to think about the
minimally efficient solution. Years ago when Usenet existed before
the Internet, and when it was possible to read the entire volume of
postings each day, there was (I think in comp.lang.c) exploration
of "malgorithms". IIRC a malgorithm was defined as an effective
procedure to solve a problem that optimized the time required to
find a solution (where "optimize" implies "maximize") without
adding superfluous do-nothing code to the solution.

My favorite example of a malgorithm for sorting a sequence can be
expressed as:

1. randomize the order of the sequence
2. if the sequence is now ordered, return it
3. goto 1

> Here's a simple randomized algorithm (although deterministic
> algorithms also exist; look up 'median algorithm', for example
> in Aho, Hopcroft and Ullman).

Here is my solution for an effective malgorithm for the current
problem. Please note that this malgorithm is carefully coded
to do the right thing for sequences with length less than 2, and
for sequences with elements that are #'=.

Read it and weep.

(defun silver-medal (list-of-reals)
(symbol-macrolet
((list-of-reals1 (remove-duplicates list-of-reals :test #'=)))
(and (cdr list-of-reals1)
(loop as trial = (elt list-of-reals1
(random (length list-of-reals1)))
when (and (loop for x in list-of-reals1
when (< x trial)
collect pi)
(null (cdr (loop for x in list-of-reals1
when (< x trial)
collect 22/7))))
return trial)))))

[Alan Crowe]

Marcin 'Qrczak' Kowalczyk <qrc...@knm.org.pl> writes:

> Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

> > Do they short circuit? That is, does a <= b < c <= d hold off
> > evaluating c and d until it has checked that a is indeed less than
> > or equal to b?
>
> Yes in both.
>
> In Icon it relies on the unusual core evaluation rules of the
> language, which uses backtracking where an expression can potentially
> lazily generate several values, similarly to Prolog. "if" checks
> whether the condition succeeds or fails, i.e. whether it produces
> any values or not; it doesn't involve materialized Boolean values.
> Comparison operators return their right argument if the condition
> is true, and fail if it's false. This yields the intended semantics
> of chained comparisons when operator calls are nested in the right
> direction.
>
> In Python comparison operators are just treated specially by the
> compiler. "a <= b < c" generates the short-circuiting code which
> evaluates each expression at most once, and is different from
> both "(a <= b) < c" and "a <= (b < c)".
>

I'm going green with envy here. When I have an inequality
such as 0 <= r < n to code up I find that

(and (<= 0 r)
(< r n))

feels gross and

(< -1 r n)

is too stressful, because that kind of petty transformation
is bound to cause an off by one error one day.

I think this macro does the trick

;;;; (inequality 0 <= i < j <= n)
;;; includes short circuiting so that later terms
;;; are not evalutated if earlier ones fail
;;; includes temporary variables. Forms are
;;; evaluated zero or one times, never twice

;;; I don't check the names given for the inequalities
;;; so they can be user defined functions (of two arguments)
;;; With
#|
(defun strlen< (r s)
(< (length r)
(length s)))
|#
;;; (inequality "alan" strlen< "crowe" strlen< "edinburgh") => T

#| I want (inequality a <= b < c <= d) to
expand to

eval a
eval b
check a<=b
if ok
eval c
check b<c
if still ok
eval d
check c <= d |#

#| I think I have dreamt up a suitable pattern
The code for b < c <= d is going to have to save c in case it is needed
later

(let ((#:temp c))

and then use the value of b saved from last time

(< #:earlier-temp #:temp)

which has to be anded with the rest of the computation,
which is recursive on c <= d and needs to know the name
#:temp so that it can access the value already computed

* (macroexpand '(inequality a <= b < c <= d))

(LET ((#:G867 A))
(LET ((#:G868 B))
(AND (<= #:G867 #:G868)
(LET ((#:G869 C))
(AND (< #:G868 #:G869)
(LET ((#:G870 D))
(AND (<= #:G869 #:G870) T)))))))

|#

(defmacro inequality (&rest odd)
(labels ((order-next (odd previous)
(if (endp (cdr odd))
t
(let ((temp (gensym)))
`(let ((,temp ,(third odd)))
(and (,(second odd) ,previous ,temp)
,(order-next (cddr odd) temp)))))))
(let ((temp (gensym)))
`(let ((,temp ,(car odd)))
,(order-next odd temp)))))

Alan Crowe
Edinburgh
Scotland

[Kaz Kylheku]

Alan Crowe wrote:
> * (macroexpand '(inequality a <= b < c <= d))
>
> (LET ((#:G867 A))
> (LET ((#:G868 B))
> (AND (<= #:G867 #:G868)
> (LET ((#:G869 C))
> (AND (< #:G868 #:G869)
> (LET ((#:G870 D))
> (AND (<= #:G869 #:G870) T)))))))

How about this pattern:

(LET (#:G001)
(AND (<= A (SETF #:G001 B))
(< #:G001 (SETF #:G001 C))
(<= #:G001 D)))

You just need one temporary variable to tie you over from one
inequality to the next.

[Joe Marshall]

"Steven M. Haflich" <s...@alum.mit.edu> writes:

> Paul F. Dietz wrote:
>> Yes, this can be done in time proportional to the length of the list,
>> for any n.
>
> I'm often perplexed by all the learned scholars who speculate about
> the maximal efficiency of an algorithm. It seems to me overly
> restrictive and a violation of parity not to think about the
> minimally efficient solution.

Broder and Stolfi wrote a wonderful paper on just this problem:
``Pessimal Algorithms and Simplexity Analysis''
at
http://www.cs.uiuc.edu/class/fa05/cs473ug/resources/pessimal-algorithms.pdf

[lin8080]

Peter Seibel schrieb:
> Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

<http://www.gigamonkeys.com/book/practical-parsing-binary-files.html>
<http://www.gigamonkeys.com/book/practical-an-id3-parser.html>

Hi;

This is too interesting to ignore. I will give you an example where this
would be more necessary than a first thought will show.

Think about an expand (describe), when you want access to available
docus, ie (show-doc 'name), (list-doc-local), (search-doc-web), ...

I actualy try something with xml parts, but this may take a while, this
is a large field :).

(with-xml-part '(
<location file="local\documents\owner\cl-impnotes\..."/>
<info type="use" value="constants"/>
<info type="use" value="COMMON-LISP"/>
<info type="export" value="+LIBRARY-NAME+"/>
<variable id="variable + LIBRARY-NAME + LIBRARY-NAMES"/>
<location file="public\documents\owner\climpnotes\*.html"/>
<info type="mod" value="constant"/>
))

Now one problem is named path-names, another is include some-lisp-code
to specify a few points, or the in/out-put between interpreter and
browser-xml-mechanics.

But I dont plan to type tonnes of xml- or slot-code there, just think
around, which could be a elegant way to get that done. Sure, there are
some tests, but its horrible to work on after some time passed.

Last point: will I have the output in a browser-window (case read-only)
or in the interpreter-window (case work-on-it), ... things like this
easily fill the brain-room and ends in confusion.

My goal is using pseudo-code with the interpreter and use the specified
output from the xml-search-results to automatically translate/ create
some useable code-pieces to work on. Starting with a simply lookup
possibility for some examples or :keywords to a function. Therefor it is
useful to get a quick access to all local/ online docs (or commented
code-examples) with one simple (show-doc 'name :key-specifics).

stefan

(pseudo-code) vs (do-what-i-mean)

[Marcin 'Qrczak' Kowalczyk]

"Kaz Kylheku" <kkyl...@gmail.com> writes:

>> (LET ((#:G867 A))
>> (LET ((#:G868 B))
>> (AND (<= #:G867 #:G868)
>> (LET ((#:G869 C))
>> (AND (< #:G868 #:G869)
>> (LET ((#:G870 D))
>> (AND (<= #:G869 #:G870) T)))))))
>
> How about this pattern:
>
> (LET (#:G001)
> (AND (<= A (SETF #:G001 B))
> (< #:G001 (SETF #:G001 C))
> (<= #:G001 D)))

I would suppose that LET with separate variables is easier for
compilers to optimize than SETF. E.g. they will more easily infer and
make use of the fact that the type of the given variable is a fixnum,
or that it's a constant, than that it's a fixnum between this
assignment and that.

[Lars Brinkhoff]

Alan Crowe <al...@cawtech.freeserve.co.uk> writes:
> Marcin 'Qrczak' Kowalczyk <qrc...@knm.org.pl> writes:
> > In Python comparison operators are just treated specially by the
> > compiler. "a <= b < c" generates the short-circuiting code which
> > evaluates each expression at most once, and is different from both
> > "(a <= b) < c" and "a <= (b < c)".
> I'm going green with envy here. When I have an inequality
> such as 0 <= r < n to code up I find that
> (and (<= 0 r)
> (< r n))
> feels gross and
> (< -1 r n)
> is too stressful

In the limited case with only three numbers to compare, how does

(typep r `(integer 0 (,n))) ;Or "real", or whatever.

make you feel?

[Alan Crowe]

Lars Brinkhoff <lars...@nocrew.org> writes:

> Alan Crowe <al...@cawtech.freeserve.co.uk> writes:
> > When I have an inequality
> > such as 0 <= r < n to code up I find that
> > (and (<= 0 r)
> > (< r n))
> > feels gross and
> > (< -1 r n)
> > is too stressful
>
> In the limited case with only three numbers to compare, how does
>
> (typep r `(integer 0 (,n))) ;Or "real", or whatever.
>
> make you feel?

The strong feelings originate in my relationship to the
source material from which I'm coding. When my program
doesn't work I check my translation. So if the source
material says (before I run TeX)

sum_{ 0<= i < j < n } f(i,j)

I would like to type in

(sum (i j)(inequality 0 <= i < j < n)
(f i j))

If it says r \member [0,n)
then

(typep r `(integer 0 (,n)))

would feel pretty good, and slightly preferable to
reformating to

(inequality 0 <= r < n )

Alan Crowe
Edinburgh
Scotland

[joseph...@gmail.com]

Alan Crowe wrote:
> > Alan Crowe <al...@cawtech.freeserve.co.uk> writes:
> > > When I have an inequality
> > > such as 0 <= r < n to code up I find that
> > > (and (<= 0 r)
> > > (< r n))
> > > feels gross and
> > > (< -1 r n)
> > > is too stressful

> The strong feelings originate in my relationship to the

> source material from which I'm coding. When my program
> doesn't work I check my translation. So if the source
> material says (before I run TeX)
>
> sum_{ 0<= i < j < n } f(i,j)
>
> I would like to type in
>
> (sum (i j)(inequality 0 <= i < j < n)
> (f i j))

That's a *quite* different set of semantics from the Python example
that was originally stated. Depending on the mathematician and/or
formula, such an inequality could represent a set of integers, a
sequence (possibly infinite) of integers, or, in your particular case,
a set of ordered pairs of integers.

Your "sum" will have to be one hell of a macro to make sense out of
general inequality forms slurped out of TeX files. Good luck with that.

[Paul F. Dietz]

Lars Brinkhoff wrote:

> In the limited case with only three numbers to compare, how does
>
> (typep r `(integer 0 (,n))) ;Or "real", or whatever.
>
> make you feel?

It doesn't make me feel good at all, since I suspect all existing
Lisp implementations will do this by consing up the type at run
time, then calling the general-case TYPEP function, which would
parse this type term. This will have horrible performance.

It seems to me that Lisp is missing types (except for classes)
as first class objects; these would be useful here.

Paul

[Duane Rettig]

"Paul F. Dietz" <di...@dls.net> writes:

> Lars Brinkhoff wrote:
>
>> In the limited case with only three numbers to compare, how does
>> (typep r `(integer 0 (,n))) ;Or "real", or whatever.
>> make you feel?
>
> It doesn't make me feel good at all, since I suspect all existing
> Lisp implementations will do this by consing up the type at run
> time, then calling the general-case TYPEP function, which would
> parse this type term. This will have horrible performance.

Well, except for the fact that our compiler-macro for typep doesn't
handle the backquote expression as I would have expected, we at
least come close - this in Allegro CL 7.0:

CL-USER(1): (compile (defun foo (x) (typep x '(integer 0 (10)))))
FOO
NIL
NIL
CL-USER(2): (disassemble 'foo)
;; disassembly of #<Function FOO>
;; formals: X

;; code start: #x10684a9c:
0: 83 f9 01 cmpl ecx,$1
3: 74 02 jz 7
5: cd 61 int $97 ; SYS::TRAP-ARGERR
7: 80 7f cb 00 cmpb [edi-53],$0 ; SYS::C_INTERRUPT-PENDING
11: 74 02 jz 15
13: cd 64 int $100 ; SYS::TRAP-SIGNAL-HIT
15: a8 03 testb al,$3
17: 74 07 jz 26
19: 8b c7 movl eax,edi
21: f8 clc
22: 8b 75 fc movl esi,[ebp-4]
25: c3 ret
26: 83 f8 00 cmpl eax,$0
29: 7c f4 jl 19
31: 83 f8 24 cmpl eax,$36
34: 8b c7 movl eax,edi
36: 7f 03 jnle 41
38: 8d 47 c2 leal eax,[edi-62] ; T
41: f8 clc
42: eb ea jmp 22
CL-USER(3): (foo 9)
T
CL-USER(4): (foo 10)
NIL
CL-USER(5): (foo 9.0)
NIL
CL-USER(6): (foo 'a)
NIL
CL-USER(7):

Note that there is no call in this function; all of the checks are
being done based on a breakdown of the type itself.

I'll have to look into fixing the compiler-macro to allow the
backquoted expression - as long as the final form is a constant
there should be no trouble expanding this. It should also be easy
enough to rewrite a non-constant integer range into a test, although
the testing would be slightly less efficient, because you wouldn't
know if n were a fixnum, nor would you know that the
whole test could be elided and nil returned if n were negative.
Thanks.

> It seems to me that Lisp is missing types (except for classes)
> as first class objects; these would be useful here.

Mostly what is missing is the ability to normalize them. However,
they don't necessarily need to be first-class - they could just
be a subset of (or symbol list class) that has a way to manipulate
them as types.

--
Duane Rettig du...@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182

[Gareth McCaughan]

Joe Marshall wrote:

[Alan Crowe:]
>> So I try it out and it works first time.
>
> No doubt the static typing.
>
>> Maybe the experiment is a success after all.
>
> It'd be interesting to give the same problem to some students and have
> them solve it in Java, C, or whatever the language of the day is.

I tried the experiment in Python (my second-favourite language
after Common Lisp, and arguably one of the "languages of the day"),
producing (as with Alan, on the basis of Paul's pseudocode)

def nth_smallest(items, n):
if len(items) < n: raise "illegal spec"
if len(items) == 1: return items[0]
x = choose_randomly(items)
smaller, equal, larger = split(items, x)
if n < len(smaller): return nth_smallest(smaller, n)
else: n -= len(smaller)
if n < len(equal): return x
else: n -= len(equal)
return nth_smallest(larger, n)

def choose_randomly(items):
return items[random.randint(0,len(items)-1)]

def split(items, pivot):
return [x for x in items if x<pivot], \
[x for x in items if x==pivot], \
[x for x in items if x>pivot]

which also worked first time. (Although there was a little bug
in my trivial test harness.) Elapsed time: a couple of minutes.
So Lisp isn't unique in this respect. I think Ruby or even Perl
would have been a similar story, modulo some reference-related
pain in Perl.

C, C++ or Java would have been a different story altogether.

--
Gareth McCaughan
.sig under construc

[Gareth McCaughan]

I wrote:

> I tried the experiment in Python (my second-favourite language
> after Common Lisp, and arguably one of the "languages of the day"),
> producing (as with Alan, on the basis of Paul's pseudocode)

[etc]

... not noticing that this thread has been quiescent for over
a month. I've been reading c.l.l rather sporadically. Ahem.

[Alan Crowe]

Gareth McCaughan <Gareth.M...@pobox.com> writes:

> I wrote:
>
> > I tried the experiment in Python (my second-favourite language
> > after Common Lisp, and arguably one of the "languages of the day"),
> > producing (as with Alan, on the basis of Paul's pseudocode)
> [etc]
>
> ... not noticing that this thread has been quiescent for over
> a month. I've been reading c.l.l rather sporadically. Ahem.

Well it is an interesting thread, and I was thinking of
sticking another post on it myself.

The post I consider most worth discussing has ID

861x2q4...@cawtech.freeserve.co.uk

and is accessible at

http://groups.google.co.uk/group/comp.lang.lisp/msg/a827235ce7466a92?hl=en

I think the question it is discussing is this

Suppose I write down my algorithm in a way that I like
and think is especially clear, but then realise that it
is not written in any particular programming language?
What happens if I get very stiff necked about this and
insist that that is the /right/ way of expressing the
algorithm. Rather than change my text to suit a
particular language, I want to change the language to
encompass the text.

One thing that happens is that it triggers lots of pointless
busy work, fitting the syntax of a well thought out language
to the needs of a jotting specific to an algorithm.

Nevertheless, I feel that this touches on something very
deep. What is a programming language? It seems in practise
that a programming language is the boundary document between
human work and automation. Humans write the program and then
the compiler, the assembler, the linker, and the loader
finish the job.

Horizontal motion of that boundary, to one language or
another seems less interesting than vertical motion of that
boundary, such as making a specification or a pseudo-code
algorithm runnable.

Alan Crowe
Edinburgh
Scotland

[Thomas F. Burdick]

Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

> I think the question it is discussing is this
>
> Suppose I write down my algorithm in a way that I like
> and think is especially clear, but then realise that it
> is not written in any particular programming language?
> What happens if I get very stiff necked about this and
> insist that that is the /right/ way of expressing the
> algorithm. Rather than change my text to suit a
> particular language, I want to change the language to
> encompass the text.
>
> One thing that happens is that it triggers lots of pointless
> busy work, fitting the syntax of a well thought out language
> to the needs of a jotting specific to an algorithm.

I think you have that completely backwards. Seeing the algorithm for
the code is often difficult, and often the way the algorithm is
written is very well thought out, not just jotted down. Maintaining
the notation of the algorithm, but in an s-expression form, can be the
easiest way to make the algorithm clear, and the code clearly an
implementation of the algorithm. The work of building Lisp up to the
point of being able to run the pseudo-code is about the same as the
work of implementing it in a funnier-looking way.

--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'