Hi,
that's a nice example of using closures to store data!
(f)first and rest look like constant time to me. count is linear time,
but could easily be made constant time by storing the counts instead
of recursing.
Insertion is linear time though, plus it recurses, resulting in stack
sizes in the order of the length of the queue.
Here's a version that's roughly equivalent (including the recursion
problem), but uses maps instead of closures:
(defn prio-insert [queue elem prio]
(if (> prio (:prio queue (Integer/MIN_VALUE)))
{:first elem
:prio prio
:count (inc (:count queue 0))
:rest queue}
(let [new-rest (prio-insert (:rest queue) elem prio)]
(assoc queue
:rest new-rest
:count (inc (:count new-rest))))))
user=> (def pq (prio-insert nil 3 4))
#'user/pq
user=> pq
{:first 3, :prio 4, :count 1, :rest nil}
user=> (def pq (prio-insert pq 2 10))
#'user/pq
user=> pq
{:first 2, :prio 10, :count 2, :rest {:first 3, :prio 4, :count
1, :rest nil}}
user=> (def pq (prio-insert pq 4 1))
#'user/pq
user=> pq
{:first 2, :prio 10, :count 3, :rest {:first 3, :prio 4, :count
2, :rest {:first 4, :prio 1, :count 1, :rest nil}}}
user=> (:first (:rest pq))
3
Kind regards,
achim
Am 01.03.2009 um 06:31 schrieb zoglma...@gmail.com:
>
> After helping tutor some students earlier in the week on the subject
> of priority queues, I ended up implementing it in Clojure as a mutable
> data structure. It was straight forward, but curiosity struck and I
> implemented the priority queue as an immutable data structure. I'm
> pretty sure that 'ffirst 'first 'count and 'rest have a constant time
> complexity, but it is a little hard to wrap my mind around this code.
> Is it really constant time?
>
> ;----- immutiable priority queue -----
>
> (defn priority-cons [priority data queue]
> (defstruct element :priority :data)
> (let [elem (struct element priority data)
> queue-first
> (if (nil? queue)
> nil
> (queue 'ffirst))
> queue-rest
> (cond
> (nil? queue)
> nil
> (nil? elem)
> (queue 'rest)
> (>= priority (queue-first :priority))
> queue
> :else
> (priority-cons priority data (queue 'rest)))]
> (fn [op]
> (cond (= op 'count)
> (cond
> (nil? queue)
> 1
> (nil? elem)
> (queue 'count)
> :else
> (inc (queue 'count)))
> (= op 'first)
> (cond
> (nil? queue)
> data
> (nil? elem)
> nil
> (>= priority (queue-first :priority))
> data
> :else
> (queue-first :data))
> (= op 'ffirst)
> (cond
> (nil? queue)
> elem
> (nil? elem)
> nil
> (>= priority (queue-first :priority))
> elem
> :else
> queue-first)
> (= op 'rest)
> queue-rest
> ))))
>
> ;--- testing code
>
> (defn print-priority-queue [queue]
> (loop [queue queue]
> (if (nil? queue)
> nil
> (do
> (println (queue 'first))
> (recur (queue 'rest))))))
>
> (def a (priority-cons 10 "hello" nil))
> (print-priority-queue a)
> (a 'count)
>
> (def b (priority-cons 20 "hello2" a))
> (print-priority-queue b)
> (b 'count)
>
> (def c (priority-cons 15 "hello-m" b))
> (print-priority-queue c)
> (c 'count)
>
> ((c 'rest) 'count)
> (((c 'rest) 'rest) 'first)
> (((c 'rest) 'rest) 'count)
> (((c 'rest) 'rest) 'rest)
>
> >
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to clojure@googlegroups.com
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
