1

我需要根据一些数量规则从序列中提取一些元素。这是我想出的一个解决方案：

(defn take-while-not-enough
[p len xs]
(loop [ac 0
       r []
       s xs]
       (if (empty? s)
            r
            (let [new-ac (p ac (first s))]
                (if (>= new-ac len)
                    r
                    (recur new-ac (conj r (first s)) (rest s)))))))

(take-while-not-enough + 10 [2 5 7 8 2 1]) ; [2 5]

(take-while-not-enough #(+ %1 (%2 1)) 7 [[2 5] [7 8] [2 1]]) ; [[2 5]]

有没有更好的方法来实现同样的目标？

谢谢。

更新：

有人发布了该解决方案，但随后将其删除。它与我接受的答案相同，但更具可读性。谢谢你，匿名的好心人！

(defn take-while-not-enough [reducer-fn limit data] 
   (->> (reductions reducer-fn 0 data)      ; 1. the sequence of accumulated values
        (map vector data)                   ; 2. paired with the original sequence
        (take-while #(< (second %) limit))  ; 3. until a certain accumulated value
        (map first)))                       ; 4. then extract the original values
4

4 回答 4

2

我的第一个想法是将这个问题视为 reduce 的变体，因此将问题分为两个步骤：

  • 计算结果中的项目数
  • 从输入中取那么多

我还对参数名称采取了一些自由：

user> (defn take-while-not-enough [reducer-fn limit data] 
       (take (dec (count (take-while #(< % limit) (reductions reducer-fn 0 data)))) 
             data)) 
#'user/take-while-not-enough 

user> (take-while-not-enough #(+ %1 (%2 1)) 7 [[2 5] [7 8] [2 1]])    
([2 5])     

user> (take-while-not-enough + 10 [2 5 7 8 2 1]) 
(2 5)

这将返回一个序列，并且您的示例返回一个向量，如果这很重要，那么您可以添加一个调用vec

于 2013-04-23T20:41:08.517 回答
1

Something that would traverse the input sequence only once:

(defn take-while-not-enough [r v data]
  (->> (rest (reductions (fn [s i] [(r (s 0) i) i]) [0 []] data))
       (take-while (comp #(< % v) first))
       (map second)))
于 2013-04-24T04:50:00.333 回答
0

好吧，如果您想使用 flatland/useful，这是一种不错的使用方式glue：

(defn take-while-not-enough [p len xs]                                                              
  (first (glue conj []                                                                              
               (constantly true)                                                                    
               #(>= (reduce p 0 %) len)                                                             
               xs)))

但是每次它决定是否进一步增加块时，它都会为整个“已处理”块重建累加器，所以它是 O(n^2)，这对于更大的输入是不可接受的。

对你的实现最明显的改进是让它变得惰性而不是尾递归：

(defn take-while-not-enough [p len xs]                                                                                    
  ((fn step [acc coll]                                                                          
     (lazy-seq                                                                                  
       (when-let [xs (seq coll)]                                                                  
         (let [x (first xs)                                                                     
               acc (p acc x)]                                                                   
           (when-not (>= acc len)                                                               
             (cons x (step acc xs)))))))                                                        
   0 xs))
于 2013-04-24T04:45:17.433 回答
0

有时lazy-seq是直截了当且不言自明的。

(defn take-while-not-enough
  ([f limit coll] (take-while-not-enough f limit (f) coll))
  ([f limit acc coll]
   (lazy-seq
     (when-let [s (seq coll)]
       (let [fst  (first s)
             nacc (f acc fst)]
         (when (< nxt-sd limit)
           (cons fst (take-while-not-enough f limit nacc (rest s)))))))))

注意：f预计遵循reduce的规则。

于 2013-04-24T05:59:05.967 回答