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中

Answer 1

评论者：importer

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

Answer 2

评论者：jafingerhut

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

---

同时，为了启动关于如何修改子序列的讨论，我附上了一个提案补丁。这个补丁通过修改Sorted接口中的 seqFrom 方法来接受一个额外的“inclusive”参数（即，<=和>=是包含的，< 和 > 不是）。

在这个补丁中，我没有解决我之前提出的一个问题，即子序列名称是否暗示它应该返回一个序列而不是序列（换句话说，nil 而不是 ()）。如果希望有 seq 行为，则需要在 take-while 调用周围包装一个对 seq 的调用。但目前为止，我只是让行为与当前行为匹配。

虽然我认为这是解决 subseq 扩展性问题最干净的方法，但 seqFrom 的更改将中断任何当前覆盖该方法的程序。我没有在 clojure.contrib 中看到这样的类，所以我认为这不是一个问题，但如果这成为问题，我的另一个想法是在 subseq 中完全通过将 next 调用改为 drop-while 调用来修复问题。我已经编写了这个代码以确认它可行，如果需要，我可以提供该替代补丁。

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

Answer 3

评论者：jafingerhut

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

Answer 4

评论者：jafingerhut

补丁文件 clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v3.txt，日期为2013年5月1日，与 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之外的一些有趣内容。在这个方面所投入的任何思考我认为都是值得的。特别是，了解到2到3个现有集合可能会从中受益是很好的。如果我们找不到2到3个这样的集合，那么我认为我们会将其归档，直到有令人信服的理由。特别是，这似乎与Java中的SortedSet -> NavigableSet存在某种对应关系，可能需要进行类似处理。

Answer 9

评论者为：marco.m

感谢Alex，非常感激您的回复和对这个问题所投入的思考 :-)

Answer 10

评论者为：markengelberg

我认为，衡量一种语言的重要指标是它的内部抽象程度，这些抽象用于构建自己的数据结构，并且这些抽象是否能够方便地扩展。正因为如此，我一直认为这是值得解决的问题。在subseq和rsubseq中内嵌的假设是Sorted集合只能具有唯一排序值，这肯定是在初始代码中存在的一个疏漏，这不仅阻止了优先映射（priority-map）与subseq和rsubseq挂钩，还阻止了几种Marczyk设计的巧妙的数据结构。我认为，在Sorted中，并没有什么特别有趣的东西需要我们去理解——问题在于，实现Sorted的seqFrom接口目前不足以让subseq和rsubseq按照它们当前的定义提供所需的行为。你可以将其视为Sorted的缺陷，或者subseq/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 seqFrom实现的复合结构一起工作。

Answer 11

评论者为：alexmiller

我想说的是，这是我第一次记得查看这个工单，因为它基本上在我参与Clojure核心之前。我知道已经过去很多年了，我正在努力真诚地思考这个问题。但我在重新审视你的路径时可能会问些愚蠢的问题。

我在这一点上与使优良的集合特性能够被Clojure核心内外部的impl使用完全同意。

关于更改协议的可行性，我认为你可能误解了我的意图。我们当然可以更改或扩展协议，但我们只需以扩展（保留现有内容）而不是破坏（通过更改现有方法签名）的方式进行。我反对的是更改Sorted.seqFrom()的签名，因为这会破坏所有现有的实现 - 这根本不可行。但是，将Sorted扩展到Sorted2（或任何更有意义的名称）并添加新的seqFrom权重新完全没问题。子序列代码可以在集合并排序为Sorted2的情况下执行最佳操作，如果只是Sorted，则回退到其他操作。有多种方法可以实现这一点，但希望你能理解意图 - 持续工作而不更改现有内容，当可用时利用新内容。

追溯一下，seqFrom及其朋友似乎不足以涵盖可能在不同数据结构中期望的所有事物。我仍然认为NavigableSet有很多好的先前思考（不说是直接答案，但真的是同一个问题领域），并且广泛研究近年来添加的其他数据结构可能会很有益处。

实际上，子序列实现非常糟糕，依赖于很多移动部件和假设。也许整个子序列操作应该直接由集合并排序执行。

Answer 12

评论者为：markengelberg

问题的核心是subseq允许 <=, <, >=, >，但seqFrom只允许 <=, >=，然后subseq将seqFrom的输出“按摩”成 <, > 以删除最多一项，如果有多于一个相等的项则不起作用。我认为这是一个设计缺陷的原因是你可以创建一个seqFrom实现，该实现确实做了所需的事（生成适当的 <= 和 >= 子序列），但是subseq和rsubseq可能仍然不正确。

很久以前，似乎是这样想的，“嘿，seqFrom和subseq/rsubseq之间的这种不匹配是真的令人头痛。让我们让集合并排序在其seqFrom实现中处理所有的subseq/rsubseq逻辑，这样就不需要将两个可能的子序列按摩成四个可能的子序列。”

可以修复subseq和rsubseq以便删除必要数量的项，而不需要更改接口，但是如果集合并排序能直接执行所有逻辑，它可能比在subseq和rsubseq级别进行修复更加高效。

我看到了你关于Sorted2接口的观点。

Answer 13

评论者为：alexmiller

我认为这是一个有用的重新声明问题。我认为用drop逻辑来“修复”subseq仅仅是掩盖这个分歧，而更有效率且更有帮助的是允许集合并排序直接执行用户所需的事情。

Answer 14

评论者为：alexmiller

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

Answer 15

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