欢迎!有关如何使用本网站的更多信息,请参阅关于页面。
目前,Cycle、Range 和 Repeat 没有实现索引,这意味着 "nth" 的平均时间复杂度是 O(n)。
建议的更改是实现这些类的索引,使得 "nth" 成为 O(1) 操作。
评论者:alexmiller
这将是功能承诺的扩展,比这些函数过去所做的一切都要多。我们已经对这些函数投入了比实际想要的更多的承诺,所以我不确定我们还想再添加更多的承诺。无论如何,我们不会在 1.7 中这样做。
顺便说一下,你正在修补的 Range 代码当前并未被用于任何目的 - 现实现的当前 impl 使用 core.clj 中的分块 seq 定义。CLJ-1515 将(可能会)用全新实现在 Range 类中替换。无论如何,在 CLJ-1515 解决之前,在此处修补 Range 可能并无太大用处。
评论者:mikera
关于1.7的理解。尽管我个人认为这相当小,你可以将其塞进去。您决定。
然而,我仍然认为这种方法是有用的:nth 是一个非常常见的操作,我注意到您尚未在 CLJ-1515 中对其进行基准测试。不管使用什么新的 Range 实现方式,都会受益于索引实现。
目前没有任何一个函数保证返回Indexed类型的数据。如果我们添加这一承诺,并且人们开始依赖它,我们便无法以移除它的方式修改实现。因此,我不确定这是否是一个我们想做出的承诺。
我并不是提议我们承诺提供索引返回值,而是简单地说,这样的类应该将接口的实现细节(在合理的地方)作为接口的一部分。
这会导致像RT.nth这样的函数在快速路径上执行,因此我们对于最常见的索引查找情况获得O(1)的时间复杂度,而不是O(n)。
实际上,我的假设是“Indexed”接口的主要用途,即让具体的集合类型能够以效用的方式参与Clojure的索引访问函数。
评论者:gshayban
人们往往都会依赖实现细节,无论是有明确的承诺,还是没有承诺。如果Clojure添加了Indexed然后又移除它,人们代码要么会出错,要么会变慢。
实现行为(无论是明确的还是隐含的)在本质上被视为对未来约束(镣铐)的处理,因此这是值得仔细考虑的。