Задать вопрос
@lllaptemlll

Как оптимизировать функцию, выбирающую из списка только элементы, встречающиеся более n-раз?

Я написал функцию, которая, подсчитывает сколько раз каждый элемент встречается в векторе и создаю новый вектор по типу [{:value count} {:value count} ... ], после чего отфильтровываю новый вектор, чтобы в нем остались только элементы, которые больше n
Однако, показав это преподавателю, мне указали на то, что алгоритм неэффективен, так как большая скорость роста алгоритма. Как это можно исправить?

(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))
  • Вопрос задан
  • 167 просмотров
Подписаться 1 Средний Комментировать
Решения вопроса 1
sergey-gornostaev
@sergey-gornostaev Куратор тега Clojure
Седой и строгий
В стандартной библиотеке есть функция frequencies. Но если изобретение велосипеда в учебных целях, то:
(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))

P.S. Стоит придерживаться принятого соглашения о стиле кода.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Для общего случая - отсортировать массив и одним проходом посчитать количество и занести в новый массив.
Для частных случаев может быть и более оптимальное решение.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы