Clojure：O(1) 函数来检查序列是否恰好有 1 个元素

Question

在 Clojure 中是否有一种快速检查序列是否恰好有 1 个元素的方法？请注意，一个序列可能包含 nils.

如果我读 source 正确，调用序列 count 需要 O(n) 时间。

替代解决方案：

(and
  (not (empty? a-seq))
  (empty? (rest a-seq)))

Docs 说在集合 coll 上调用 empty? 与调用 (not (seq coll)) 相同，但他们没有指定其效率或调用时会发生什么empty? 在一个序列上。我试图搜索 github 存储库以了解 empty? 是如何实现的，但它忽略了搜索中的问号并且在 "empty" 上有大量点击。我想 empty? 和 rest 是 O(1)，但话又说回来，count 不是...

Answer 1

因为

user=> (empty? (cycle [1]))
false

（函数终止的事实），我假设 empty? 在恒定时间内求值，即 (seq coll) 在恒定时间内初始化一个序列。

user=> (source empty?)
(defn empty?
  "Returns true if coll has no items - same as (not (seq coll)).
  Please use the idiom (seq x) rather than (not (empty? x))"
  {:added "1.0"
   :static true}
  [coll] (not (seq coll)))
nil

你的代码做得相当好。也许我会说：

user=> (defn single-elem? [s]
  #_=>   (and
  #_=>     (seq s)
  #_=>     (empty? (rest s))))
#'user/single-elem?

user=> (single-elem? [1])
true
user=> (single-elem? [1 2])
false
user=> (single-elem? [])
nil
user=> (single-elem? {:foo :bar})
true
user=> (single-elem? {:foo :bar :fez 42})
false

Answer 2

1.9 中添加了以下功能（目前仍处于 alpha 阶段）：

(defn bounded-count
  "If coll is counted? returns its count, else will count at most the first n
  elements of coll using its seq"
  {:added "1.9"}
  [n coll]
  (if (counted? coll)
    (count coll)
    (loop [i 0 s (seq coll)]
      (if (and s (< i n))
        (recur (inc i) (next s))
        i))))

所以我想 (bounded-count 2 coll) 应该可以为您提供所需的恒定时间计数。

Answer 3

当序列可以是惰性的时，你就不能真正谈论 "constant time"，因为在输入序列的构造中可能已经推迟了任何数量的工作。例如，考虑这个序列：

(filter even? (filter odd? (range)))

在此序列上调用 seq 永远不会 return 任何类型的结果，除非您等待的时间足够长以超过 Long/MAX_VALUE。

但是，一般来说，函数只做它们需要做的最少工作量。因此 seq 所做的工作足以确定集合的第一个元素是什么（如果有），而 next 所做的工作足以确定第一个和第二个元素是什么（如果有）。

Answer 4

一些注意事项：

Docs say that calling empty? on a collection is the same as calling (not (seq coll)), but they don't specify its efficiency or what happens when you call empty? on a sequence.

empty? 适用于序列，无论是否基于集合。定义作为seq的补充：

(defn empty? [coll]
  (not (seq coll)))

我会将您的函数重写为

(defn one-element? [coll]
  (and (seq coll)
       (empty? (rest coll))))

或

(defn one-element [coll]
  (and (seq coll)
       (not (next coll))))

它们的速度与 seq 和 rest/next 的速度相同。

Clojure：O(1) 函数来检查序列是否恰好有 1 个元素

Clojure: O(1) function to check if sequence has exactly 1 element

performance

functional-programming

predicate

clojure