施瓦茨变换的历史

2016年9月2日，作者：brian d foy

施瓦茨变换的历史非常引人入胜，充满了阴谋、竞争的哲学以及跨语言的不情愿合作。施瓦茨变换是指一种缓存的键排序算法的具体实现。

它的首次公开出现可能是在1994年12月16日，Randal Schwartz在Usenet上对Ken Brown请求帮助的回应帖子中

我在按记录中最后一个字段的最后一个单词排序时遇到了麻烦

Ken Brown

Randal在他的回复中包含了以下代码

#!/usr/bin/perl
require 5; # new features, new bugs!
print
  map { $_->[0] }
  sort { $a->[1] cmp $b->[1] }
  map { [$_, /(\S+)$/] }
  <>;

Randal没有给它命名。他编写了代码，基本上就结束了。他说他正在教一个Perl课程时休息，所以他的回复简短且未解释 - 这对于一名经验丰富的Usenet居民来说是典型的（他说他曾在半小时内读完整个Usenet）。我认为他没料到它会有那么大的麻烦。

他的代码并不复杂。它是一个大的语句，但当我把它教给Perl课程的学生时，我告诉他们从后往前读（任何列表管道的有用技巧）

1. 第一步计算排序的键。它将该键与原始值结合成一个元组。
2. 中间步骤对元组中的计算元素进行排序。
3. 最后一步从元组中提取原始值。

你可能想象不到当时这对人们来说有多么震惊。Perl 5在1994年10月正式发布，但第一版开发版本早在1993年中叶就已经出现。Randal肯定是在Perl 5一出来就开始玩它了。这意味着大多数Perl程序员还没有看到像map函数或引用这样的新特性。他们当然对这些想法并不熟悉。

然而，Randal知道来自LISP的装饰-排序-取消装饰技巧，特别是因为他坚定地站在编辑器之战中的emacs阵营。Renzo在代码审查中修正了我的LISP版本尝试

(defun schwartzian-transform (list costly-function predicate)
"sort a list of objects over the value of a function applied to them,
by applying the Schwartzian Transform (https://en.wikipedia.org/wiki/Schwartzian_transform)
the parameters are the list, the function, and the predicate for the sort."
  (mapcar #'cdr
      (stable-sort (mapcar (lambda (x)
                 (cons (funcall costly-function x) x))
                 list)
             predicate
             :key #'car)))

(require :sb-posix)
(schwartzian-transform
 (directory "/etc/*")
 (lambda (x) (sb-posix:stat-mtime (sb-posix:stat x)))
 #'<=)

即使只有一点LISP知识，你也可以弄清楚相同的算法。你看到mapcar、stable-sort和mapcar。 （我使用了SBCL）

1995年，Tom Christiansen写了比你所知道的关于排序的一切都多，并详细介绍了Randal的代码，尽管当时还没有给它命名。他并不太喜欢它，但，为了公正，他在最后说

我并不是在嘲笑Randal，只是在开个小玩笑。他只是试图表现得聪明一点，这就是他做的事。我只是提交了一章样本供他审阅，以供传说中的阿尔帕卡书使用 :-)

Tom Christiansen

Tom提到了《学习Perl对象、引用、对象和模块》，这本书要到2003年才会出现（现在称为Intermediate Perl）。有趣的是，在那年的同一时间，Python中的文本处理（Google Books）提到了它。

在他的Usenet帖子一个月后，Randal在1996年1月的Unix Review专栏中写了关于他的decorate-sort-undecorate语法的文章，但那时他还没有给这个技巧命名。

获得名称

1995年8月，Bennett Todd在Perl讨论组中用“施瓦茨变换”回答了一个排序问题

或者为了更高的效率，确保对每个记录的调用只发生一次，而不是大约NlogN次，使用施瓦茨变换:-)

Bennett Todd

@keys = map { $_->[0] }
    sort { $a->[1] <=> $b->[1] or $a cmp $b }
    map { [ $_, datexform($foo{$_}) ] } keys %foo;

这是我能找到的第一个将Randal的姓氏与这种技术联系起来的例子。人们已经看到并理解了这项技术，并且它已经开始有了名字，但还不是成语。它也没有确定一个名字。

Tom Christiansen于1996年4月在comp.lang.perl.misc论坛上的帖子“按时间戳顺序读取目录？”中展示了一些排序方法的基准测试。他将其中一个命名为“Schwartzian变换”。

7月份，Colin Howarth开始了“Schwartzian变换的%$self……帮助？”这一主题的讨论。

10月份，Tom在perllol的扩展草案中发布了Perl数据结构食谱的一部分，这最终演变成了perldsc和perllol。他使用了全称“Schwartzian变换”。这个术语开始流行起来。

获得知名度

我仍然对Randal发布这个感到愤怒

Tom Christiansen

Tom在12月写了这些，他没有委婉。现在这看起来可能有点刻薄，但当时，Tom正在努力让人们爱上Perl。他传播这种语言，不想让人们因为看起来奇怪的代码而感到害怕。他在人们谈论Perl的任何地方，这对我们来说都是好事。这意味着他实际上在支持他写的、他喜欢的、人们不理解的语言。在他的Perl传教士角色中，他被询问了一些他自己不会写的问题。

后来，在同一条线程中，他又给了它另一个名字，“Black变换”。他利用了Randal的日耳曼姓氏的翻译，反映了他的个人观点。这个名字并没有留下。

就像大多数漫长的Usenet论坛一样，人们具体不喜欢代码的哪些地方并不完全清楚，甚至不清楚是否存在共识的投诉。一些投诉围绕Randal缺乏注释。有些人希望Perl一开始就能被不熟悉这种语言的人理解。而其他人虽然对高级编程技能很舒服，但并不在意。这种紧张关系至今仍然存在。

记住，引用和方法符号是新的语法。熟悉Perl 4的人仍在学习Perl 5。Perl还没有发展出用于列表处理的成语（LISP，当然），因此人们似乎并不太适应堆叠的列表操作。有些人只是讨厌函数式编程和LISP。

还有一部分人更愿意使用易于学习的编程语言，而不是更强大但更神秘的。

在那个时期，Joseph Hall写了关于Schwartzian变换的更多信息（互联网档案馆）。很难确切知道他是什么时候写的，但互联网档案馆中最早的副本注明最后修改于1997年1月。Joseph使用他的PeGS（Perl图形结构）展示了它们的作用。这可能是除Usenet之外的第一提及。它也是他1998年书Effective Perl Programming中条目的基础。

同时，Joseph在与Randal在Stonehenge咨询公司一起开发Perl课程。我对这个时间表不是很清楚，但他的课程最终演变成了书《学习Perl对象、引用和模块》（后来更名为Intermediate Perl）。是他提出了吉尔igans Island的例子，但他在PeGS和Schwartzian变换方面的手艺体现在那本书和课程中。

《有效的Perl编程》可能是第一本提到这个转换的书，他使用了之前已经写过的内容。尽管我也参与过那本书的第二版，但我认为Joseph的原版在Amazon.com上仍值4美元。这是Perl历史上最好的Perl写作之一。

1998年，这个转换也出现在了《Perl食谱》第一版中，Tom将其称为Schwartzian转换。我不知道是谁首先将其输入到手稿中，所以可能是一个平局。Tom和Joseph可能需要在他们之间解决这个问题。

《精通Perl算法》（Google Books）在1999年涵盖了这个转换，而《Perl CGI编程》（Google Books）在2000年提到了它。之后，“Schwartzian转换”这个词在许多地方出现，甚至在一些Ruby、Python、Jython的书中。

以下是一些从那个长线程中摘录的有趣引言，二十年后看起来似乎有些过时。我最喜欢的是一个预言性的

我想这个代码块是否会永远困扰我们。

Eric Arnold

的确，它自那时以来一直困扰着我们，但故事还没有结束。

变体

Randal使用匿名数组的方式很有趣，但这并不是装饰原始值的唯一方式。你可以计算值并将它们存储在哈希中。Joseph Hall提出了一个叫做Orcish Maneuver的东西——可能是对Orc（或许）和“OR Cache”的巧妙双关。这并不使用map函数或引用

my @sorted = sort {
  ( $times{$a} ||= -M $a ) <=>
  ( $times{$b} ||= -M $b )
} @old_array;

Joseph使用哈希来存储可能昂贵的排序值。如果该键尚不存在，则他计算并存储它以供下次使用。这个惯用法依赖于Perl赋值返回所赋值的特性。

感谢因斯布鲁克2016年Alpine Perl研讨会为赞助关于这一历史的演讲。您可以在Slideshare上找到那次演讲的幻灯片。

顺便说一句，您会在Perl源代码中找到大量《魔戒》的引用。

这篇文章最初发布在PerlTricks.com上。