Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

Commit6aefc73

Browse files
CLJS-3393: Efficient drop, partition for persistent/algo colls (#196)
Co-authored-by: Mike Fikes <mike@fikesfarm.com>
1 parent2199516 commit6aefc73

File tree

5 files changed

+384
-40
lines changed

5 files changed

+384
-40
lines changed

‎src/main/cljs/cljs/core.cljs

Lines changed: 161 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -886,6 +886,14 @@
886886
(-iterator [coll]
887887
"Returns an iterator for coll."))
888888

889+
(defprotocolIDrop
890+
"Protocol for persistent or algorithmically defined collections to provide a
891+
means of dropping N items that is more efficient than sequential walking."
892+
(^clj-or-nil -drop [coll n]
893+
"Returns a collection that is ISequential, ISeq, and IReduce, or nil if past
894+
the end. The number of items to drop n must be > 0. It is also useful if the
895+
returned coll implements IDrop for subsequent use in a partition-like scenario."))
896+
889897
;; Printing support
890898

891899
(deftypeStringBufferWriter [sb]
@@ -1631,6 +1639,14 @@ reduces them without incurring seq initialization"
16311639
(IndexedSeq. arr (inc i)nil)
16321640
nil))
16331641

1642+
IDrop
1643+
(-drop [coll n]
1644+
(if (pos? n)
1645+
(if (< (+ i n) (alength arr))
1646+
(IndexedSeq. arr (+ i n)nil)
1647+
nil)
1648+
coll))
1649+
16341650
ICounted
16351651
(-count [_]
16361652
(max0 (- (alength arr) i)))
@@ -1949,10 +1965,14 @@ reduces them without incurring seq initialization"
19491965
(defnnthrest
19501966
"Returns the nth rest of coll, coll when n is 0."
19511967
[coll n]
1952-
(loop [n n xs coll]
1953-
(if-let [xs (and (pos? n) (seq xs))]
1954-
(recur (dec n) (rest xs))
1955-
xs)))
1968+
(if (implements? IDrop coll)
1969+
(if (pos? n)
1970+
(or (-drop coll (Math/ceil n)) ())
1971+
coll)
1972+
(loop [n n xs coll]
1973+
(if-let [xs (and (pos? n) (seq xs))]
1974+
(recur (dec n) (rest xs))
1975+
xs))))
19561976

19571977
(defnget
19581978
"Returns the value mapped to key, not-found or nil if key not present
@@ -2997,10 +3017,14 @@ reduces them without incurring seq initialization"
29973017
(defnnthnext
29983018
"Returns the nth next of coll, (seq coll) when n is 0."
29993019
[coll n]
3000-
(loop [n n xs (seq coll)]
3001-
(if (and xs (pos? n))
3002-
(recur (dec n) (next xs))
3003-
xs)))
3020+
(if (implements? IDrop coll)
3021+
(if (pos? n)
3022+
(-drop coll (Math/ceil n))
3023+
(seq coll))
3024+
(loop [n n xs (seq coll)]
3025+
(if (and xs (pos? n))
3026+
(recur (dec n) (next xs))
3027+
xs))))
30043028

30053029
;;;;;;;;;;;;;;;;;;;;;;;;;; basics ;;;;;;;;;;;;;;;;;;
30063030

@@ -4828,7 +4852,7 @@ reduces them without incurring seq initialization"
48284852
(cons (first s) (take (dec n) (rest s))))))))
48294853

48304854
(defndrop
4831-
"Returns alazy sequence of all but the first n items in coll.
4855+
"Returns alaziness-preserving sequence of all but the first n items in coll.
48324856
Returns a stateful transducer when no collection is provided."
48334857
([n]
48344858
{:pre [(number? n)]}
@@ -4845,12 +4869,18 @@ reduces them without incurring seq initialization"
48454869
(rf result input))))))))
48464870
([n coll]
48474871
{:pre [(number? n)]}
4848-
(let [step (fn [n coll]
4849-
(let [s (seq coll)]
4850-
(if (and (pos? n) s)
4851-
(recur (dec n) (rest s))
4852-
s)))]
4853-
(lazy-seq (step n coll)))))
4872+
(if (implements? IDrop coll)
4873+
(or
4874+
(if (pos? n)
4875+
(-drop coll (Math/ceil n))
4876+
(seq coll))
4877+
())
4878+
(let [step (fn [n coll]
4879+
(let [s (seq coll)]
4880+
(if (and (pos? n) s)
4881+
(recur (dec n) (rest s))
4882+
s)))]
4883+
(lazy-seq (step n coll))))))
48544884

48554885
(defndrop-last
48564886
"Return a lazy sequence of all but the last n (default 1) items in coll"
@@ -5019,6 +5049,14 @@ reduces them without incurring seq initialization"
50195049
ICollection
50205050
(-conj [coll o] (cons o coll))
50215051

5052+
IDrop
5053+
(-drop [coll n]
5054+
(if (== count-1)
5055+
coll
5056+
(let [dropped-count (- count n)]
5057+
(when (pos? dropped-count)
5058+
(Repeat.nil dropped-count valnilnil)))))
5059+
50225060
IEmptyableCollection
50235061
(-empty [coll] (.-EMPTY List))
50245062

@@ -5645,6 +5683,13 @@ reduces them without incurring seq initialization"
56455683
(<= cnt32) (IndexedSeq. tail0nil)
56465684
:else (chunked-seq coll (first-array-for-longvec coll)00)))
56475685

5686+
IDrop
5687+
(-drop [coll n]
5688+
(if (< n cnt)
5689+
(let [offset (js-mod n32)]
5690+
(chunked-seq coll (unchecked-array-for coll n) (- n offset) offset))
5691+
nil))
5692+
56485693
ICounted
56495694
(-count [coll] cnt)
56505695

@@ -5849,6 +5894,17 @@ reduces them without incurring seq initialization"
58495894
s))
58505895
(-chunked-next coll)))
58515896

5897+
IDrop
5898+
(-drop [coll n]
5899+
(let [o (+ off n)]
5900+
(if (< o (alength node))
5901+
(chunked-seq vec node i o)
5902+
(let [i (+ i o)]
5903+
(if (< i (-count vec))
5904+
(let [new-offset (js-mod i32)]
5905+
(chunked-seq vec (unchecked-array-for vec i) (- i new-offset) new-offset))
5906+
nil)))))
5907+
58525908
ICollection
58535909
(-conj [coll o]
58545910
(cons o coll))
@@ -6864,6 +6920,11 @@ reduces them without incurring seq initialization"
68646920
(when (< i (- (alength arr)2))
68656921
(PersistentArrayMapSeq. arr (+ i2)nil)))
68666922

6923+
IDrop
6924+
(-drop [coll n]
6925+
(when (< n (-count coll))
6926+
(PersistentArrayMapSeq. arr (+ i (*2 n))nil)))
6927+
68676928
IReduce
68686929
(-reduce [coll f] (seq-reduce f coll))
68696930
(-reduce [coll f start] (seq-reduce f start coll)))
@@ -6964,6 +7025,11 @@ reduces them without incurring seq initialization"
69647025
(-seq [coll]
69657026
(persistent-array-map-seq arr0nil))
69667027

7028+
IDrop
7029+
(-drop [coll n]
7030+
(when-some [s (-seq coll)]
7031+
(-drop s n)))
7032+
69677033
ICounted
69687034
(-count [coll] cnt)
69697035

@@ -9737,6 +9803,47 @@ reduces them without incurring seq initialization"
97379803
(when-let [s (seq coll)]
97389804
(cons (take n s) (partition-all n step (drop step s)))))))
97399805

9806+
(defnsplitv-at
9807+
"Returns a vector of [(into [] (take n) coll) (drop n coll)]"
9808+
[n coll]
9809+
[(into [] (take n) coll) (drop n coll)])
9810+
9811+
(defnpartitionv
9812+
"Returns a lazy sequence of vectors of n items each, at offsets step
9813+
apart. If step is not supplied, defaults to n, i.e. the partitions
9814+
do not overlap. If a pad collection is supplied, use its elements as
9815+
necessary to complete last partition upto n items. In case there are
9816+
not enough padding elements, return a partition with less than n items."
9817+
([n coll]
9818+
(partitionv n n coll))
9819+
([n step coll]
9820+
(lazy-seq
9821+
(when-let [s (seq coll)]
9822+
(let [p (into [] (take n) s)]
9823+
(when (= n (count p))
9824+
(cons p (partitionv n step (nthrest s step))))))))
9825+
([n step pad coll]
9826+
(lazy-seq
9827+
(when-let [s (seq coll)]
9828+
(let [p (into [] (take n) s)]
9829+
(if (= n (count p))
9830+
(cons p (partitionv n step pad (nthrest s step)))
9831+
(list (into [] (take n) (concat p pad)))))))))
9832+
9833+
(defnpartitionv-all
9834+
"Returns a lazy sequence of vector partitions, but may include
9835+
partitions with fewer than n items at the end.
9836+
Returns a stateful transducer when no collection is provided."
9837+
([n]
9838+
(partition-all n))
9839+
([n coll]
9840+
(partitionv-all n n coll))
9841+
([n step coll]
9842+
(lazy-seq
9843+
(when-let [s (seq coll)]
9844+
(let [seg (into [] (take n) coll)]
9845+
(cons seg (partitionv-all n step (drop step s))))))))
9846+
97409847
(defntake-while
97419848
"Returns a lazy sequence of successive items from coll while
97429849
(pred item) returns logical true. pred must be free of side-effects.
@@ -9824,7 +9931,12 @@ reduces them without incurring seq initialization"
98249931
(set! i (+ i step))
98259932
ret)))
98269933

9827-
(deftypeIntegerRange [meta start end step ^:mutable chunk ^:mutable chunk-next ^:mutable __hash]
9934+
(defn-range-count
9935+
"Returns exact size of remaining items in an IntegerRange."
9936+
[start end step]
9937+
(Math/ceil (/ (- end start) step)))
9938+
9939+
(deftypeIntegerRange [meta start end step cnt ^:mutable __hash]
98289940
Object
98299941
(toString [coll]
98309942
(pr-str* coll))
@@ -9838,23 +9950,15 @@ reduces them without incurring seq initialization"
98389950
(-lastIndexOf coll x (count coll)))
98399951
(lastIndexOf [coll x start]
98409952
(-lastIndexOf coll x start))
9841-
(forceChunk [coll]
9842-
(when (nil? chunk)
9843-
(let [count (-count coll)]
9844-
(if (> count32)
9845-
(do
9846-
(set! chunk-next (IntegerRange.nil (+ start (* step32)) end stepnilnilnil))
9847-
(set! chunk (IntegerRangeChunk. start step32)))
9848-
(set! chunk (IntegerRangeChunk. start step count))))))
98499953

98509954
ICloneable
9851-
(-clone [_] (IntegerRange. meta start end stepchunk chunk-next __hash))
9955+
(-clone [_] (IntegerRange. meta start end stepcnt __hash))
98529956

98539957
IWithMeta
98549958
(-with-meta [rng new-meta]
98559959
(if (identical? new-meta meta)
98569960
rng
9857-
(IntegerRange. new-meta start end stepchunk chunk-next __hash)))
9961+
(IntegerRange. new-meta start end stepcnt __hash)))
98589962

98599963
IMeta
98609964
(-meta [rng] meta)
@@ -9878,19 +9982,40 @@ reduces them without incurring seq initialization"
98789982
(-next [rng]
98799983
(if (pos? step)
98809984
(when (< (+ start step) end)
9881-
(IntegerRange.nil (+ start step) end stepnilnilnil))
9985+
(IntegerRange.nil (+ start step) end step(range-count (+ start step) end step)nil))
98829986
(when (> (+ start step) end)
9883-
(IntegerRange.nil (+ start step) end stepnilnilnil))))
9987+
(IntegerRange.nil (+ start step) end step (range-count (+ start step) end step)nil))))
9988+
9989+
IDrop
9990+
(-drop [rng n]
9991+
(if (pos? n)
9992+
(if (< n cnt)
9993+
(IntegerRange.nil (+ start (* step n)) end step (- cnt n)nil)
9994+
nil)
9995+
rng))
98849996

98859997
IChunkedSeq
98869998
(-chunked-first [rng]
9887-
(.forceChunk rng)
9888-
chunk)
9999+
(IntegerRangeChunk. start step (min cnt32)))
988910000
(-chunked-rest [rng]
9890-
(.forceChunk rng)
9891-
(if (nil? chunk-next)
10001+
(if (<= cnt32)
989210002
()
9893-
chunk-next))
10003+
(let [start (+ start (* step32))]
10004+
(cond
10005+
(pos? step)
10006+
(if (<= end start)
10007+
()
10008+
(IntegerRange.nil start end step (range-count start end step)nil))
10009+
10010+
(neg? step)
10011+
(if (>= end start)
10012+
()
10013+
(IntegerRange.nil start end step (range-count start end step)nil))
10014+
10015+
:else
10016+
(if (== end start)
10017+
()
10018+
(repeat start))))))
989410019

989510020
IChunkedNext
989610021
(-chunked-next [rng]
@@ -9911,7 +10036,7 @@ reduces them without incurring seq initialization"
991110036

991210037
ICounted
991310038
(-count [rng]
9914-
(Math/ceil (/ (- end start) step)))
10039+
cnt)
991510040

991610041
IIndexed
991710042
(-nth [rng n]
@@ -10060,14 +10185,14 @@ reduces them without incurring seq initialization"
1006010185
(if (<= end start)
1006110186
()
1006210187
(if (and (integer? start) (integer? end) (integer? step))
10063-
(IntegerRange.nil start end stepnilnilnil)
10188+
(IntegerRange.nil start end step(range-count start end step)nil)
1006410189
(Range.nil start end stepnilnilnil)))
1006510190

1006610191
(neg? step)
1006710192
(if (>= end start)
1006810193
()
1006910194
(if (and (integer? start) (integer? end) (integer? step))
10070-
(IntegerRange.nil start end stepnilnilnil)
10195+
(IntegerRange.nil start end step(range-count start end step)nil)
1007110196
(Range.nil start end stepnilnilnil)))
1007210197

1007310198
:else

‎src/main/clojure/cljs/core.cljc

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -820,7 +820,7 @@
820820
IPrintWithWriter IPending IWatchable IEditableCollection ITransientCollection
821821
ITransientAssociative ITransientMap ITransientVector ITransientSet
822822
IMultiFn IChunkedSeq IChunkedNext IComparable INamed ICloneable IAtom
823-
IReset ISwap IIterable])
823+
IReset ISwap IIterable IDrop])
824824
(iterate (core/fn [[p b]]
825825
(if (core/==2147483648 b)
826826
[(core/inc p)1]

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp