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

Question

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

摘自2010年7月14日Mark Engelberg在该讨论线程中的信息。

仅通过对核心进行补丁，才可以在优先级映射上正确实现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月编写，并附在他发送到描述中链接的dev线程消息中。他在该线程中描述了自己的方法，内容如下：

---

同时，为了讨论如何修改subseq，我附上一个提议的补丁。这个补丁通过修改Sorted接口的seqFrom方法来接受一个额外的"inclusive"（包含）参数（即 <= 和 >= 是包含的，而 < 和 > 不是）。

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

尽管我认为这是解决subseq扩展性问题最干净的方式，但这种对seqFrom的修改将破坏任何目前覆盖此方法的人。我没有在clojure.contrib见到任何这样的类，所以我认为这不是一个问题，但如果这让你担心，我的另一个想法是在subseq内部通过将调用next更改为调用drop-while来完全解决这个问题。我已经为此编写了代码，并确认它可以工作，如果需要，我可以提供那个备选补丁。

我还可以提供一种使用drop-while在clojure.core/subseq和rsubseq中的补丁，如果这种方法比这个补丁更喜欢。

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

Patch文件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。由于代码和测试有不同的作者，因此将它们保存在不同的文件中，将来更新此类补丁会更方便。

Answer 7

评论者：marco.m

你好，有什么消息吗？

Answer 8

评论者：alexmiller

按照目前的实现，这个改变将破坏Sorted中的兼容性，所以我认为仅在这一问题上，那个特定的补丁就不应该用于Sorted。

但可能更专注于宏观层面。与其推动subseq及其含义，不如考虑一些抽象接口，它能捕捉 Sorted之外的一些有趣的东西。我认为投入任何思考都是值得的。特别是，若能有一个关于 2 或 3 个现有集合可能会从中受益的想法就很好。如果我们找不到 2-3 个，我认为我会将它归档，直到有令人信服的案件为止。特别是，这看起来像是 SortedSet -> NavigableSet 在Java之间有些对应关系，也许需要类似的东西。

Answer 9

评论者：marco.m

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

Answer 10

评论者：markengelberg

我认为衡量一种语言的重要指标是其内部抽象的程度，这是用于其自身数据结构的，它们开放度决定了其扩展性。正因为如此，我一直认为这是一个值得解决的问题。subseq 和 rsubseq 中嵌入的假设，即排序集合只能有唯一的排序值，在初始代码中显然是一个疏忽，这不仅阻止了 priority-map 与 subseq 和 rsubseq 的挂钩，而且还阻止了多个由 Marczyk 设计的巧妙数据结构。我认为我们在 Sorted 中已经找到了有趣的东西，我们不需要试图理解 —— 问题是，按照当前的定义实现 Sorted 的 seqFrom 接口对于 subseq 和 rsubseq 来说并不足够，因为他们无法提供指定的行为。你可以把这一点看作是 Sorted 或子seq / rsubseq 的缺陷。

Marco，clojure.data.priority-map 的最新版本包含一个修补过的 subseq 和 rsubseq 版本，它不依赖于更改基础 Sorted 接口来修复在具有重复排序值的排序集合上的不正确行为。您可以使用该实现与 priority-map 或任何其他类似的您可能正在构建的数据结构。

我不能代表 Clojure 团队，但我想，如果有人采取主动进行对 clojure.data.priority-map 中的 subseq 和 rsubseq 进行广泛基准测试，并确定现有排序的 Clojure 数据结构没有性能影响，那么他们可能更愿意将修补的版本移入 Clojure 的核心，因为这将带来明显的好处而没有副作用。（或者，如果与 Clojure 的现有排序数据结构相比存在性能影响，找出如何调整以避免性能损害，这应该很容易做到）。对 subseq 和 rsubseq 所需的更改很简单：将当前通过调用 rest 来删除第一个项目将 <= 子序列转换为 < 子序列的代码更改为调用 drop-while 来删除序列前面的所有相等项目，因为有多个这样的项目。当这个问题首次被提出时，核心团队成员表示他们更希望在这一协议级别解决这个问题，但如果这不再可行，我希望看到对 subseq 和 rsubseq 的这种更改得到考虑。这似乎是解决阻止 subseq 和 rsubseq 与所有满足 Sorted 序列 from 实现的数据结构一起工作这一长期问题的简单方法。

Answer 11

评论者：alexmiller

我只是想提一下，这是我第一次记得查看这个票据，因为它基本上早于我在 Clojure 核心中参与的时期。我知道已经很多年了，我正在尝试真正诚实地思考这。但恐怕我会提出一些愚蠢的问题，因为我正在重新走您已经走过的道路。

我在让良好的集合特质能够被 Clojure 核心内外部的 impls 使用这一方面完全同意。

关于更改协议的可行性，我想也许你误解了我的意图。我们当然可以更改 / 扩展协议，但我们只需以不中断（保留现有内容）的方式，而不是中断（通过更改现有方法签名）来执行。我反对的是更改 Sorted.seqFrom() 的签名，因为这将破坏所有现有 impl - 这只是一个不可行的方案。但我们完全可以将 Sorted 扩展到 Sorted2（或任何更有意义的名称）并具有新的 seqFrom 等价。subseq 代码可以在 coll 是 Sorted2 时做最好的事，如果只 Sorted，则回归到另一种方法。有许多这样做的方法，但希望你能理解我的意图——现有内容继续按原样工作，如果有新内容，它将被利用。

备份过程中，看起来 seqFrom 和类似的方法还未充分丰富，无法涵盖跨不同数据结构可能希望的所有需求。我仍然认为 NavigableSet 包含了很多好的前期思考（并非直接说是解决方案，但确实是在相同的问题领域），并且更广泛地查看这些年来添加的其他数据结构会很有益处，看看我们能启用哪些功能。

实际上，子序列的实现相当糟糕，并且依赖于许多移动部件和假设。也许该子序列操作实际上应该直接由集合来完成。

Answer 12

评论者：markengelberg

问题的关键在于 subseq 允许使用 <=, <, >=, > 操作，但 seqFrom 仅允许 <=, >=，接着 subseq 以一种会导致最多一个项目被排除的方式来“处理”seqFrom 的输出并转换为 <, > 的方式，如果有多个相等的项，这就不起作用了。我认为这是一个设计缺陷，因为你可以创建一个 seqFrom 的实现，它正好完成所需的功能（生成适当的 <= 和 >= 子序列），但 subseq 和 rsubseq 可能仍然不能正确运行。

回想起来，当时的思考似乎是，"嘿，seqFrom 和 subseq/rsubseq 之间存在这种不匹配有点糟糕。让我们让集合在其 seqFrom 的实现中处理所有子序列/rsubseq 逻辑，这样就不需要将两个可能的子序列揉成四种可能的子序列了。"

可以通过修复 subseq 和 rsubseq 来舍弃所需的项目数量，而不需要对接口进行任何修改，但如果集合可以直接执行所有逻辑，那么集合可能比仅在 subseq 和 rsubseq 层面进行修复更高效地创建 <, > 子序列。

我明白了你的 Sorted2 接口观点。

Answer 13

评论者：alexmiller

我觉得这是一个有益的关于问题的重述。我觉得用丢弃逻辑“修复”subseq 只是在更大程度上掩盖这种不匹配，而这个不匹配如果允许集合直接满足用户的需求，会更有帮助且更高效。

Answer 14

评论者：alexmiller

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

Answer 15

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