Как рассчитать частоты для последовательностей, содержащих NaN?

Question

Результат frequencies неверен при использовании для последовательностей, содержащих NaN с, например:

=> (frequencies [Double/NaN Double/NaN])
{NaN 1, NaN 1}

вместо ожидаемых {NaN 2}.

Кроме того, время работы ухудшается с ожидаемого / среднего O(n) до наихудшего O(n^2), например,

=> (def v3 (vec (repeatedly 1e3 #(Double/NaN))))
=> (def r (time (frequencies v3)))
"Elapsed time: 36.081751 msecs"
...
=> (def v3 (vec (repeatedly 1e3 #(Double/NaN))))
=> (def r (time (frequencies v3)))
"Elapsed time: 3358.490101 msecs"
...

, т. Е. В 10 раз больше элементов требуют в 100 раз больше времени работы.

Как можно рассчитать частоты с (ожидаемым / средним) O(n) временем работы, когда в последовательности присутствует NaN с?

---

Как примечание стороны:

 => (frequencies (repeat 1e3 Double/NaN))
 {NaN 1000}

дает ожидаемый результат, возможно, потому что все элементы в последовательности являются ссылками на один и тот же объект.

Answer 1

NaN довольно странно во многих языках программирования, отчасти потому, что стандарт IEEE 754 для чисел с плавающей запятой определяет, что NaN не должен равняться ничему, даже самому себе. Это часть «даже не сама», которая приводит к большей части странного поведения, которое вы видите. Подробнее здесь, если вам интересно: https://github.com/jafingerhut/batman

Пример функции ниже может быть адаптирован к вашим потребностям. Он использует: nan-kw в возвращенной карте, чтобы указать, сколько NaN было найдено. Если вы замените: nan-kw на ## NaN, то у возвращенной карты есть недостаток, заключающийся в том, что вы не можете найти счетчик с помощью (получить возвращаемое значение частоты ## NaN) из-за странности ## NaN.

(defn frequencies-maybe-nans [s]
  (let [separate-nans (group-by #(and (double? %) (Double/isNaN %)) s)
        num-nans (count (separate-nans true))]
    (merge (frequencies (separate-nans false))
           (when-not (zero? num-nans)
             {:nan-kw num-nans}))))

(def freqs (frequencies-maybe-nans [1 2 ##NaN 5 5]))
freqs
(get freqs 2)
(get freqs :nan-kw)

Answer 2

Некоторые значения фона NaN в JVM: https://www.baeldung.com/java-not-a-number

---

Это можно решить путем временного кодирования значений NaN при вычислении частот:

(ns tst.demo.core
  (:use tupelo.core
        tupelo.test))

(defn is-NaN? [x] (.isNaN x))

(defn nan-encode
  [arg]
  (if (is-NaN? arg)
    ::nan
    arg))

(defn nan-decode
  [arg]
  (if (= ::nan arg)
    Double/NaN
    arg))

(defn freq-nan
  [coll]
  (it-> coll
    (mapv nan-encode it)
    (frequencies it)
    (map-keys it nan-decode)))

(dotest
  (let [x [1.0 2.0 2.0 Double/NaN Double/NaN Double/NaN]]
    (is= (spyx (freq-nan x)) {1.0   1,
                              2.0   2,
                              ##NaN 3})))

с результатом:

-------------------------------
   Clojure 1.10.1    Java 13
-------------------------------

Testing tst.demo.core

(freq-nan x) => {1.0 1, 2.0 2, ##NaN 3}

FAIL in (dotest-line-25) (core.clj:27)
expected: (clojure.core/= (spyx (freq-nan x)) {1.0 1, 2.0 2, ##NaN 3})
  actual: (not (clojure.core/= {1.0 1, 2.0 2, ##NaN 3} {1.0 1, 2.0 2, ##NaN 3}))

Обратите внимание, что, несмотря на то, что он вычисляет и печатает правильный результат, модульный тест все равно не пройден, поскольку NaN никогда не равняется ничему, даже самому себе. Если вы хотите, чтобы модульный тест прошел, вы должны оставить в качестве заполнителя ::nan, например:

(defn freq-nan
  [coll]
  (it-> coll
    (mapv nan-encode it)
    (frequencies it)
  ))

(dotest
  (let [x [1.0 2.0 2.0 Double/NaN Double/NaN Double/NaN]]
    (is= (spyx (freq-nan x)) {1.0   1,
                              2.0   2,
                              ::nan 3})))