code-reviews 2019-10-07 | Slack Archive

tdantas17:10:38

the sort is returning an ArraySeq which does not implements RandomAccess interface. to proper use the binarySearch full power, your datatype must implement the RandomAccess (for instance PersistentVector ) final solution , less than 1 second to run on 100K items

(defn solution [team-a team-b]
    (let [steam-a (into [] (sort team-a))
          search #(java.util.Collections/binarySearch steam-a %1)
          mapper  (comp inc search)]
       (mapv #(Math/abs (mapper %1)) team-b)))

jaihindhreddy18:10:58

A style point: the inc and the Math/abs can be done inline. Also, because steam-a doesn't escape the function, we can make it a mutable array of primitive ints, which has excellent cache locality. Throw in a couple of type hints to remove reflection, and you got a pretty fast solution:

(defn solution [team-a team-b]
  (let [steam-a ^ints (into-array Integer/TYPE (sort team-a))]
    (mapv #(-> (java.util.Arrays/binarySearch steam-a ^int %)
               inc
               Math/abs)
          team-b)))

jaihindhreddy18:10:46

In fact, we can do the sort in-place in the array to get even more perf.

(defn solution [team-a team-b]
  (let [steam-a ^ints (into-array Integer/TYPE team-a)]
    ; Sorts the array in-place
    (java.util.Arrays/sort steam-a)
    (mapv #(-> (java.util.Arrays/binarySearch steam-a ^int %)
               inc
               Math/abs)
          team-b)))

Note though, haven't benchmarked, so perf claims might as well be baloney 😅

tdantas20:10:44

Thanks for your tips , gonna update my code

tdantas17:10:51

thanks @dominicm and @jaihindhreddy

noisesmith17:10:59

@oliv another option: sorted-set instead of [], then the sorting is implicit, and it is splittable for binary search

noisesmith17:10:31

that also removes dupes - may be incompatibel with some other requirement

tdantas17:10:03

nice @noisesmith, good way to distinct values and sort

2019-10-07

Channels