在Clojure的`first`功能的性能

问题描述：

我看到了下面的例子中丰富的视频序列 http://blip.tv/file/734409 约33-36分钟到其中：在Clojure的`first`功能的性能

(first "abcd") => \a

现在，他说，这扩展到（排序）：

(first "abcd") => (first (seq "abcd")) => (first '(\a \b \c \d))

因此，它看起来像一个O(N)操作，因为字符串的完整副本正在制作。首先，如果String是不可变的，那么它为什么被复制？（编辑：根据答案，它可能不是;只是在打印时以这种方式看）。其次，假设first在Java中可变的其他东西上操作，比如说一个整数链表。 first是否应该以懒惰的方式行动（例如，首先创建一个持久序列）？马上评估并保存它是否有意义？这可能会破坏很好的抽象，但我认为完成这项工作很快。当您拨打(seq "abcd")时，您不知道如何使用它。当您拨打seq上的first时，您知道该怎么做。但是，当您拨打 "abcd"时，我认为执行一个快速“抓取并保存”的方法比抓取一个序列更好，然后致电first。

我错过了什么吗？ Rich Hickey是否跳过了一些步骤？

让我知道如果我有问题。谢谢！

答

其他答案是正确的，但我会利用这个机会指出Clojure的不变性哲学的一个有趣效果。

因此，它看起来像一个O（N）操作，因为字符串的完整副本正在生成。

字符串和Clojure中的其他数据结构一样是不可变的。（它们是一种特殊情况，在JVM中实现而不是在Clojure中实现，但对于这一点非常重要。）

不可变对象的副本是免费。没错，免费。因为你根本不需要复制。内存中的相同分配对象可以简单地批量重用，因为它保证始终与“复制”时相同。

所以像seq这样的功能从来没有必须实际上复制任何东西。它只是在任何传递的内容上直接操作，并且返回一个（可能是懒惰的）序列，为您称为seq的任何事物提供抽象接口。

所以，seq总是O（1）。

谢谢，关于使用可变成Java序列的可变Java对象的任何进一步输入？ – 2010-10-04 16:41:44

IIRC调用seq返回一个由Java迭代器支持的惰性Clojure序列。所以随着懒惰序列的实现，它需要遵循与迭代器有关的所有规则（只要对基础对象进行变异）一旦实现，它就是一个不可变的Clojure序列。 – levand 2010-10-04 18:06:14

@Hamish - 如果你想把一个可变的Java对象变成一个序列，那么你需要做一个O（n）成本的防御副本，否则就有可能改变底层数据的风险（这会违反seq的正常期望行为并可能导致微妙的错误）。前一种方法（复制）可能是可取的，后者是非常危险的，除非你绝对确定在错误的时刻什么都不会改变。 – mikera 2011-09-29 08:15:18

答

这并不表示正在创建字符串的完整副本。（但是，这是一个很好的问题。）

在源为clojure.lang.RT，你会发现，运行时使用的CharSequence创建序列：

static ISeq seqFrom(Object coll){ 
    if(coll instanceof Seqable) 
     return ((Seqable) coll).seq(); 
    else if(coll == null) 
     return null; 
    else if(coll instanceof Iterable) 
     return IteratorSeq.create(((Iterable) coll).iterator()); 
    else if(coll.getClass().isArray()) 
     return ArraySeq.createFromObject(coll); 
    else if(coll instanceof CharSequence) 
     return StringSeq.create((CharSequence) coll); 
      . 
      . 
      .

因此，其实，这是一个Java问题，而不是一个clojure问题。我没有检查，但我相当肯定CharSequence做的是“正确的事情”。

感谢您的回答，Rob。假设'CharSequence'做了正确的事情，因为它可以，因为'String'是不可变的。现在，如果我有一个由Java代码定义的999个整数的可变链表，并且我想抓取第一个项目。我可以比先复制999件物品做得更好，还是这样做是为了采取“非折扣”方式而必须支付的罚款？例如。我应该创建一个包含那些不可变的类的类？在我看来，在Clojure中需要使用不完美的Java库时，会出现这种情况。我知道第一个元素可能很大。 – 2010-10-03 17:48:34

（续），所以调用'first'可能需要一段时间 - 比如说我们首先调用一个可变链表的可变链表。我明白为什么我们想通过复制的方式将第一个内部可变链表变成一个持久序列，但为什么对它的“休息”做同样的事情，对于在这种情况下永远不会看到的事情？ – 2010-10-03 17:51:21

不需要将999个项目复制到seq中，因为seq只是根据需要使用基础数据结构，并且出于性能和不可变性的原因，缓存它找到的内容。如果您在某些集合（例如，链表）上调用“first”，那么seq需要查看的唯一元素是第一个。底层集合中尚未观察到的元素可能会在没有通知的情况下发生变化。只有当seq实际读取一个元素时，该元素才会在seq中“持久”。 – 2010-10-03 18:20:52

答

您可以看看seq，就好像它根据字符串创建了一个惰性序列。

它实际上并没有创建一个惰性序列，它实际上会短路到CharSequence的java实现，但这是一个实现细节。

从一个复杂点，first是O(1)上一个seq，您可以创建在常数时间内seq从什么是迭代。

在Clojure的`first`功能的性能

相关推荐