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

欢迎!请参阅关于页面,了解更多关于如何使用本站的信息。

0
集合

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

摘自Mark Engelberg在2010年7月14日那个讨论线程中的信息

只有在核心补丁的情况下,才能真正实现priority maps上的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中的测试在clj-428-tests-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月编写,并与他发送到描述中链接的开发线程的消息一起附上。他在该线程中描述了所采取的方法,此处复制


同时,为了就如何修改subseq进行讨论,我附上了一个建议的补丁。这个补丁通过修改Sorted接口的seqFrom方法来接受一个额外的“inclusive”参数(即,<=和>=是包含的,而<和>不包含)。

在这个补丁中,我没有解决我 previously 提出的一个问题,即subseq的名字是否意味着它应该返回一个seq而不是一个序列(换句话说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相同,仍然 fixes 提至于-v2的错误,但删除了一些补丁中的不必要更改。关于-v1.txt中关于该方法的评论依然适用。

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个这样的集合,我认为我会将它放入待办事项清单,直到有说服力的论据出现。特别是,这似乎与Java中的SortedSet -> NavigableSet之间存在某种对应关系,可能需要类似的解决方案。

0

评论者:marco.m

感谢Alex,真的很感激你的回复和你在上面所付出的思考:)

0

评论者:markengelberg

我认为,衡量一种语言的重要指标之一是其内部抽象的可扩展程度,这些抽象用于其自身的数据结构。因此,我坚信这是一个值得解决的问题。在subseq和rsubseq中嵌入的假设——有序集合只能有唯一的有序值——无疑是初始代码中的疏忽,这个疏忽不仅阻止了priority-map与之连接,还阻止了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实现的数据结构一起工作。

0
通过

评论者:alexmiller

我只是想提一下,这是我第一次记得查看这个票据,因为它在很大程度上早于我参与Clojure核心的时候。我知道已经过了很多年,我正在试图真正地深入思考这个问题。但我在重新走过你们的路径时,可能还会提一些愚蠢的问题。

我当然同意让好的集合特性能够在Clojure核心内外得到使用。

关于更改协议的可行性,我认为可能你误解了我的意图。我们当然可以更改或扩展协议,但我们只需以一种累积扩展(保留现有内容)的方式去做,而不是破坏(通过更改现有方法签名)的方式。我对更改Sorted.seqFrom()签名的反对意见是,这会破坏所有现有的实现——这完全是不可行的。但是,将Sorted扩展到Sorted2(或任何更有意义的名称)并添加一个新的seqFrom抽象是完全可以接受的。这样,子序列代码就可以如果集合是Sorted2那么做到最好,如果只是Sorted则回退到其他方式。有各种实现方法,但希望你能理解意图——现有内容继续按原样工作,新内容如果可用则会得到利用。

回顾一下,seqFrom及其相关功能似乎不足以涵盖不同数据结构中可能需要的所有功能。我继续认为NavigableSet有很多好的前期思考(并不是说它是直接的答案,但确实是相同的问题领域),并且扩展到其他在间隔年份中添加的其他数据结构,看看我们可以实现什么是有益的。

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

0

评论者:markengelberg

问题的核心是subseq允许 <=、<、>=、>,但seqFrom只允许 <=、>=,然后subseq将seqFrom的输出“按摩”成<、>,在丢弃最多一个元素的方式,如果存在多个相等的元素则不起作用。我认为这是一个设计缺陷的原因是,你可以创建一个seqFrom的实现,该实现正好满足实现要求(生成适当的 <= 和 >= 子序列),但subseq和rsubseq可能仍然不正确。

早在很久以前,想法似乎是,“嘿,seqFrom与subseq/rsubseq之间的不匹配有点糟糕。让我们让collections在seqFrom的实现中进行所有subseq/rsubseq逻辑,这样就不需要按摩两个可能的subseq成为四个可能的。”

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

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

0

评论者:alexmiller

我认为这是对问题的有益重述。我感觉“修复”subseq的drop逻辑只是对这个隔阂的更多掩盖,而当允许collections直接完成用户需要的事情将会更有帮助(并且更有效率)。

0

评论者:alexmiller

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

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