请在 2024 年 Clojure 调查问卷! 中分享你的想法。

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

0
Collections

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 中测试

补丁:clj-428-code-v5.patch

15 个答案

0

评论由:importer

已从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月编写,并附在他发送到说明中提供的dev线程的邮件中。他在该线程中描述了所采取的方法,此处进行复制


同时,为了启动关于如何修改subseq的讨论,我附上了一个提议的补丁。这个补丁通过修改Sorted接口的seqFrom方法来增加一个“inclusive”参数(即,<= 和 >= 是包含的,< 和 > 不包含)。

在这个补丁中,我没有解决我之前提出的一个问题,即subseq这个名字是否意味着它应该返回一个序列而不是一个列表(换句话说,是nil而不是())。如果需要seq的行为,需要在调用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.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中提到的错误修复,但移除了一些补丁中的不必要更改。关于-v1.txt的注释 continue to apply for the approach。

0

评论者:jafingerhut

补丁文件 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 中导致破坏性更改,因此我认为仅基于这个原因,那个特定的补丁就不应该采纳。

但是最好关注大局。与其推促 subseq 和其含义,不如考虑一些抽象接口,它能够捕捉 Sorted 中不存在的有趣功能。我认为对于这一点所付出的任何思考都是值得的。尤其是,如果有 2 个或 3 个现有集合可能从中受益的想法,那就更好了。如果我们找不到 2 个或 3 个,我认为我会将它放入待办事项列表,直到有一个有说服力的案例。特别是,这似乎与 SortedSet -> NavigableSet 在 Java 中的对应关系有关。

0

评论者:marco.m

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

0
by

评论者:markengelberg

我认为一种语言的重要衡量标准是它用于自身数据结构的内部抽象的扩展程度。因此,我长期以来一直认为这是一个值得解决的问题。子seq和rsubseq中嵌入的假设——排序集合只能有唯一的排序值,无疑是在初始代码中的疏忽,这不仅阻止了优先映射从子seq和rsubseq中挂钩,还阻止了Marczyk的几个巧妙的数据结构。我不认为Sorted之外还有什么有趣的,我们试图理解——问题在于,根据当前的定义,Sorted的seqFrom接口实现对于子seq和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进行这一改变。这看起来是一种简单的解决长久以来阻碍子seq和rsubseq与所有满足Sorted的seqFrom实现的data structures一起工作的长期问题的方法。

0
by

评论者:alexmiller

让我只是简单提一下,这是我第一次记得查看这个票据,因为它几乎在我参与Clojure核心之前。我知道这已经过去很长时间了,我正在试图真正地重新审视这个问题。但我可能会问你一些愚蠢的问题,因为我正在重新走过你走过的那条路。

我完全同意让良好的收集特性既能在Clojure核心内的实现中,也能在外部实现中发挥作用。

至于修改协议的可行性,我认为你可能误解了我的意图。我们当然可以修改/扩展协议,但我们只需要以一种增长(保留现有内容)而不是打破(通过更改现有的方法签名)的方式进行。我反对的是更改Sorted.seqFrom()的签名,这会破坏所有现有的实现——这根本不可行。但是,将Sorted扩展到Sorted2(或任何更有意义的名称)并在其中添加seqFrom的新arity是完全没问题的。子序列代码可以在集合是Sorted2的情况下做最好的事情,如果只是Sorted,就回退到其他方式。有各种方法来实现这一点,但希望你能理解这个意图——现有的东西继续按原样工作,如果有新的东西,就会利用它。

回溯一下,似乎seqFrom及其相关内容还没有足够强大,覆盖了可能存在于不同数据结构中的所有内容。我仍然认为NavigableSet有很多好的先验思考(不是说我有一个直接的答案,但它真的是同一个问题区域),并且广泛地查看在过去几年中添加的其他数据结构,看看我们能够实现什么是有益的。

实际上,子序列的整个实现在一定程度上比较低级,依赖于很多移动部件和假设。也许整个子序列操作实际上应该直接由集合来完成。

0

评论者:markengelberg

问题的核心是subseq允许 <=, <, >=, > 但是seqFrom只允许 <=, >= 然后subseq “按摩”seqFrom的输出为 <, >,如果有多于一个相同的物品则不起作用。我把这认为是设计缺陷的原因是,你可以创建一个seqFrom的实现,它恰好做到了实现所需的事情(生成适当的 <= 和 >= 子序列),而subseq和rsubseq可能仍然不会正常工作。

在过去,想法似乎是,“嘿,seqFrom和subseq/rsubseq之间的不匹配有点糟糕。让我们让集合在其seqFrom的实现中完成所有的subseq/rsubseq逻辑,这样就不需要将两种可能的subseq压缩成四种了。”

修复subseq和rsubseq以掉落所需数量的项目是可能的,这样就不需要更改接口,但如果集合能够直接完成所有逻辑,则可能允许集合以比在subseq和rsubseq级别修复更有效的方式创建 <, > 子序列。

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

0

评论者:alexmiller

我认为这是对问题的一个有用的陈述。我觉得用drop逻辑“修复”subseq只是在做更多掩饰这种脱节的表面文章,当直接允许集合执行用户需要的内容会更有用(并且更高效)。

0
by

评论者:alexmiller

例如,您可以有一个名为Subseqable的接口,如果subseq/rsubseq检测到它,它们只需将控制权传递给集合。

0
by
...