问题描述
去年，我已经发布了关于Python的教程和评论以及
Perl的排序功能。 （）
在那篇文章中，我讨论了一种在少年Perlers中知道的技术
作为Schwartzian变换，它也体现在Python中作为其
a ?? keya ??可选参数。
在这里，我会详细介绍这个结构的原因和方法。
----
语言和排序优化：装饰 - 排序 - dedecorate
有许多排序算法。每种语言都可以选择
使用哪种语言。有关详细列表和说明，请参阅维基百科：
Sorting_algorithma ?? 。
但是，使用哪种算法并不重要，最终它将需要对要排序的项目的订单决定功能。假设
你的物品是（a，b，c，d，......），你的订单决定功能是F.
各种算法会尽量减少调用F的次数是
，但是，F将多次应用于列表中的特定元素
。例如，可以调用F（a，b）来查看哪个？a
a ?? aa ??或者?? ?? ??先到了。然后，稍后算法可能需要
来调用F（m，a）或F（a，z）。这里的要点是，对于列表中任意两个项目，F将被称为
，即使其中一个
元素已经与之前的其他元素进行了比较。 br />
现在假设您要在3D空间中对某些多边形进行排序，或者根据该人的地址距离某个位置的距离对个人
记录进行排序，或者在某些数学应用程序中按其特征值排序
矩阵，或按文件中某些文本的出现次数排序
文件。
通常，当您定义决策函数F（x，y）时，您将需要从要排序的元素中提取某些属性。对于
示例，当按空间标准对空间中的点进行排序时，需要计算该点的距离。当按人员的位置从数据库中对个人
记录进行排序时，决策函数
将需要从数据库中检索该人的地址，然后找到
该地址的坐标，用于计算从那里到给定坐标的距离
a的距离。在通过特征值对数学中的矩阵进行排序时，
顺序决策将首先计算矩阵的特征值。以上所有的共同主题是：他们都需要对每个元素进行一些非平凡的计算。
正如我们所看到的，订单决策函数F可能需要先对每个元素进行一些昂贵的计算，这几乎总是在排序时的情况下是b / b
除简单数字以外的元素。另外，我们知道分类算法需要多次调用F（x，y），即使
之前已经将x或y中的一个与其他人进行了比较。因此，这可能导致高效率的低效率。例如，您需要通过他们的
位置向您的家庭订购人员。所以当调用F（Mary，Jane）时，Mary的地址
首先从网络上的数据库中检索出来，
的坐标查找了她的地址在另一个数据库中然后使用球面几何计算到您的
住宅的距离。对Jane来说，完全相同的是
。但是稍后，它可能会调用F（Mary，Chrissy），
F（Mary，Jonesy），F（Mary，Pansy）等等，以及整个记录
对Mary的检索重复了很多次。
一个解决方案是，为每个
元素进行一次昂贵的提取，然后将其与相应的元素。假设
这个昂贵的提取函数叫做gist（）。所以，你创建一个
新列表（[玛丽，吉斯特（玛丽）]，[简，吉斯特（简）]，[约翰，吉斯特（约翰逊）]，
[Jenny，gist（Jenny）]，...）并对此列表进行排序，完成后，删除
相关的要点。这种技术有时被称为
decorate-sort-dedecorate。
在Perl编程中，这种装饰 - 排序 - dedecorate技术是狡猾的
$ b我们之前已经证明了$ b被称为Schwartzian变换。在
Python中，他们试图将这种技术融入到语言中，通过
添加a ?? keya ??可选参数，这是我们的gist（）函数。
----------
这篇文章存档于：
我会对有关Common Lisp，Scheme和
Haskell如何处理decorate-sort-dedecorate技术的评论感兴趣。特别是
，它是否以语言本身表现出来？如果没有，那么
通常如何在代码中执行？ （注意：请回复合适的团体
，如果它没有普遍的利益。谢谢）（我也感兴趣
Perl6或Python3000这样做，如果有重大改变他们的种类
功能）
谢谢。
Xah
a ??
Last year, i''ve posted a tutorial and commentary about Python and
Perl''s sort function. (http://xahlee.org/perl-python/sort_list.html)
In that article, i discussed a technique known among juvenile Perlers
as the Schwartzian Transform, which also manifests in Python as its
a??keya?? optional parameter.
Here, i give a more detailed account on why and how of this construct.
----
Language and Sort Optimization: decorate-sort-dedecorate
There are many algorithms for sorting. Each language can chose which to
use. See wikipedia for a detailed list and explanation:
Sorting_algorithma?? .
However, does not matter which algorithm is used, ultimately it will
need the order-deciding function on the items to be sorted. Suppose
your items are (a,b,c,d,...), and your order-deciding function is F.
Various algorithms will try to minimize the number of times F is
called, but nevertheless, F will be applied to a particular element in
the list multiple times. For example, F(a,b) may be called to see which
of a??aa?? or a??ba?? comes first. Then, later the algorithm might need
to call F(m,a), or F(a,z). The point here is that, F will be called
many times on arbitrary two items in your list, even if one of the
element has been compared to others before.
Now suppose, you are sorting some polygons in 3D space, or personal
records by the person''s address''s distance from a location, or sorting
matrixes by their eigen-values in some math application, or ordering
files by number of occurrences of some text in the file.
In general, when you define your decision function F(x,y), you will
need to extract some property from the elements to be sorted. For
example, when sorting points in space by a criterion of distance, one
will need to compute the distance for the point. When sorting personal
records from database by the person''s location, the decision function
will need to retrieve the person''s address from the database, then find
the coordinate of that address, that compute the distance from there to
a given coordinate. In sorting matrixes in math by eigen-values, the
order-decision will first compute the eigen-value of the matrix. A
common theme from all of the above is that they all need to do some
non-trivial computation on each element.
As we can see, the order-decision function F may need to do some
expensive computation on each element first, and this is almost always
the case when sorting elements other than simple numbers. Also, we know
that a sorting algorithm will need to call F(x,y) many times, even if
one of x or y has been compared to others before. So, this may result
high inefficiency. For example, you need to order people by their
location to your home. So when F(Mary,Jane) is called, Mary''s address
is first retrieved from a database across a network, the coordinate of
her address is looked up in another database. Then the distance to your
home are computed using spherical geometry. The exact same thing is
done for Jane. But later on, it may call F(Mary,Chrissy),
F(Mary,Jonesy), F(Mary,Pansy) and so on, and the entire record
retrieval for Mary is repeated many times.
One solution, is to do the expensive extraction one time for each
element, then associate that with the corresponding elements. Suppose
this expensive extraction function is called gist(). So, you create a
new list ([Mary,gist(Mary)], [Jane,gist(Jane)], [John,gist(John)],
[Jenny,gist(Jenny)], ...) and sort this list instead, when done, remove
associated gist. This technique is sometimes called
decorate-sort-dedecorate.
In Perl programing, this decorate-sort-dedecorate technique is sillily
known as Schwartzian Transform as we have demonstrated previously. In
Python, they tried to incorporate this technique into the language, by
adding the a??keya?? optional parameter, which is our gist() function.
----------
This post is archived at:
http://xahlee.org/perl-python/sort_list.html
I would be interested in comments about how Common Lisp, Scheme, and
Haskell deal with the decorate-sort-dedecorate technique. In
particular, does it manifest in the language itself? If not, how does
one usually do it in the code? (note: please reply to approprate groups
if it is of no general interest. Thanks) (am also interested on how
Perl6 or Python3000 does this, if there are major changes to their sort
function)
Thanks.
Xah
xa*@xahlee.org
a?? http://xahlee.org/
推荐答案
％w（FORTRAN LISP COBOL）.sort_by {| s | s.reverse}
==> [" COBOL"，" FORTRAN"，" LISP"]
-
Common Lisp确实杀了Lisp。期。 ......对Lisp来说是什么
C ++是C.一个完全忽略基础知识的怪物
语言设计，简单和正交开始
with。 --- Bernard Lang
%w(FORTRAN LISP COBOL).sort_by{|s| s.reverse}
==>["COBOL", "FORTRAN", "LISP"]
--
Common Lisp did kill Lisp. Period. ... It is to Lisp what
C++ is to C. A monstrosity that totally ignores the basics
of language design, simplicity, and orthogonality to begin
with. --- Bernard Lang
Python也有这样的机制，特殊的`__cmp __（）`方法
基本上具有相同的签名。装饰，排序，
un-decorate模式解决的问题是这个对象特定的比较操作
只使用* one *标准。
假设你有一个名字，姓氏，出生日期的'Person`对象，
等等。当你有一个这样的对象列表，并希望按名称
或出生日期对它们进行排序时，你不能使用`compareTo（）`方法。
Ciao，
Marc''BlackJack''Rintsch
Python has such a mechanism too, the special `__cmp__()` method
has basically the same signature. The problem the decorate, sort,
un-decorate pattern solves is that this object specific compare operations
only use *one* criteria.
Let''s say you have a `Person` object with name, surname, date of birth and
so on. When you have a list of such objects and want to sort them by name
or by date of birth you can''t use the `compareTo()` method for both.
Ciao,
Marc ''BlackJack'' Rintsch
这篇关于排序优化技术：decorate-sort-dedecorate的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！