Re: the sort function in lisp (destructive)

On Jan 7, 1:08 am, Madhu <enom...@xxxxxxxx> wrote:
* Gene <3d734438-8f14-48ab-95f6-46aec08e7...@xxxxxxxxxxxxxxxxxxxxxxxxxxx> :
Wrote on Sun, 6 Jan 2008 13:20:31 -0800 (PST):
|> > In fact looking at the source for Corman Lisp I discovered that it
|> > reads  the CAR into a vector, sorts that, and then puts the values
|> > back in the  CAR's in sorted order.
|>
|> This might have been done for other reasons than avoiding side-effect.
|> For example, to avoid having two different sort algorithms, or even
|> because it didn't occur to him how to write the algorithm without
|> doing indexed access.
|>
| Another possible reason is to avoid a certain kind of degenerate cache/
| paging behavior.  If you sort a long, randomly ordered list by
| changing cdr's, merely traversing the resulting list cells makes for a
| terrible memory access pattern.

I think there are two many `if's in reasoning about memory access
patterns. You will traverse the list to get it into the array in the
first place, and there may be repeated traversals immediately , on the
resulting list.

But I notice you have made this point in the past, when citing
your paper which exhibited a SHUFFLE algorithm which worked on cons
cells.  I could not look it up, perhaps you could post a brief
description of how it worked here?


I agree. There may not be many cases when it would benefit.

On the random permuter, I'm really very sorry, but I have no access to
the original lisp. Only C. At least this is a fairly literal
translation of the lisp. Here, rand31() is a random number in [0 ..
2^31 - 1]. I apologize for

// this is a provably random permuter Call initially with tail=NULL.
NODE *permutation(NODE *p, int len, NODE *tail)
{
NODE *e, *l1, *l2, *next;
unsigned int l1_len, l2_len;
unsigned long r;

if (!p) return tail;

for (r = rand31() % len, e = p; r; --r) e = e->left;
for (r = 1, l1 = l2 = NULL, l1_len = l2_len = 0; p != NULL; p = next)
{
next = p->left;
if (r == 1) r = rand31() | (1 << 31); // random bit generator
if (p != e) {
if (r & 1) { p->left = l1; l1 = p; ++l1_len; }
else { p->left = l2; l2 = p; ++l2_len; }
r >>= 1; // set up for next random bit
}
}
e->left = permutation(l1, l1_len, permutation(l2, l2_len, tail));
return(e);
}
.

Relevant Pages

  • Re: Sorting by enumeration
    ... sort on the second field, ... But since Lisp only has "less than" ... to have to do some equals testing as well. ... Optimization is a good looking trap but I prefer to avoid it. ...
    (comp.lang.lisp)
  • Re: I would appreciate a code review
    ... > through Paul Graham's ANSI Common Lisp book. ... SORT is mentioned after page 56. ... Don't forget, once you have the matching alist entry, you can: ...
    (comp.lang.lisp)
  • Re: Sorting by enumeration
    ... sort on the second field, ... But since Lisp only has "less than" ... to have to do some equals testing as well. ... Optimization is a good looking trap but I prefer to avoid it. ...
    (comp.lang.lisp)
  • CL subset?
    ... language in a conscious effort to create smaller distributables. ... case of COMPILE and friends, they wouldn't be giving up much at all. ... it seems the most obvious way to implement this sort of thing is to ... LISP" question. ...
    (comp.lang.lisp)
  • Re: the sort function in lisp (destructive)
    ... If you sort a long, ... I think there are two many `if's in reasoning about memory access ... your paper which exhibited a SHUFFLE algorithm which worked on cons ...
    (comp.lang.lisp)