hi
i need to sort a list of objects in a function, but since the function
"sort" is destructive it changes my initial list.
so what is the best way to simulate a "non-destructive sort" in a function ?
shall i use "copy-list", and sort a copy of my initial list (does it take a
lot of memory if we use copy-list in a repetitive way) ?
or is it better to use a setq ?
or maybe another solution...?
thank U
"fabien" <···············@tiscali.fr> writes:
>
> hi
> i need to sort a list of objects in a function, but since the function
> "sort" is destructive it changes my initial list.
> so what is the best way to simulate a "non-destructive sort" in a function ?
> shall i use "copy-list", and sort a copy of my initial list
This is really your only option. If you want to sort a new list, you
have to create that new list.
> (does it take a
> lot of memory if we use copy-list in a repetitive way) ?
Not any more than you apparently need. If you need to have a copy of
the original list, then you need to use the memory.
Or are you concerned because you will be repeatedly sorting a list. If
this is really a problem (i.e., you know through analysis or profiling
that this will be a bottleneck for your code), you could try structuring
things so that you only make one copy of the list, but it seems likely
that if you need to sort the list again, it will be because it changed.
In that case, there won't be a way out.
The only copying you can avoid is by only sorting the list when it
really needs to be sorted.
> or is it better to use a setq ?
A setq won't help you in any way. SETQ does not copy things, it only
changes the binding of a variable to an object. If you were to do
something like:
(let ((a (list 1 2 3 4 5 6))
b)
(setq b a)
...)
Then B will point to exactly the same list as A. If you sort the list
pointed to by B, the list pointed to by A will also be affected.
> or maybe another solution...?
If you are concerned about repetitive copying, then you need to arrange
your program logic to either not repetitively sort the same list, or
else to do the copy of the list before passing it to the function that
does the repetitive sorting.
Since sorting is a moderately expensive function, at least O(n log n),
avoiding the unnecessary sorts will be much more effective than worrying
about doing the copying. Copy is only O(n), although there are related
space issues.
> thank U
>
>
--
Thomas A. Russ, USC/Information Sciences Institute
"fabien" <···············@tiscali.fr> writes:
> hi
> i need to sort a list of objects in a function, but since the
> function "sort" is destructive it changes my initial list. so what
> is the best way to simulate a "non-destructive sort" in a function ?
> shall i use "copy-list", and sort a copy of my initial list (does it
> take a lot of memory if we use copy-list in a repetitive way) ? or
> is it better to use a setq ? or maybe another solution...? thank U
It depends what you mean by "simulate". Here are the facts:
- SORT will return a list that is a sorted version of the list you
gave it.
- You should assume SORT will scramble the cons cells in the list
you give it.
- You can assign the value returned by SORT back to the variable
that is holding the original list.
Thus, if you really want the original list to be intact after the
SORT, then you'd better pass a copy to SORT. And COPY-LIST is the way
to go. On the other hand, if you're not going to be doing anything
with the old list after you've got the sorted version you don't need
to copy it. Copying will create as many new cons cells as there are
elements in the list so you don't want to do it for no reason. But if
you have a list that you want a sorted and unsorted version of you're
obviously going to have to copy it at some point.
And you can, of course, assign the result of SORT back to the variable
that originally held the list. The only trick with this is that any
other references to the original list will now be refering to the
mangled version. Nothing you can do about that. So your choices are:
(do-stuff (sort list)) ; don't plan to use `list' again.
(do-stuff (sort (copy-list list))) ; want `list' left alone.
(setf list (sort list)) ; `list' is now sorted version of
; original list. (But any other
; references to the previous
; value of `list' are now
; referencing a scrambled mess.)
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
fabien wrote:
> hi
> i need to sort a list of objects in a function, but since the function
> "sort" is destructive it changes my initial list.
> so what is the best way to simulate a "non-destructive sort" in a function ?
Why do you need a non-destructive version?
> shall i use "copy-list", and sort a copy of my initial list (does it take a
> lot of memory if we use copy-list in a repetitive way) ?
It seems that sort and stable-sort are intended to best work
destructively. Copying a list first and then sorting the copy probably
reduces the advantage of a destructive sort. If your code is for
exploration purposes, this might be fine. However, if it's really the
case that you need a non-destructive version because your requirements
suggest this, then it's probably better to build your own data structure
and write your own sort function. In your case, something like insertion
sort is probably a good idea because it allows you to build a copy and
have it sorted in one go.
Pick a good book about algorithms and data structures to learn about the
trade offs of the numerous alternatives. It doesn't necessarily have to
be about Lisp because in this regard, languages don't differ too much.
Maybe there are also some Common Lisp libraries out there that already
provide more of this stuff.
Pascal
--
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."
Pascal Costanza wrote:
> It seems that sort and stable-sort are intended to best work
> destructively. Copying a list first and then sorting the copy probably
> reduces the advantage of a destructive sort. If your code is for
> exploration purposes, this might be fine. However, if it's really the
> case that you need a non-destructive version because your requirements
> suggest this, then it's probably better to build your own data
> structure and write your own sort function. In your case, something
> like insertion sort is probably a good idea because it allows you to
> build a copy and have it sorted in one go.
Unless his requirements include "must not under any circumstances
cons *any* more memory than strictly needed", it seems very
unlikely to me that insertion sort will be better than
(sort (copy-list ...)). Insertion sort is *slow* unless
the list being sorted is either short or already nearly
sorted.
--
Gareth McCaughan
.sig under construc
Gareth McCaughan wrote:
> Pascal Costanza wrote:
>
>
>>It seems that sort and stable-sort are intended to best work
>>destructively. Copying a list first and then sorting the copy probably
>>reduces the advantage of a destructive sort. If your code is for
>>exploration purposes, this might be fine. However, if it's really the
>>case that you need a non-destructive version because your requirements
>>suggest this, then it's probably better to build your own data
>>structure and write your own sort function. In your case, something
>>like insertion sort is probably a good idea because it allows you to
>>build a copy and have it sorted in one go.
>
> Unless his requirements include "must not under any circumstances
> cons *any* more memory than strictly needed", it seems very
> unlikely to me that insertion sort will be better than
> (sort (copy-list ...)). Insertion sort is *slow* unless
> the list being sorted is either short or already nearly
> sorted.
OK, thanks for your comment. I vaguely remember a sorting algorithm that
is especially good when it is not sorting in place. However, I don't
remember its name, and apparently I have got it confused with insertion
sort. Unfortunately, I don't know how to find it at the moment. I think
it was in one of data structures and algorithms books by Niklaus Wirth.
Pascal
--
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."
Pascal Costanza <········@web.de> writes:
> Gareth McCaughan wrote:
>
> > Pascal Costanza wrote:
> >
> >>It seems that sort and stable-sort are intended to best work
> >>destructively. Copying a list first and then sorting the copy probably
> >>reduces the advantage of a destructive sort. If your code is for
> >>exploration purposes, this might be fine. However, if it's really the
> >>case that you need a non-destructive version because your requirements
> >>suggest this, then it's probably better to build your own data
> >>structure and write your own sort function. In your case, something
> >>like insertion sort is probably a good idea because it allows you to
> >>build a copy and have it sorted in one go.
> > Unless his requirements include "must not under any circumstances
> > cons *any* more memory than strictly needed", it seems very
> > unlikely to me that insertion sort will be better than
> > (sort (copy-list ...)). Insertion sort is *slow* unless
> > the list being sorted is either short or already nearly
> > sorted.
>
> OK, thanks for your comment. I vaguely remember a sorting algorithm
> that is especially good when it is not sorting in place. However, I
> don't remember its name, and apparently I have got it confused with
> insertion sort. Unfortunately, I don't know how to find it at the
> moment. I think it was in one of data structures and algorithms books
> by Niklaus Wirth.
Merge sort is very fast (especially when the comparison
function is slow) but needs extra memory. Perhaps that's
what you had in mind?
In any case, I suspect that for sorting linked lists
it's often best to copy the list into contiguous memory,
sort *that*, and then build a new list (reusing the
conses of the old one if you like), in which case
it wouldn't really be "in place" anyway :-).
--
Gareth McCaughan
.sig under construc
From: Marcus Breiing
Subject: Re: a question about sort!
Date:
Message-ID: <VWkjbZL8O5P@breiing.com>
Gareth McCaughan <················@pobox.com> wrote:
> Merge sort is very fast (especially when the comparison
> function is slow) but needs extra memory.
Merge sort of a linked list takes O(log n) extra stack space, which
isn't that much. It also is a stable sort, which IMHO is a very nice
property. It's clearly my favourite for use with linked lists.
Marcus
Marcus Breiing wrote:
> Gareth McCaughan <················@pobox.com> wrote:
>
>>Merge sort is very fast (especially when the comparison
>>function is slow) but needs extra memory.
>
> Merge sort of a linked list takes O(log n) extra stack space, which
> isn't that much. It also is a stable sort, which IMHO is a very nice
> property. It's clearly my favourite for use with linked lists.
Yes, merge sort it was. ;)
Thanks,
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Pascal Costanza <········@web.de> writes:
> OK, thanks for your comment. I vaguely remember a sorting algorithm
> that is especially good when it is not sorting in place. However, I
> don't remember its name, and apparently I have got it confused with
> insertion sort. Unfortunately, I don't know how to find it at the
> moment. I think it was in one of data structures and algorithms books
> by Niklaus Wirth.
From flipping through "Algorithms + Data Structures = Programs",
heapsort looks like the ticket. "Purely Functional Data Structures" is
probably a good place to look for non-destructive algorithms too.
It's quite a long shot that COPY-LIST+SORT wouldn't be perfectly fine
for the original poster though!
BTW, I recently noticed that the (non-destructive) sort code in the
Erlang standard library [1] is 1375 lines of code. Most curious as to
what it all does :-)
Cheers,
Luke
[1]: http://www.bluetail.com/~luke/misc/erlang/lists_sort.erl
Well, this somewhat begs the question. It seems to me that a
"non-destructive" SORT will eventually end up CONSing something sorted.
Therefore the non-destructive sort can always be defined (for
sequences) as
(defun sort-nd (seq pred &key (key #'identity))
(declare (type sequence seq))
(sort (copy-seq seq) pred :key key))
What is at stake here is "object identity". This is what cannot be
easily done without wrapping the sequence. Thus,
(defstruct my-sequence (the-seq () :type sequence))
(defmethod my-stuff:sort ((s my-sequence) pred &key (key #'identity))
(setf (my-sequence-the-seq)
(sort (copy-seq (my-sequence-the-seq s)) pred :key key)))
(defmethod my-stuff:sort ((s sequence) pred &key (key #'identity)
(sys:sort-in-place s pred :key key))
where SYS:SORT-IN-PLACE is an implementation dependent way to achieve
the effects of the first defmethod.
Cheers
--
Marco
Pascal Costanza wrote:
>
> fabien wrote:
>
>> hi
>> i need to sort a list of objects in a function, but since the function
>> "sort" is destructive it changes my initial list.
>> so what is the best way to simulate a "non-destructive sort" in a
>> function ?
>
>
> Why do you need a non-destructive version?
>
>> shall i use "copy-list", and sort a copy of my initial list (does it
>> take a
>> lot of memory if we use copy-list in a repetitive way) ?
>
>
> It seems that sort and stable-sort are intended to best work
> destructively. Copying a list first and then sorting the copy probably
> reduces the advantage of a destructive sort. If your code is for
> exploration purposes, this might be fine. However, if it's really the
> case that you need a non-destructive version because your requirements
> suggest this, then it's probably better to build your own data structure
> and write your own sort function. In your case, something like insertion
> sort is probably a good idea because it allows you to build a copy and
> have it sorted in one go.
>
> Pick a good book about algorithms and data structures to learn about the
> trade offs of the numerous alternatives. It doesn't necessarily have to
> be about Lisp because in this regard, languages don't differ too much.
>
> Maybe there are also some Common Lisp libraries out there that already
> provide more of this stuff.
>
>
> Pascal
>