关于支持优先级映射的subseq和rsubseq增强？

Question

在http://groups.google.com/group/clojure-dev/browse_thread/thread/fdb000cae4f66a95上查看开发线程。

以下内容摘自Mark Engelberg在2010年7月14日讨论线程中的消息

只有通过修改核心，才能正确地实施对优先级映射的subseq。subseq通过将其大部分行为委托给Java方法seqFrom、seq、entryKey和comparator来实现其多态行为（针对排序映射和排序集合）。所以从理论上讲，您应该能够通过自定义这些方法来扩展subseq以适用于任何新的集合。

然而，当前subseq的实现假定排序所依据的值是唯一的，这对于内置排序映射来说是合理的假定，因为它是基于唯一键进行排序的，但它使得subseq行为难以扩展到其他类型的集合。为了给库设计者提供能够钩入subseq的能力，这种假设需要被移除。

方法

1. 一种简单的方式是，当subseq对seqFrom的结果进行按摩使其成为严格大于序列时，允许丢弃多个相等值。

2. 更好的方式是，让subseq将更多的逻辑委托给seqFrom（通过在方法调用时添加一个额外的标志来指出您是想得到大于、大于等于还是严格大于）。这将允许获得最佳效率，并为未来的扩展提供最大的可能性。
   注意：在有些情况下，subseq目前返回()而不是nil。如果这个想法没有落实，我们可能仍然想修复这个问题。

补丁clj-428-code-v5.patch实现了上述方法#2。它保留了当前返回()而不是nil的行为。

补丁：clj-428-code-v5.patch测试在clj-428-tests-v5.patch中

补丁：clj-428-code-v5.patch在clj-428-tests-v5.patch中进行了测试

Answer 1

评论者：importer

从http://www.assembla.com/spaces/clojure/tickets/428转换而来

Answer 2

评论人：jafingerhut

2013年4月28日的补丁文件clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v1.txt由Mark Engelberg在2010年7月编写，并将其附加在描述中链接的开发线程发送的一条消息中。他在该线程中描述了他的方法，此处复制如下

---

在此期间，为了启动关于如何修改subseq的讨论，我已经附加了一个提议的补丁。此补丁通过修改Sorted接口的seqFrom方法来接收一个额外的“inclusive”参数（即，<=和>=是包含的，而<和>是不包含的）。

在这个补丁中，我没有解决我在之前提出的一个问题，即subseq的名称是否意味着它应该返回一个序列而不是一个seq（换句话说，nil而不是()）。如果需要seq行为，则必须在调用take-while之前调用seq。但是，目前我只是在使行为符合当前的行为。

尽管我认为这是解决subseq扩展性问题最干净的方式，但seqFrom的变化将破坏当前覆盖该方法的任何用户。我没有在clojure.contrib中看到这样的类，因此我认为这不是一个问题，但如果这是一个担忧，我的另一个想法是在subseq内部完全解决这个问题，通过将next的调用更改为drop-while的调用。我已经编码了这个方法以确认它可行，并可以提供这个替代补丁，如果需要的话。

如果有人更喜欢这种补丁的方法而不是这个补丁中的方法，我也可以提供在clojure.core/subseq和rsubseq中使用drop-while的补丁。

Answer 3

评论人：jafingerhut

2013年4月28日的clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v2.txt与clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v1.txt相同（即将被删除），除了它为subseq和rsubseq添加了测试，并修复了该补丁中的一些错误。该方法与上面描述的补丁相同。

Answer 4

评论人：jafingerhut

2013年5月1日的补丁文件clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v3.txt与clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v1.txt相同，仍然包含v2中提到的错误修复，但移除了补丁中的一些不必要更改。对于-v1.txt的评论仍然适用于这种方法。

Answer 5

评论人：jafingerhut

补丁文件 clj-428-v4.diff 与之前评论中提到的 clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v3.txt 完全相同，只是它更新了一些 diff 上下文行，以便它能干净地应用到最新的今天 Clojure master 版本。

Answer 6

评论人：jafingerhut

文件 clj-428-code-v5.patch 和 clj-428-tests-v5.patch 与之前的 -v4 附件相同，只是它们能干净地应用到最新的 Clojure master 版本。由于代码和测试是由不同的作者编写的，因此将它们放入独立的文件中将方便 future 更新这样的补丁。

Answer 7

评论者：marco.m

你好，有什么消息吗？

Answer 8

评论者：alexmiller

按照现在的实现，这个更改将导致 Sorted 中的 breaking change，所以我认为仅仅在这个前提下，那个特定的补丁就不能开始实施。

但可能还是应该关注高层次的问题。与其推动 subseq 及其含义，不如考虑一些抽象接口来捕获一些有趣的东西，而不仅仅是 Sorted 中的东西。我相信对这个的想法都会是有价值的。特别是，最好有一个想法，2 个或 3 个现有的集合可能从中受益。如果我们找不到 2-3 个，那么我认为我会将它放在 backlog 中，直到有令人信服的证据。特别是，这看起来像 SortedSet -> NavigableSet 在 Java 中的对应关系，可能需要类似的做法。

Answer 9

评论者：marco.m

感谢 Alex，真的非常感谢你的回复和你的思考 :-)

Answer 10

评论者：markengelberg

我认为语言的一个重要衡量标准是其内部抽象的程度，这些抽象用于其自身的数据结构，并且可以扩展。因此，我一直相信这是一个值得解决的问题。subseq和rsubseq在内部预先设定的假设——排序集合只能有唯一的排序值——无疑是初版代码中的疏忽。这不仅仅阻止了优先映射与subseq和rsubseq融合，还阻止了Marczyk设计的几个巧妙的数据结构。我认为sorted中并没有超过本身的价值需要我们去理解——问题在于，按照目前的定义，sorted的seqFrom接口实现对于subseq和rsubseq目前来说不足以提供它们指定的行为。你可以将其视为Sorted的缺陷，或者是subseq/rsubseq的缺陷。

Marco，clojure.data.priority-map的最新版本包含一个修复版的subseq和rsubseq，它不依赖于对底层Sorted接口的改变，以修复在具有重复排序值的排序集合上的不正确行为。你可以自由地使用这个实现与优先映射或其他你可能正在构建的类似数据结构。

我不能代表Clojure团队，但我想如果有人主动对clojure.data.priority-map中的subseq和rsubseq进行广泛的基准测试，并证实它们对现有的排序Clojure数据结构没有性能影响，那么他们可能会愿意将那些修复版本移至Clojure的核心，因为这会有明显的益处而无任何弊端。（或者，如果在Clojure现有排序数据结构上有所性能损失，找出如何调整以消除性能损失，这应该很容易做到）。subseq和rsubseq所需的变化很简单：它们当前通过调用rest来丢弃第一个项目将一个<=子序列转换为<子序列，我只是将它们改为调用drop-while来丢弃序列前面的所有等价项目，因为可能有多个。当这个问题第一次被提出时，核心团队成员表示他们更希望看到这个问题在协议层面上得到修复，但如果没有可行性，我希望这个改变被考虑用于subseq和rsubseq。这似乎是解决这个长期存在的、阻止subseq和rsubseq与所有实现Sorted seqFrom协议的数据结构工作的简单方法。

Answer 11

评论者：alexmiller

只想提一下，这是我第一次记得查看这个工单，因为它基本上在我参与Clojure核心之前。我知道这已经很多年了，我正在试图真正地思考这个问题。但在我重新走你走过的每一步时，我可能会问一些愚蠢的问题。

我一定同意，使好的收集特性能够被Clojure核心内外部impl使用。

至于修改协议的可行性，我想你可能误解了我的意图。我们当然可以修改/扩展协议，我们只需要以一种成长的方式（保留现有内容）而不是破坏的方式（通过改变现有方法签名）来做。我反对的是修改Sorted.seqFrom()的签名，这会破坏所有现有的实现——这根本无法实现。但是将Sorted扩展到Sorted2（或任何更有意义的名称）并添加一个新的seqFrom级别是完全可行的。子序列代码可以在集合是Sorted2的情况下做最好，如果没有，则回退到其他操作。有各种方法可以实现这一点，但希望你能理解其意图——现有内容继续工作而不做任何改变，在新内容可用的情况下加以利用。

备份数据时，感觉似乎 seqFrom 及相关功能不足以涵盖在不同数据结构间可能希望实现的所有需求。我仍然认为 NavigableSet 在之前有很多好的思考（不是直接说这是一个直接的答案，但确实是同一个问题领域），并且进一步广泛地查看那些在此期间添加的其他数据结构，看看我们能实现什么将会是有益的。

实际上，子序列的实现相当粗糙，依赖于许多动作部件和假设。也许整个子序列操作实际上应该直接由集合来执行。

Answer 12

评论者：markengelberg

问题的关键在于 subseq 允许使用 <=, <, >=, >，但 seqFrom 只允许 <=, >=，然后 subseq 以一种会去除一个元素的方式来“调整”seqFrom的输出以成为 < 或 >，这在有多个相同元素的情况下是不行的。我认为这是一个设计缺陷，因为你可以创建一个符合seqFrom实现的整个实现（生成适当的 <= 和 >= 子序列），但subseq和rsubseq可能仍然无法正确工作。

在以前，这种 seqFrom 和 subseq/rsubseq 之间的不匹配似乎是相当糟糕的。我们将在 seqFrom 的实现中让集合做所有子序列/rsubseq逻辑，这样就不需要将两种可能的子序列压缩成四种。

可以通过使子序列和rsubseq丢弃所需的任何数量的元素来修复它们，而不需要对接口进行任何更改，但如果有集合可以直接执行所有逻辑，那么它可能比在子序列和rsubseq级别进行修复更有可能更有效地创建 <, > 子序列。

我理解你的关于Sorted2接口的观点。

Answer 13

评论者：alexmiller

我觉得这个问题表述得相当有帮助。我觉得用丢弃逻辑“修复”subseq，实际上只是在掩盖这种不匹配，而更有帮助（更有效率）的是允许集合直接执行用户需要的操作。

Answer 14

评论者：alexmiller

例如，你可以有一个可子序列接口，如果subseq/rsubseq检测到它，它们只需将控制权传递给集合。

Answer 15

参考： https://clojure.atlassian.net/browse/CLJ-428（由stu报告）