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的行为扩展到其他类型的集合。为了给库设计者提供将subseq hook的功能,需要去除这个假设。

方法

  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

修改后的“clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v1.txt”,日期为2013年4月28日,由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.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中的方法的评论仍适用。

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 中没有的有趣抽象接口。对任何思考在内的想法都是有价值的。特别是,确定两个或三个可能从这中获益的现有集合的想法会很好。如果我们找不到两个或三个,我认为我会将它放入待办事项中,直到有一个有说服力的案例。特别是,这似乎与 SortedSet -> NavigableSet 在 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的核心,因为这将带来明显的利益而没有风险。(或者,如果与Clojure现有的排序数据结构相比有性能影响,找出如何调整以消除性能损失,这应该很容易实现)。对subseq和rsubseq所需的改动很简单:他们将当前小于等于子序列变为小于子序列的方式通过调用rest来丢弃第一个项,我只是将它们改为调用drop-while来丢弃序列前端的全部相等项,因为可能会有多个。当首次提出此问题时,核心团队成员表示他们更希望看到在协议层面进行修复,但如果这不再可行,我希望看到对subseq和rsubseq的这种改动得以考虑。这看起来是一个解决长久以来阻碍subseq和rsubseq与所有满足Sorted的seqFrom实现的数据结构工作的简单方法。

0

评论者:alexmiller

我只是想说,这是我第一次记得查看这个工单,因为它很大程度上早于我在Clojure核心中的参与。我知道已经过去了多年,我正在尽力真诚地思考这个问题。但我不太可能在你已经走过的路径上提出一些愚蠢的问题。

我确实赞同让良好的集合特性能够被Clojure核心内外部的实现所使用。

关于更改协议的可行性,我认为可能你在那里误解了我的意图。我们当然可以更改或扩展协议,但我们只需要以成长(保留现有内容)的方式来进行,而不是打破(通过更改现有的方法签名)。我反对的是更改 Sorted.seqFrom() 的签名,因为这会破坏所有现有的实现——这根本不可行。但将 Sorted 扩展到 Sorted2(或任何更有意义的名称)并添加新的 seqFrom 实例数是完全可行的。子序列代码可以对 coll 是 Sorted2 的情况做最好的事,如果只是 Sorted,则回落到其他操作。有各种方法来实现这一点,但希望能理解意图——现有内容不改变继续工作,如果可用,则利用新内容。

回顾一下,seqFrom 和相关功能似乎不足以涵盖可能会跨越不同数据结构的需求。我仍然认为 NavigableSet 有许多很好的前期思考(不是直接说它是答案,但确实是同一个问题领域),并且更广泛地研究在间隔几年间添加的其他数据结构将非常有利,看看我们能够实现什么。

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

0

评论者:markengelberg

问题的核心是子序列允许 <=, <, >=, >,但 seqFrom 只允许 <=, >=,然后子序列以丢弃最多一个项目的方式“按摩”seqFrom 的输出变为 <, >,如果有多于一个相等的项则不起作用。我将其视为设计缺陷的原因是,即使创建了一个精确实现 seqFrom 的实现(生成适当的 <= 和 >= 子序列),子序列和 rsubseq 也可能不正确。

早在很久以前,想法似乎是,“嘿,seqFrom 与子序列/rsubseq 之间的不匹配相当糟糕。让我们让集合在其 seqFrom 实现中执行所有子序列/rsubseq 逻辑,这样就不需要将两个可能的子序列按摩为四个了。”

可以修复子序列和 rsubseq 以丢弃所需的项目数量,以便不需要更改接口,但如果集合可以直接执行所有逻辑,那么集合可能比在子序列和 rsubseq 级别进行修复更有效地创建 <, > 子序列。

我理解您的 Sorted2 接口观点。

0

评论者:alexmiller

我觉得这是对问题的一个很有帮助的重述。我觉得,用丢弃逻辑“修复”子序列只是在掩盖这一失调,而当允许集合直接执行用户所需的内容时,将更有帮助(并且更高效)。

0

评论者:alexmiller

例如,您可以有一个支持子序列的接口,如果 subseq/rsubseq 检测到它,它将直接将控制权传递给集合。

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