Pytanie min / max kolekcji zawierających NaN (obsługa nieporównywalnej ilości w zamówieniu)


Właśnie wpadłem na paskudny błąd w wyniku następującego zachowania:

scala> List(1.0, 2.0, 3.0, Double.NaN).min
res1: Double = NaN

scala> List(1.0, 2.0, 3.0, Double.NaN).max
res2: Double = NaN

Rozumiem, że w przypadku porównania parami czasami może być lepsze max(NaN, 0) = NaN i to jest prawdopodobnie powód, dla którego java.lang.Double.compare podąża za tą konwencją (wydaje się, że jest Standard IEEE za to). Jednak w przypadku kolekcji naprawdę uważam, że jest to dziwna konwencja. Po tym wszystkim powyższy zbiór zawiera prawidłowe liczby; a liczby te mają wyraźne maksimum i minimum. Moim zdaniem koncepcja, że maksymalny numer z kolekcji jest nie numer jest sprzecznością, ponieważ no cóż, NaN nie jest liczbą, więc nie może być maksymalną lub minimalną "liczbą" kolekcji - chyba że w ogóle nie ma prawidłowych numerów; w tym przypadku ma sens, że maksimum "nie jest liczbą". Semantycznie min i max funkcje zdegenerowane do sprawdzenia, czy kolekcja zawiera NaN. Ponieważ istnieją bardziej odpowiednie sposoby sprawdzania istnienia NaN (np. collection.find(_.isNaN)) Byłoby wspaniale utrzymać semantycznie znaczące min / max w kolekcjach.

Moje pytanie brzmi: jakie jest najlepsze podejście do uzyskania zachowania, aby zignorować istnienie NaN? Widzę dwie możliwości:

  1. Filtrowanie NaN przed wywołaniem min / max. Ponieważ wymaga to jawnego obchodzenia się z problemem we wszystkich miejscach i może podlegać karom wykonania, wolałbym coś łatwiejszego.

  2. Byłoby wspaniale mieć pewnego rodzaju porządkowanie ignorujące NaN, które może być użyte jako ukryty porządek wszędzie tam, gdzie jest to konieczne. Próbowałem następujące:

      object NanAwareOrdering extends Ordering[Double] {
        def compare(x: Double, y: Double) = {
          if (x.isNaN()) {
            +1 // without checking x, return y < x
          } else if (y.isNaN()) {
            -1 // without checking y, return x < y
          } else {
            java.lang.Double.compare(x, y)
          }
        }
      }
    

    Jednak wydaje się, że takie podejście zależy od tego, czy interesuje mnie znalezienie minimalnej lub maksymalnej wartości, tj .:

     scala> List(1.0, 2.0, 3.0, Double.NaN).min(NanAwareOrdering)
     res7: Double = 1.0
    
     scala> List(1.0, 2.0, 3.0, Double.NaN).max(NanAwareOrdering)
     res8: Double = NaN
    

    Oznacza to, że musiałbym mieć dwa NanAwareOrdering w zależności od tego, czy chcę minimum czy maksimum, które zabraniałoby posiadania implicit val. Dlatego moje pytanie brzmi: jak mogę zdefiniować porządek w taki sposób, aby obsłużyć oba przypadki jednocześnie?

Aktualizacja:

Dla kompletności: W trakcie analizy problemu zdałem sobie sprawę, że przesłanka "degeneruje się do sprawdzenia NaN" jest w rzeczywistości błędna. W rzeczywistości myślę, że jest jeszcze bardziej brzydka:

scala> List(1.0, Double.NaN).min
res1: Double = NaN

scala> List(Double.NaN, 1.0).min
res2: Double = 1.0

11
2018-05-09 12:00


pochodzenie


"maksymalna liczba kolekcji nie jest liczbą, jest sprzecznością, ponieważ no, NaN nie jest liczbą, więc nie może być maksymalną lub minimalną" liczbą "kolekcji" Metoda nazywa się max, nie maxNumberi nie zwraca liczb w innych przypadkach: np. gdy kolekcja nie jest liczb, ale innego uporządkowanego typu, lub gdy zawiera nieskończoności lub gdy jest pusta. Więc byłoby to dziwne, jeśli tylko NaN był specjalny-przypadek w standardowej bibliotece. - Alexey Romanov
Naprawdę nie widzę twojego punktu widzenia. Nazwa max funkcja nie powinna oczywiście zależeć od rodzaju podłoża. Jeśli twoja kolekcja zawiera Customerniż max dostaje "maksymalnego klienta". Gdy kolekcja zawiera "liczby", powinieneś otrzymać "maksymalną liczbę", prawda? I w tej analogii istnieje również pojęcie nieporównywalnego elementu: Ty też nie chciałbyś otrzymać UncomparableCustomer jako maksimum lub minimum. - bluenote10
1. Czy zgadzasz się z tym wariantem twojej argumentacji: jeśli zbiór zawiera liczby, to collection.head musi być liczbą, a więc List(Double.NaN, 1).head powinno być 1? Jeśli nie, jaka jest istotna różnica między head i max? - Alexey Romanov
2. Jak widzisz, nie możesz mieć jednego zamówienia, które traktuje NaNtak, jak chcesz. Podobnie, nie możesz napisać ogólnej max[T] co wyklucza NaNs. - Alexey Romanov
Istnieje ogromna różnica semantyczna pomiędzy head i max: Pierwszy jest czysto pozycyjny, drugi z natury zależy od uporządkowania (co znajduje również odzwierciedlenie w fakcie, że head nie wymaga żadnego niejawnego parametru). Skoro Scala oferuje możliwość niejawnego przekazania takiego zamówienia, czy nie jest to naturalne pragnienie przekazania zamówienia, które może obsłużyć "nieporównywalność" zgodnie z naszymi żądaniami? - bluenote10


Odpowiedzi:


Zastrzeżenie: dodam własną odpowiedź na to pytanie, na wypadek gdyby ktoś jeszcze był zainteresowany bardziej szczegółowymi informacjami na ten temat.

Pewna teoria ...

Wygląda na to, że ten problem jest bardziej złożony, niż się spodziewałem. Jak zauważył już Aleksiej Romanow, pojęcie nieporównywalności wymagałoby, aby funkcje maks / min przyjmowały częściowe uporządkowanie. Niestety, Alexey ma również rację, że ogólna funkcja max / min oparta na częściowym porządku nie ma sensu: pomyśl o przypadku, w którym częściowe porządkowanie definiuje tylko relacje w obrębie pewnych grup, ale same grupy są całkowicie niezależne od nawzajem (na przykład, elementy {a, b, c, d} z tylko dwoma relacjami a <b i c <d; mielibyśmy dwa maksimum / min). W tym względzie można nawet twierdzić, że formalnie max / min powinien zawsze zwraca dwie wartości, NaN i odpowiednie obowiązujące minimum / maksimum, ponieważ sam NaN jest również wartością ekstremalną w swojej własnej grupie powiązań.

W związku z tym, że częściowe zamówienia są zbyt ogólne / złożone, funkcje min / max przyjmują Ordering. Niestety, całkowita kolejność nie pozwala na pojęcie nieporównywalności. Przegląd trzech właściwości definiujących całkowite zamówienie sprawia, że ​​oczywiste jest, że "ignorowanie NaN" jest formalnie niemożliwe:

  1. Jeśli ≤ b i b ≤ a, a = b (antymymetria)
  2. Jeżeli ≤ b i b ≤ c, a ≤ c (przechodniość)
  3. a ≤ b lub b ≤ a (całość)

... i ćwicz ...

Więc kiedy próbuje wymyślić implementację Ordering aby spełnić nasze pożądane zachowanie min / max, jasne jest, że musimy coś naruszyć (i ponieść konsekwencje). Implementacja min/max/minBy/maxBy w TraversableOnce podąża za wzorem (dla min):

reduceLeft((x, y) => if (cmp.lteq(x, y)) x else y)

i gteq dla max warianty. To dało mi pojęcie "lewostronnego" porównania, tj .:

x   <comparison_operator> NaN    is always true to keep x in the reduction
NaN <comparison_operator> x      is always false to inject x into the reduction

Wynikowa implementacja takiego "lewostronnego" porządkowania wyglądałaby następująco:

object BiasedOrdering extends Ordering[Double] {
  def compare(x: Double, y: Double) = java.lang.Double.compare(x, y) // this is inconsistent, but the same goes for Double.Ordering

  override def lteq(x: Double, y: Double): Boolean  = if (x.isNaN() && !y.isNaN) false else if (!x.isNaN() && y.isNaN) true else if (x.isNaN() && y.isNaN) true  else compare(x, y) <= 0
  override def gteq(x: Double, y: Double): Boolean  = if (x.isNaN() && !y.isNaN) false else if (!x.isNaN() && y.isNaN) true else if (x.isNaN() && y.isNaN) true  else compare(x, y) >= 0
  override def lt(x: Double, y: Double): Boolean    = if (x.isNaN() && !y.isNaN) false else if (!x.isNaN() && y.isNaN) true else if (x.isNaN() && y.isNaN) false else compare(x, y) < 0
  override def gt(x: Double, y: Double): Boolean    = if (x.isNaN() && !y.isNaN) false else if (!x.isNaN() && y.isNaN) true else if (x.isNaN() && y.isNaN) false else compare(x, y) > 0
  override def equiv(x: Double, y: Double): Boolean = if (x.isNaN() && !y.isNaN) false else if (!x.isNaN() && y.isNaN) true else if (x.isNaN() && y.isNaN) true  else compare(x, y) == 0

}

... przeanalizował:

Obecnie staram się dowiedzieć:

  • jak ta kolejność porównuje się z domyślną kolejnością,
  • gdzie naruszamy całkowite właściwości zamówienia,
  • i jakie są potencjalne problemy.

Porównuję to do domyślnej kolejności Scali Ordering.Double oraz następujące uporządkowanie, które pochodzi bezpośrednio z java.lang.Double.compare:

object OrderingDerivedFromCompare extends Ordering[Double] {
  def compare(x: Double, y: Double) = {
    java.lang.Double.compare(x, y)
  }
}

Jedna interesująca właściwość domyślnej kolejności Scali Ordering.Double jest to, że nadpisuje wszystkie funkcje porównywania przez natywne operatory porównania liczbowego (<, <=, ==, >=, >), więc wyniki porównania są identyczne, jakbyśmy mogli porównać bezpośrednio z tymi operatorami. Poniżej przedstawiono wszystkie możliwe zależności między NaN i prawidłową liczbą dla trzech zamówień:

Ordering.Double             0.0 >  NaN = false
Ordering.Double             0.0 >= NaN = false
Ordering.Double             0.0 == NaN = false
Ordering.Double             0.0 <= NaN = false
Ordering.Double             0.0 <  NaN = false
OrderingDerivedFromCompare  0.0 >  NaN = false
OrderingDerivedFromCompare  0.0 >= NaN = false
OrderingDerivedFromCompare  0.0 == NaN = false
OrderingDerivedFromCompare  0.0 <= NaN = true
OrderingDerivedFromCompare  0.0 <  NaN = true
BiasedOrdering              0.0 >  NaN = true
BiasedOrdering              0.0 >= NaN = true
BiasedOrdering              0.0 == NaN = true
BiasedOrdering              0.0 <= NaN = true
BiasedOrdering              0.0 <  NaN = true

Ordering.Double             NaN >  0.0 = false
Ordering.Double             NaN >= 0.0 = false
Ordering.Double             NaN == 0.0 = false
Ordering.Double             NaN <= 0.0 = false
Ordering.Double             NaN <  0.0 = false
OrderingDerivedFromCompare  NaN >  0.0 = true
OrderingDerivedFromCompare  NaN >= 0.0 = true
OrderingDerivedFromCompare  NaN == 0.0 = false
OrderingDerivedFromCompare  NaN <= 0.0 = false
OrderingDerivedFromCompare  NaN <  0.0 = false
BiasedOrdering              NaN >  0.0 = false
BiasedOrdering              NaN >= 0.0 = false
BiasedOrdering              NaN == 0.0 = false
BiasedOrdering              NaN <= 0.0 = false
BiasedOrdering              NaN <  0.0 = false

Ordering.Double             NaN >  NaN = false
Ordering.Double             NaN >= NaN = false
Ordering.Double             NaN == NaN = false
Ordering.Double             NaN <= NaN = false
Ordering.Double             NaN <  NaN = false
OrderingDerivedFromCompare  NaN >  NaN = false
OrderingDerivedFromCompare  NaN >= NaN = true
OrderingDerivedFromCompare  NaN == NaN = true
OrderingDerivedFromCompare  NaN <= NaN = true
OrderingDerivedFromCompare  NaN <  NaN = false
BiasedOrdering              NaN >  NaN = false
BiasedOrdering              NaN >= NaN = true
BiasedOrdering              NaN == NaN = true
BiasedOrdering              NaN <= NaN = true
BiasedOrdering              NaN <  NaN = false

Widzimy to:

  • tylko OrderingDerivedFromCompare spełnia całkowite właściwości zamówienia. Na podstawie tego wyniku uzasadnienie java.lang.Double.compare staje się o wiele bardziej przejrzysty: umieszczenie NaN na górnym końcu całego porządku pozwala uniknąć sprzeczności!
  • Domyślna kolejność Scali i stronniczy porządek naruszają wiele warunków całkowitych. Domyślna kolejność Scali zawsze powraca false, podczas gdy dla stronniczej kolejności zależy od pozycji. Ponieważ oba prowadzą do sprzeczności, trudno jest dostrzec, które mogą prowadzić do poważniejszych problemów.

Teraz do naszego aktualnego problemu, funkcje min / max. Dla OrderingDerivedFromCompare teraz jest jasne, co musimy uzyskać - NaN jest po prostu największą wartością, więc oczywiste jest, że uzyskujemy ją jako max, niezależnie od tego, jak są uporządkowane elementy na liście:

OrderingDerivedFromCompare  List(1.0, 2.0, 3.0, Double.NaN).min = 1.0
OrderingDerivedFromCompare  List(Double.NaN, 1.0, 2.0, 3.0).min = 1.0
OrderingDerivedFromCompare  List(1.0, 2.0, 3.0, Double.NaN).max = NaN
OrderingDerivedFromCompare  List(Double.NaN, 1.0, 2.0, 3.0).max = NaN

Teraz do domyślnego uporządkowania Scali. Byłem głęboko zszokowany widząc, że sytuacja jest jeszcze bardziej skomplikowana niż wspomniano w moim pytaniu:

Ordering.Double             List(1.0, 2.0, 3.0, Double.NaN).min = NaN
Ordering.Double             List(Double.NaN, 1.0, 2.0, 3.0).min = 1.0
Ordering.Double             List(1.0, 2.0, 3.0, Double.NaN).max = NaN
Ordering.Double             List(Double.NaN, 1.0, 2.0, 3.0).max = 3.0

W rzeczywistości kolejność elementów staje się istotna (w wyniku powracania false za każde porównanie w reduceLeft). "Lewe odchylenie" oczywiście rozwiązuje ten problem, prowadząc do spójnych wyników:

BiasedOrdering              List(1.0, 2.0, 3.0, Double.NaN).min = 1.0
BiasedOrdering              List(Double.NaN, 1.0, 2.0, 3.0).min = 1.0
BiasedOrdering              List(1.0, 2.0, 3.0, Double.NaN).max = 3.0
BiasedOrdering              List(Double.NaN, 1.0, 2.0, 3.0).max = 3.0

Niestety nadal nie jestem w stanie odpowiedzieć na wszystkie pytania tutaj. Niektóre pozostałe punkty to:

  • Dlaczego domyślne uporządkowanie Scali zostało zdefiniowane tak, jak jest? Obecnie obsługa NaN wydaje się być dość wadliwa. Bardzo niebezpieczny szczegół Ordering.Double jest to, że compare funkcja faktycznie deleguje do java.lang.Double.compare, podczas gdy członek porównania jest wdrażany w oparciu o porównania natywne języka. To oczywiście prowadzi do niespójnych wyników, na przykład:

    Ordering.Double.compare(0.0, Double.NaN) == -1     // indicating 0.0 < NaN
    Ordering.Double.lt     (0.0, Double.NaN) == false  // contradiction
    
  • Jakie są potencjalne wady BiasedOrderingoprócz bezpośredniej oceny sprzecznego porównania? Szybkie sprawdzenie sorted dał następujące wyniki, które nie wykazały żadnych problemów:

    Ordering.Double             List(1.0, 2.0, 3.0, Double.NaN).sorted = List(1.0, 2.0, 3.0, NaN)
    OrderingDerivedFromCompare  List(1.0, 2.0, 3.0, Double.NaN).sorted = List(1.0, 2.0, 3.0, NaN)
    BiasedOrdering              List(1.0, 2.0, 3.0, Double.NaN).sorted = List(1.0, 2.0, 3.0, NaN)
    
    Ordering.Double             List(Double.NaN, 1.0, 2.0, 3.0).sorted = List(1.0, 2.0, 3.0, NaN)
    OrderingDerivedFromCompare  List(Double.NaN, 1.0, 2.0, 3.0).sorted = List(1.0, 2.0, 3.0, NaN)
    BiasedOrdering              List(Double.NaN, 1.0, 2.0, 3.0).sorted = List(1.0, 2.0, 3.0, NaN)
    

Na razie będę miał wolną rękę z tym lewicowym zamówieniem. Ale ponieważ natura problemu nie pozwala na nieskazitelne ogólne rozwiązanie: używaj ostrożnie!

Aktualizacja

A jeśli chodzi o rozwiązania oparte na domniemanej klasie, jak sugerował monkjack, bardzo podoba mi się to, co następuje (ponieważ w ogóle nie miesza się z (błędnymi?) Zamówieniami ogółem, ale wewnętrznie przekształca się w czysto całkowicie uporządkowaną domenę):

implicit class MinMaxNanAware(t: TraversableOnce[Double]) {
  def nanAwareMin = t.minBy(x => if (x.isNaN) Double.PositiveInfinity else x)
  def nanAwareMax = t.maxBy(x => if (x.isNaN) Double.NegativeInfinity else x)
}

// and now we can simply use
val goodMin = list.nanAwareMin

5
2018-05-10 21:01





Co powiesz na implicite w zakresie, który pozwoliłby ci na dodanie nowych metod min / max na liście.

Coś jak:

object NanAwareMinOrdering extends Ordering[Double] {
    def compare(x: Double, y: Double) = {
      if (x.isNaN()) {
        +1 // without checking x, return y < x
      } else if (y.isNaN()) {
        -1 // without checking y, return x < y
      } else {
        java.lang.Double.compare(x, y)
      }
    }
  }

object NanAwareMaxOrdering extends Ordering[Double] {
  ....
}

implicit class MinMaxList(list:List[Double]) {
  def min2 = list.min(NanAwareMinOrdering)
  def max2 = list.max(NanAwareMaxOrdering)
}

List(1.0, 2.0, 3.0, Double.NaN).min2


2
2018-05-09 12:10



Możesz zdefiniować niejawne, aby zaakceptować Seq lub jakiś inny wspólny super typ twoich klas kolekcji. A metoda min2 / max2 nie musi koniecznie używać filtra (to tylko dla szybkości odpowiedzi), możesz wywołać min / max na oryginale z niestandardową kolejnością, którą zasugerowałeś, lub zrobić cokolwiek innego. - monkjack
Tak, to prawdopodobnie ma sens, aby go zdefiniować tylko TraversableOnce, który również zapewnia samą min / max. I będziemy dalej potrzebować maxBy/minBy wdrożenia. - bluenote10
Tak, więc po prostu używaj zamawiania min2 / max2 zamiast filtra i min / max. - monkjack
Zaktualizowana odpowiedź, aby pokazać, co mam na myśli. - monkjack
Można dodać ukrytą kolejność, która zgłasza wyjątek podczas wywoływania. Tak więc list.max / list.min użyłby tego niejawnie, podczas gdy min2 / max2 użyłby innych porządków i pracy. Trochę zdziczały może, ale zadziała. - monkjack


Dla

val a = List(1.0, 2.0, 3.0, Double.NaN)

Posortuj to,

a.sortWith {_ >_ }
res: List[Double] = List(3.0, 2.0, 1.0, NaN)

a więc NaN wartości są relegowane, a więc dla max,

a.sortWith {_ >_ }.head
res: Double = 3.0

Również

a.sortWith {_ < _ }
res: List[Double] = List(1.0, 2.0, 3.0, NaN)

a więc przez min,

a.sortWith {_ < _ }.head
res: Double = 1.0

1
2018-05-09 12:28



Biorąc pod uwagę moje ogromne rozmiary kolekcji, zmiana z O (N) na O (N log N) prawdopodobnie spowodowałaby pewne problemy ... - bluenote10
@ bluenote10 Być może możliwa jest nie-idiomatyczna iteracja dotycząca gromadzenia i aktualizacji wartości maksymalnych lub minimalnych zmiennych zmiennych. Od momentu zainicjowania pierwszej minuty lub maksimum pierwsze wystąpienie nieNaN z kolekcji. - elm
Właściwie to lubię wygodę min/max/minBy/maxBy dużo. Przed całkowitym zaniedbaniem tych funkcji nadal wolałbym jawnie przekazać NanIgnoringMaxOrdering i NanIgnoringMinOrdering w zależności od tego, czy wykonam min czy max. - bluenote10


Ta odpowiedź jest po prostu wyjaśnieniem problemu, odpowiedź @ monkjack prawdopodobnie zapewnia najlepsze praktyczne rozwiązanie.

Skoro Scala oferuje możliwość niejawnego przekazania takiego zamówienia, czy nie jest to naturalne pragnienie przekazania zamówienia, które może obsłużyć "nieporównywalność" zgodnie z naszymi wymaganiami

Ordering w Scala tylko reprezentuje całkowity uporządkowania, tj. te, w których wszystkie elementy są porównywalne. Tam jest PartialOrdering[T]: http://www.scala-lang.org/api/2.10.3/index.html#scala.math.PartialOrdering, ale jest kilka problemów:

  1. W rzeczywistości nie jest on używany nigdzie w standardowej bibliotece.

  2. Jeśli próbujesz wdrożyć max/maxBy/itp. które biorą PartialOrdering, szybko zobaczysz, że nie jest to ogólnie możliwe z wyjątkiem w takich przypadkach jak Float/Double gdzie masz elementy, które nie są porównywalne z niczym i całą resztą  porównywalne ze sobą (możesz zdecydować się po prostu zignorować nieporównywalne elementy).


1
2018-05-10 11:11



Bardzo dobra uwaga końcowa - właśnie miałem zamiar opublikować coś bardzo podobnego w wyniku niewielkich badań. - bluenote10