Lisp中的破坏性排序 [英] Destructive sorting in lisp

问题描述

我正在阅读实用的Lisp 。在第11章中，它是关于排序的：

I'm reading Practical Common Lisp. In chapter 11, it says this about sorting:

通常，您对序列的未排序版本不关心，因此允许 SORT 和 STABLE-SORT 在排序过程中销毁该序列。但这确实意味着您需要记住编写以下内容：

Typically you won't care about the unsorted version of a sequence after you've sorted it, so it makes sense to allow SORT and STABLE-SORT to destroy the sequence in the course of sorting it. But it does mean you need to remember to write the following:

(setf my-sequence (sort my-sequence #'string<))

我尝试了以下代码：

CL-USER> (defparameter *a* #( 8 4 3 9 5 9 2 3 9 2 9 4 3)) 
*A*            
CL-USER> *a*
#(8 4 3 9 5 9 2 3 9 2 9 4 3)                                     
CL-USER> (sort *a* #'<)
#(2 2 3 3 3 4 4 5 8 9 9 9 9)
CL-USER> *a*
#(2 2 3 3 3 4 4 5 8 9 9 9 9)

在这段代码中，我们可以看到变量 * a * 已由 sort 函数更改。

In this code we can see that the variable *a* has been changed by the sort function.

那为什么书上说做作业是必须的？

Then why do the book say that is necessary to do an assignment?

我正在使用SBCL + Ubuntu 14.04 + Emacs + Slime

I'm using SBCL + Ubuntu 14.04 + Emacs + Slime

编辑：
在@Sylwester评论后，我添加了 *的评估值a * ，因此很明显值已更改。

Following the comment of @Sylwester I add the evaluation of *a* so it's clear that the value has been changed.

推荐答案

必须进行赋值如果您希望变量之后包含排序后序列的正确值。如果您不在乎，只希望返回值 sort ，则无需分配。

It's necessary to do the assignment if you want your variable to contain the proper value of the sorted sequence afterwards. If you don't care about that and only want the return value of sort, you don't need an assignment.

有两个原因。首先，允许实现使用非破坏性复制来实现破坏性操作。其次，列表上的破坏性操作可能会扰乱这些缺点，从而使传递给该操作的值不再指向该序列的第一个缺点。

There are two reasons for this. First, an implementation is allowed to use non-destructive copying to implement destructive operations. Secondly, destructive operations on lists can permute the conses such that the value passed into the operation no longer points to the first cons of the sequence.

这里是第二个示例问题（在SBCL下运行）：

Here's an example of the second problem (run under SBCL):

(let ((xs (list 4 3 2 1)))
  (sort xs '<)
  xs)
=> (4)

如果我们添加作业，则：

If we add the assignment:

(let ((xs (list 4 3 2 1)))
  (setf xs (sort xs '<))
  xs)
=> (1 2 3 4)

这篇关于Lisp中的破坏性排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！