How to optimize a function that selects from a list only elements that occur more than n times?

Question

Algorithms

I wrote a function that counts how many times each element occurs in a vector and creates a new vector of type [{:value count} {:value count} ... ], then I filter the new vector so that only elements that greater than n
However, having shown this to the teacher, they pointed out to me that the algorithm is inefficient, since the growth rate of the algorithm is high. How can this be fixed?

(defn CountsElement [vec value]
           (count (filter (fn[l] (= l value)) vec)))

(defn ValueToCountValue [vec]
  (let [v vec
        size (count v)]
    (loop [i 0 newVec []]
      (if (< i size)
        (recur (inc i) (conj newVec {:count (CountsElement v (v i)),
                                     :value (v i)}
                             )) newVec ))))

(defn search [vec value]
  (map :value (filter (fn[l] (> (l :count) value)) (ValueToCountValue vec))))

(println "Result" [3 0 1 7 1 2 3 3]  (ValueToCountValue [3 0 1 7 1 2 3 3]))
(println "Result" (search  [3 0 1 7 1 2 3 3] 1))

Answer 1

There is a frequency function in the standard library . But if the invention of the bicycle is for educational purposes, then:

(defn calculate-frequencies [xs]
  (reduce
   (fn [xs x] (assoc xs x (inc (get xs x 0))))
   {}
   xs))

(defn greater-then [m n]
  (filter #(> (val %) n) m))

PS It is worth sticking to the accepted code style convention .

Answer 2

For the general case, sort the array and count the number in one pass and put it in a new array.
For special cases, there may be a more optimal solution.