The problem here is that you're not following your Scala solution closely
enough. I suspect if you used defrecords to represent the pieces the way
that you used a class in Scala you can avoid the number of collisions for
larger problems.
Not tested much but I tried something like the following and I no longer
see hash collisions dominating in YourKit:
(defrecord Piece [name pos])
(defn piece [name pos]
(Piece. name pos))
(defn takes? [name [dx dy]]
(case name
:K (and (<= dx 1) (<= dy 1))
:Q (or (zero? dx) (zero? dy) (== dx dy))
:R (or (zero? dx) (zero? dy))
:B (== dx dy)
:N (or (and (== dx 1) (== dy 2)) (and (== dx 2) (== dy 1)))))
(defn allows? [{name :name [px py] :pos} [x y]]
(let [delta [(Math/abs (int (- px x))) (Math/abs (int (- py y)))]]
(and (not (and (== px x) (== py y))) (not (takes? name delta)))))
(defn allowed? [{cname :name cpos :pos :as cand} solution]
(every?
(fn [{pos :pos :as piece}]
(and (allows? piece cpos) (allows? cand pos)))
solution))
(defn solve [rows cols pieces]
(if (empty? pieces)
#{#{}}
(set
(let [name (first pieces)]
(for [solution (solve rows cols (rest pieces))
x (range 0 cols)
y (range 0 rows)
:let [cand (piece name [x y])]
:when (allowed? cand solution)]
(conj solution cand))))))
David
On Wed, Oct 23, 2013 at 1:28 PM, Paul Butcher <p...@paulbutcher.com> wrote:
> On 23 Oct 2013, at 18:15, Andy Fingerhut <andy.finger...@gmail.com> wrote:
>
> If we had a 'universal comparator', i.e. a comparison function that
> provided a total order on any pair of values that anyone would ever want to
> put into a set or use as a map key, then instead of having linked lists for
> values that collide, we could have trees like those in the implementations
> of sorted-maps and sorted-sets today.
>
>
> Wouldn't it be better to improve the way that hashes are calculated for
> vectors? A good hash function should make it unlikely that similar values
> have the same hash. The current algorithm seems to make that more likely
> than it should?
>
> --
> paul.butcher->msgCount++
>
> Snetterton, Castle Combe, Cadwell Park...
> Who says I have a one track mind?
>
> http://www.paulbutcher.com/
> LinkedIn: http://www.linkedin.com/in/paulbutcher
> MSN: p...@paulbutcher.com
> AIM: paulrabutcher
> Skype: paulrabutcher
>
> --
> --
> 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
> Note that posts from new members are moderated - please be patient with
> your first post.
> 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
> ---
> 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 clojure+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
--
--
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
Note that posts from new members are moderated - please be patient with your
first post.
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
---
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 clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
