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

Question

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

摘自 July 14, 2010 在该讨论线程中马克思·恩格尔伯格的消息

仅通过修改核心功能，才可以在优先级映射中正确实现 subseq。subseq 通过将大部分行为委托给 Java 方法 seqFrom、seq、entryKey 和 comparator 实现其多态行为（针对排序映射和排序集合）。因此，理论上，您应该能够通过自定义这些方法将 subseq 扩展到任何新的集合。

然而，subseq 的当前实现假设您正在排序的值是唯一的，对于按唯一键进行排序的内置排序映射来说，这是一个合理的假设，但这使得无法将 subseq 行为扩展到其他类型的集合。为了使库设计人员能够挂钩到 subseq，需要取消这个假设。

方法

1. 一种简单的方法是在 subseq 将 seqFrom 的结果按摩塑成严格大于序列时，允许删除多个相等值。

2. 一种更好的方法是让 subseq 将更多的逻辑委托给 seqFrom（通过在方法调用中添加一个额外的标志来判断你
   想要大于等于还是严格大于）。这将允许最佳效率，并为未来的扩展提供最大的可能性。

注意：在某种情况下，subseq currently 返回 () 而不是 nil。如果这个想法的其他部分死亡，我们可能仍然想要修复它。

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

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的名字是否暗示它应该返回一个序列而不是序列集（换句话说，是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。由于代码和测试由不同的作者完成，所以将它们分别放在不同的文件中会更便于未来的更新。

Answer 7

评论由：marco.m

你好，有什么新消息吗？

Answer 8

评论由：alexmiller

按照目前的实现，这个改动将会破坏 Sorted 的兼容性，因此我认为仅凭这一点，那个补丁就不适用于 Sorted。

但最好还是关注一下整体。与其着眼于 subseq 及其含义的推广，不如考虑一个抽象接口，它能够包含比 Sorted 更多有趣的东西。我觉得无论在这种想法上投入多少思考都是有价值的。特别是，弄清楚两个或三个可能从这之中获益的现有集合会比较有用。如果我们找不到两个或三个，那么我觉得我会将其暂存，直到有更有说服力的理由。特别是，这似乎与 SortedSet -> NavigableSet 在 Java 中的情况相呼应，并且可能需要类似的东西。

Answer 9

评论由：marco.m

感谢 Alex，非常感激您的回复和您所付出的思考 :-)

Answer 10

评论由：markengelberg

我认为衡量一门语言的重要指标是其内部抽象的开闭程度，这些抽象被用于构建自己的数据结构。正因为如此，我长期以来一直认为这是一个需要关注的问题。在子序列和rsubseq中嵌入的假设——排序集合只能拥有唯一的排序值—确实是在初始代码中犯的一个错误，这个错误不仅阻止了优先级映射从子序列和rsubseq中挂钩，还阻碍了Marczyk的一些巧妙的数据结构。我认为 Sorted 之外没有有趣的东西需要我们去理解——问题在于，按照当前定义的子序列和rsubseq，实现Sorted的 seqFrom 接口目前还不够充分来提供它们指定的行为。你可以把这看作是Sorted的不足，或者子序列/rsubseq的不足。

Marco，最新的 clojure.data.priority-map 版本包含了一个修复版的 subseq 和 rsubseq，它不依赖于对底层 Sorted 接口的更改来修复其在排序集合（包含重复排序值）上的错误行为。请自由地使用这个实现与优先级映射或任何其他您可能正在构建的类似数据结构。

我不能代表 Clojure 团队说话，但假如有人发起对 clojure.data.priority-map 中的子序列和rsubseq进行大量基准测试，并确立这不会对现有的排序 Clojure 数据结构造成性能影响，那么他们可能会更倾向于将这组补丁版本移入 Clojure 的核心，因为这将带来明确的好处而没有副作用。（或者，如果与 Clojure 的现有排序数据结构相比存在性能影响，找出如何调整使其没有性能惩罚的方法，这应该很容易做到）。对子序列和rsubseq所需的变化很简单：他们目前通过调用 rest 来丢弃第一个元素，将 <= 子序列转换为 < 子序列；我仅仅将它们改为调用 drop-while 来从序列前部丢弃所有相等的元素，因为可能不止一个。当这个问题首次被提出时，核心团队成员表示他们希望看到这个问题在协议层面得到解决，但如果这已不再可行，我希望看到这个对子序列和rsubseq的更改被考虑。这似乎是解决这一长期问题的一个简单方法，这个长期能够阻止子序列和rsubseq与所有满足Sorted的seqFrom实现的数据结构一起工作。

Answer 11

评论由：alexmiller

我只是想提到这是我第一次记得查看这个票据，因为它很大程度上早于我在 Clojure 核心中所参与的活动。我知道过去几年了，我尝试真诚地思考这一点。但在我重现你的任何路径时，我可能还会提出一些愚蠢的问题。

我肯定同意使好的集合特性能够被 Clojure 核心内外部的实现所利用。

关于更改协议的可行性，我认为你可能误解了我的意图。我们当然可以更改或扩展协议，但我们只需以一种可以增长（保留现有内容）而不是破坏（通过更改现有方法签名）的方式来做。我对更改Sorted.seqFrom()签名的反对意见是，这会破坏所有现有的实现 - 这根本不可行。但将Sorted扩展到Sorted2（或任何更有意义的名字）并引入新的seqFrom算术是完全可以接受的。然后子序列代码可以在集合是Sorted2的情况下执行最佳操作，如果只是Sorted，则回退到其他操作。有多种方法可以实现这一点，但希望你能理解意图 - 现有内容保持不变，如果有新内容可以利用。

回顾一下，seqFrom及其相关内容似乎不足以涵盖不同数据结构可能需要的所有内容。我仍然认为NavigableSet有很多好的前期思考（我不是说它是一个直接的答案，但它是同一个问题区域），看一看近几年添加的其他一些数据结构，看看我们能做什么是有益的。

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

Answer 12

评论由：markengelberg

问题的核心在于，子序列允许 <=、<、>=、>，但seqFrom只允许 <=、>=，然后子序列以丢失一个项目的方式对seqFrom的输出进行“按摩”，以转换为 <、>，这在有多个相等的项时不起作用。我认为这是设计缺陷的原因是，你可以创建一个序列的实现在seqFrom中做恰好需要做的事情（生成适当的 <= 和 >= 子序列），但子序列和逆子序列可能仍然不正确。

很久以前，想法似乎是，“嗨，这个seqFrom和subseq/rsubseq之间的差异有点混乱。让我们让集合在其seqFrom实现中以所有subseq/rsubseq逻辑进行子序列/逆序列，这样就不需要将两个可能的子序列按摩成四个可能的子序列。”

有可能修复子序列和逆序列，以便丢失所需的项目，而无需更改接口，但如果集合可以直接进行所有逻辑，则集合可能比在子序列和逆序列级别进行修复更有效地创建 <、> 子序列。

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

Answer 13

评论由：alexmiller

我认为这是一个有用的 问题重述。我认为用drop逻辑“修复”子序列只是在弥补这种脱节，而当它更有帮助（更高效）时，允许集合直接做到用户所需的事情。

Answer 14

评论由：alexmiller

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

Answer 15

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