I've written vector version. As you can make subvectors really
fast, and you can take element at index really fast, I just throw
out last element at each iteration.
(letfn [(vec-throw-out [v i]
(pop (assoc v i (get v (dec (count v))))))]
(defn lazy-shuffle [v]
(if (seq v)
(let [idx (rand-int (count v))]
(cons
(get v idx)
(lazy-seq
(lazy-shuffle
(vec-throw-out v idx))))))))
(defn lazy-shuffle2
[coll]
(let [rand-pos (rand-int (count coll))
[prior remainder] (split-at rand-pos coll)]
(cons
(nth coll rand-pos)
(lazy-seq (lazy-shuffle (concat prior (rest remainder)))))))
(let [s (range 1000000)
v (vec s)]
(time (take 10 (lazy-shuffle v)))
(time (take 10 (lazy-shuffle2 s)))
nil)
;; "Elapsed time: 0.092389 msecs"
;; "Elapsed time: 185.869154 msecs"
Понеділок, 26 січня 2009 р. 23:46:20 UTC+2 користувач Boris V. Schmid
написав:
>
> In addition to the functional shuffle thread (can't seem to post to
> that one anymore, might be too old?), I've written a lazy shuffle. Not
> sure if it is the best way to write it, but I needed a lazy shuffle
> primarily because I wanted to randomly pair a few agents from a large
> vector of agents without agents occurring one more than once.
>
>
> http://groups.google.com/group/clojure/browse_thread/thread/180842eb58c58370/0e19ab338452c64f?tvc=2&q=shuffle#0e19ab338452c64f
>
>
> (defn lazy-shuffle
> [coll]
> (let [rand-pos (rand-int (count coll))
> [prior remainder] (split-at rand-pos coll)]
> (lazy-cons (nth coll rand-pos) (lazy-shuffle (concat prior (rest
> remainder))))))
>
>
> user=> (time (take 50 (lazy-shuffle (range 10000))))
>
> "Elapsed time: 0.246 msecs"
> user=> (time (take 50 (shuffle-java (range 10000))))
>
> "Elapsed time: 0.573 msecs"
>
> (defn frequencies
> "Returns a map from distinct items in coll to the number
> of times they appear."
> [coll]
> (reduce (fn [counts x]
> (merge-with + counts {x 1}))
> {} coll))
>
> (frequencies (map (fn [n] (take 3 (lazy-shuffle (list 1 2 3)))) (range
> 1000000)))
> {(3 1 2) 166687, (1 2 3) 166126, (1 3 2) 167246, (3 2 1) 166918, (2 3
> 1) 166687, (2 1 3) 166336}
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
