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

欢迎!请查看 关于 页面,了解更多此站点的信息。

0
集合

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 行为到其他类型集合变得不可能。为了赋予库设计者 hook 到 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 中

15 个答案

0
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而不是())。如果需要序列的行为,则必须在take-while的调用周围包装seq的调用。但到目前为止,我只是让行为与当前的行为相匹配。

虽然我认为这是解决subseq可扩展性问题的最干净的方式,但修改seqFrom将破坏当前覆盖该方法的所有人。我没有在clojure.contrib中发现这样的类,所以我不认为这是一个问题,但如果这是一个关心的问题,我的另一个想法是在subseq内完全解决问题的方法,即通过将调用next变为调用drop-while来改变调用方式。我已经编好代码来确认它的工作,如果需要的话可以提供这个备选补丁。

我还可以提供使用drop-while在clojure.core/subseq和rsubseq中的补丁,如果这种方案被首选于本补丁的方法。

0

评论者:jafingerhut

2013年4月28日日期的补丁文件 clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v2.txtclj-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.txtclj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v1.txt 相同,仍然包括之前提到的用于-v2的错误修复,但移除了补丁中的某些不必要的更改。关于-v1.txt的方法的评论仍然适用。

0

评论者:jafingerhut

Patch clj-428-v4.diff 与之前评论中描述的 clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v3.txt 相同,但更新了一些 diff 内容行,以便它能干净地应用于今天的最新 Clojure master 版本。

0

评论者:jafingerhut

文件 clj-428-code-v5.patch 和 clj-428-tests-v5.patch 与之前版本 -v4 相同,但它们能干净地应用于最新的 Clojure master 版本。代码和测试分别放在不同的文件中,因为它们的作者不同,如果它们保持分离,将来更新这样的补丁将会更加容易。

0

评论者:marco.m

你好,有什么新消息吗?

0

评论者:alexmiller

根据实现,这个更改将在 Sorted 中引入不兼容的变动,所以我认为仅基于这一点,那个特定的补丁不太可能采用。

但是,最好还是从高层考虑。与其推动子序列及其意义上的变动,不如考虑一些抽象接口,这个接口能够捕获 Sorted 中没有的有趣的东西。我认为投入任何对此的思考都是值得的。特别是,如果能有一两个现有的集合可能会从这方面受益的想法就更好了。如果我们找不到两三个,那么我认为我会将它放入待办事项列表中,直到有说服力的案例出现。特别地,这似乎在 SortedSet -> NavigableSet in Java 之间有一些对应关系,也许需要类似的东西。

0

评论者:marco.m

感谢 Alex,真的非常感激你的回复以及你的深思熟虑 :-)

0

评论者:markengelberg

我认为语言的一个重要指标是其内部抽象的程度,这些抽象用于其自己的数据结构,它们对扩展的开放程度。因此,我一直认为这是一个值得解决的问题。subseq 和 rsubseq 中内置的假设,即有序集合只能具有唯一的有序值,无疑是初始代码中的一个疏忽,这不仅阻止了 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 核心的倾向,因为这会带来明显的利益而没有缺点。(或者,如果有性能影响,想方设法调整它,以消除性能惩罚,这应该很容易做到)。对 subseq 和 rsubseq 所需的改变很简单:它们现在通过调用 rest 丢弃第一个项目,将 <= 子序列更改为 < 子序列,我只是将它们更改为调用 drop-while 丢弃序列前面所有相等的项,因为可能不止一个。当这个问题首次提出时,核心团队成员表示他们更愿意在协议级别解决这个问题,但如果这样做不再可行,我希望看到 subseq 和 rsubseq 的这个更改被考虑。这似乎是一个修复这个长期存在的问题的好方法,该问题阻止 subseq 和 rsubseq 适用于所有实现 Sorted 的 seqFrom 实现的数据结构。

0

评论者:alexmiller

我只是想说,这是我有记忆以来第一次查看这个工单,因为它几乎是在我参与 Clojure 核心的活动之前。我知道已经有很多年了,我正在真诚地思考这个问题。但我在重新走过你走过的路时可能会问一些愚蠢的问题。

我在确保良好的集合特性能被 Clojure 内部和外部 impls 使用这一点上绝对是一致的。

至于更改协议的可行性,我认为可能你误解了我的意图。我们当然可以更改或扩展协议,但我们只需要以扩展而不是破坏的方式来做(通过更改现有方法签名),即在保持现有内容不变的情况下进行扩展。我反对更改Sorted.seqFrom()的签名,因为它会破坏所有现有的实现——这根本无法开辟新局面。但将Sorted扩展到Sorted2(或更具意义的名称)并添加新的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

我认为这是对问题的一个有助的重述。我觉得用删除逻辑“修复”subseq只是在这个隔阂上再做更多的掩饰,而当允许集合直接执行用户所需操作时,会更有帮助且更高效。

0
by

评论者:alexmiller

例如,您可以有一个 Subseqable 接口,如果 subseq/rsubseq 检测到它,它们就直接传递控制到集合中。

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