2024 Clojure状态调查!中分享您的想法。

欢迎!请参阅关于页面,了解有关此工作的更多信息。

0
集合

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的行为扩展到其他类型的集合。为了赋予库设计者将子序列钩入的能力,需要删除这个假设。

方法

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

  2. 更好的方法是将subseq的更多逻辑委托给seqFrom(通过在方法调用中添加一个额外的标志来指定您想要大于、大于等于还是严格大于)。这将允许获得最佳的效率,并提供了最大的未来扩展可能性。
    注意:subseq在有些情况下返回()而不是nil。如果这个想法彻底失败,我们可能仍然希望修复这个问题。

修补程序clj-428-code-v5.patch实现了上面的第二种方法。它保留了返回()而不是nil的当前行为。

修补程序:clj-428-code-v5.patch在clj-428-tests-v5.patch中测试

修补程序:clj-428-code-v5.patch在clj-428-tests-v5.patch中测试

15 答案

0

评论由:导入器创建

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

0

评论人: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,如果这种方法更受此补丁中的方法的青睐。

0

评论人: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的测试,并纠正了该补丁中的一个错误。该补丁采用的方法与上述补丁中描述的方法相同。

0

评论人: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提到的bug修复,但移除了补丁中的一些不必要更改。对-v1.txt中该补丁方法的评注依然适用。

0
by

评论人:jafingerhut

补丁文件clj-428-v4.diff与早期评论中描述的clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v3.txt相同,只是它更新了一些diff上下文行,以便今天对最新的Clojure master进行干净的应用。

0
by

评论人:jafingerhut

文件clj-428-code-v5.patch和clj-428-tests-v5.patch与前一个-v4附件相同,除了它们可以干净地应用于最新的Clojure master。由于代码和测试由不同的作者编写,因此将它们保存在单独的文件中将更容易在将来更新这些补丁。

0
by

评论者:marco.m

你好,有什么新闻吗?

0
by

评论者:alexmiller

按照实现方式,这个更改将在Sorted中引起不兼容变更,因此我认为仅基于这一点,该补丁就不适用于Sorted。

但最好关注高层次的问题。与其推动subseq和它的意义,不如考虑一些抽象接口,该接口能够捕捉 Sorted 之外的一些有趣的功能。我认为对这个问题的任何一个想法都值得思考。特别是,了解2到3种可能从这种变化中受益的现有集合将是个好主意。如果我们找不到2-3个这样的集合,我认为我会将其放入待办事项中,直到有一个有说服力的理由。特别是,这看起来与Java中的SortedSet -> NavigableSet有一些对应关系,可能需要类似的方法。

0
by

评论者:marco.m

谢谢Alex,非常感谢你的回复和你在上面的思考 :-)

0
by

评论者:markengelberg

我认为语言的一个重要指标是其内部抽象的程度,即用于其自数据结构的抽象对扩展的开放程度。因此,我长期以来认为这是一个值得解决的问题。在 subseq 和 rsubseq 中内嵌的假设——排序集合只能有唯一的排序值肯定是在初始代码中犯的一个疏忽,这个疏忽不仅阻止了 priority-map 集成到 subseq 和 rsubseq 中,还阻止了 Marczyk 的几个巧妙的数据结构的集成。我认为 Sorted 之外并没有什么有趣的内容需要我们试图理解 —— 问题在于,按目前定义的 subseq 和 rsubseq,实现 Sorted 的 seqFrom 接口目前并不足以提供它们指定的行为。你可以将其视为 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 到调用 drop-while 来删除序列开头的所有相等元素,因为可能不止一个。当这个问题首次提出时,核心团队成员表示他们更希望看到在协议级别修复,但如果这不切实际,我希望可以考虑对 subseq 和 rsubseq 的这个更改。这似乎是修复这个长期问题的一个简单方法,该问题阻止了 subseq 和 rsubseq 适用于所有履行 Sorted's seqFrom 实现的数据结构。

0

评论者:alexmiller

我只想说一下,这还是我第一次记住查看这个票证,因为它基本上在大约我参与 Clojure 核心之前就已经存在了。我知道已经过去好几年,我正在实际上诚实地点评这一问题。但我在重新走过您已经走过的路上时可能会问一些愚蠢的问题。

我确实认同让好的集合特性能够被 Clojure 核心和外部都用的 impls 利用。

关于改变协议的可行性,我认为你可能误解了我的意图。我们当然可以更改或扩展协议,但我们只需要以一种扩展而不是打破的方式(通过更改现有方法签名)来这样做。我的反对意见是更改 Sorted.seqFrom() 的签名,这会破坏所有现有的实现 - 这根本是不可行的。但是,将 Sorted 扩展到 Sorted2(或者 whatever 更有意义的名字)并添加新的 seqFromари完全没问题。子序列代码可以在集合是 Sorted2 的情况下执行最佳操作,如果只是 Sorted,则回退到其他操作。有各种方法来实现这一点,但希望你能理解意图 - 现有的东西无需更改即可继续工作,如果可用,则可以利用新事物。

回过头来说,seqFrom 和类似的功能可能不足以涵盖不同数据结构可能需要的所有内容。我继续认为 NavigableSet 有很多很好的先入为主的思考(我不是说它是一个直接的答案,但它确实是同一个问题区域),并且广泛地看看在过去的几年中添加的其他数据结构可能会有很大的好处,看看我们可以实现什么。

实际上,子序列的全部实现相当恶心,依赖于许多移动部件和假设。也许整个子序列操作实际上应该直接由集合完成。

0

评论者:markengelberg

问题的关键是 subseq 允许 <=,<,>=,>,但 seqFrom 只允许 <=,>=,然后 subseq 将 seqFrom 的输出“按摩”成 <,>,在丢弃最多一个项目的方式下。我之所以认为这是一个设计缺陷,是因为你可以创建一个 seqFrom 的实现,该实现恰好符合实际需求(生成适当的 <= 和 >= 子序列),而 subseq 和 rsubseq 可能仍然不会正确运行。

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

可以修改 subseq 和 rsubseq 以丢弃必要的项目,这样就不需要更改接口,但如果集合能够直接完成所有逻辑,那么集合可能比在 subseq 和 rsubseq 层级进行修复更能有效地创建 <,> 子序列。

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

0

评论者:alexmiller

我认为这是对问题的有益重述。我认为,用 drop 逻辑“修复”subseq 只是在试图掩盖这一不匹配,而更有帮助(更高效)的是允许集合直接完成用户需要的操作。

0

评论者:alexmiller

例如,您可以有一个Supportable接口,如果subseq/rsubseq能检测到它,它们就只是传递给集合的控制。

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