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

Question

[lllaptemlll]

Я написал функцию, которая, подсчитывает сколько раз каждый элемент встречается в векторе и создаю новый вектор по типу [{: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))

Answer 1

[Сергей Горностаев]

В стандартной библиотеке есть функция 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. Стоит придерживаться принятого соглашения о стиле кода.

Comments

[lllaptemlll]

Спасибо!

Answer 2

[Rsa97]

Для общего случая - отсортировать массив и одним проходом посчитать количество и занести в новый массив.
Для частных случаев может быть и более оптимальное решение.

Comments

[lllaptemlll]

Когда я первый раз начал писать код, я кстати так и сделал
На что преподаватель ответил, что сортировка слишком дорогая по времязатратности операция

[Rsa97]

lllaptemlll, сортировка по затратности такая же, как и работа с ассоциативным массивом. И там, и там будет O(n log(n)).

[Владимир Олохтонов]

Посчитать элементы можно и без сортировки за O(n) при использовании хеш-таблицы.

O(nlogn) будет если дерево поиска использовать, но зачем?

[Rsa97]

Владимир Олохтонов, А какого размера должна быть хэш-таблица? И какая должна быть хэш-функция? При неудачном выборе можно получить для каждой операции поиска/вставки O(n), а значит общая сложность вырастет до O(n²).

[Владимир Олохтонов]

Rsa97, для этой задачи хватит стандартной реализации из языка, не знаю уж что там в clojure. Обычно от хеш-функции требуют равной вероятности попадания в каждую ячейку (кажется это называется универсальность) и этого хватает для нормальной работы, но подробностей не знаю – тут я уже плаваю :)

Размер таблицы линейно зависит от числа уникальных элементов во входных данных, как и в случае дерева впрочем.

[Rsa97]

Владимир Олохтонов, Стандартная реализация ассоциативного массива может быть и на дереве, тогда будет тот же O(n log(n)), что и у сортировки.

[Владимир Олохтонов]

Rsa97, нашёл вот такое: https://clojure.org/reference/data_structures#Maps

Hash maps provide faster access (log32N hops) vs (logN hops), but sorted maps are, well, sorted.

[Rsa97]

Владимир Олохтонов,

Hash maps require keys that correctly support hashCode and equals.

То есть, массив на хэше будет работать не со всеми типами данных.

[Владимир Олохтонов]

Rsa97, вас это удивляет? Напомню, что речь шла о числах :)

[Rsa97]

Владимир Олохтонов, Где? В вопросе использовано слово "элементы", а значит может быть что угодно.

[Владимир Олохтонов]

Rsa97, я глазом зацепился за последние 2 строки. В любом случае задача академическая, быстрее чем за линию её не решить, я на такое решение указал.