Porównanie trójstronne - Three-way comparison
W informatyce , o porównanie trójdrożny przyjmuje dwie wartości A i B należących do typu z całkowitym porządku i określa, czy A <B, A = B lub A> B w jednej operacji, zgodnie z matematycznym prawem trichotomia .
Obliczenia na poziomie maszyny
Wiele procesorów ma zestawy instrukcji, które obsługują taką operację na typach pierwotnych. Niektóre maszyny mają liczby całkowite ze znakiem oparte na reprezentacji znaku-i-wielkości lub dopełnienia (patrz reprezentacje liczby ze znakiem ), z których obie pozwalają na zróżnicowane dodatnie i ujemne zero . Nie narusza to trichotomii, o ile przyjmuje się spójny porządek całkowity: -0 = +0 lub -0 < +0. Wspólne zmiennoprzecinkowe typy mają jednak wyjątek trichotomię: istnieje szczególna wartość „NaN” ( Not a Number ) takie, że x <NaN, x > NaN i x = NaN są fałszywe dla wszystkich wartości zmiennoprzecinkowychx (w tym sam NaN).
Języki wysokiego poziomu
Możliwości
W C , funkcje strcmpi memcmpwykonują trójstronne porównanie odpowiednio między ciągami i buforami pamięci. Zwracają liczbę ujemną, gdy pierwszy argument jest leksykograficznie mniejszy niż drugi, zero, gdy argumenty są równe, a dodatnią liczbę w przeciwnym razie. Ta konwencja zwracania „znaku różnicy” jest rozszerzona na dowolne funkcje porównujące przez standardową funkcję sortującą qsort, która przyjmuje funkcję porównywania jako argument i wymaga jej przestrzegania.
W C ++ The C ++ 20 rewizja dodaje „ operator statku kosmicznego ” <=>, który podobnie Zwraca znak różnicy, a także może zwracać różne typy (z możliwością zamiany na podpisanych liczb całkowitych) w zależności od surowości porównania.
W Perlu (tylko do porównań numerycznych, cmpoperator jest używany do porównań leksykalnych ciągów), PHP (od wersji 7), Ruby i Apache Groovy , "operator statku kosmicznego" <=>zwraca wartości -1, 0 lub 1 w zależności od tego, czy A < B, A = B lub A > B, odpowiednio. Funkcje Pythona 2.x cmp(usunięte w 3.x), OCaml compare i Kotlin compareTo obliczają to samo. W standardowej bibliotece Haskell funkcja porównywania trójstronnego comparejest zdefiniowana dla wszystkich typów w Ord klasie ; zwraca typ Ordering, którego wartości są LT(mniejsze niż), EQ(równe) i GT(większe niż):
data Ordering = LT | EQ | GT
Wiele języków zorientowanych obiektowo ma metodę porównywania trójstronnego , która wykonuje trójstronne porównanie między obiektem a innym danym obiektem. Na przykład w Javie każda klasa implementująca Comparableinterfejs ma compareTometodę, która albo zwraca ujemną liczbę całkowitą, zero lub dodatnią liczbę całkowitą, albo zwraca a NullPointerException(jeśli jeden lub oba obiekty są null). Podobnie w .NET Framework każda klasa implementująca IComparableinterfejs ma taką CompareTometodę.
Od wersji Java 1.5 to samo można obliczyć za pomocą Math.signummetody statycznej, jeśli różnica może być znana bez problemów obliczeniowych, takich jak przepełnienie arytmetyczne, o którym mowa poniżej. Wiele języków komputerowych pozwala na definicję funkcji, dzięki czemu porównanie(A,B) może być odpowiednio opracowane, ale pytanie brzmi, czy jego wewnętrzna definicja może wykorzystywać jakiś rodzaj składni trójdrożnej, czy też musi opierać się na powtarzanych testach.
Podczas wdrażania porównania trójczynnikowego, gdy operator lub metoda porównania trójczynnikowego nie są jeszcze dostępne, często łączy się dwa porównania, takie jak A = B i A < B lub A < B i A > B. Zasadniczo kompilator może wywnioskować, że te dwa wyrażenia można zastąpić tylko jednym porównaniem, po którym następuje wiele testów wyniku, ale wzmianki o tej optymalizacji nie można znaleźć w tekstach na ten temat.
W niektórych przypadkach porównanie trójczynnikowe można zasymulować, odejmując A i B i badając znak wyniku, wykorzystując specjalne instrukcje do badania znaku liczby. Wymaga to jednak, aby typ A i B miał dobrze określoną różnicę. Liczby całkowite ze znakiem o stałej szerokości mogą się przepełnić, gdy są odejmowane, liczby zmiennoprzecinkowe mają wartość NaN z niezdefiniowanym znakiem, a ciągi znaków nie mają funkcji różnicowej odpowiadającej ich całkowitej kolejności. Na poziomie maszyny przepełnienie jest zwykle śledzone i może być używane do określenia kolejności po odjęciu, ale informacje te nie są zwykle dostępne dla języków wyższego poziomu.
W jednym przypadku trójczynnikowego warunkowego dostarczonego przez język programowania, obecnie przestarzała trójstronna arytmetyczna instrukcja IF w Fortran uwzględnia znak wyrażenia arytmetycznego i oferuje trzy etykiety, do których można przeskoczyć zgodnie ze znakiem wyniku:
IF (expression) negative,zero,positive
Wspólna funkcja biblioteczna strcmp w C i językach pokrewnych jest trójstronnym leksykograficznym porównaniem ciągów; jednak w tych językach brakuje ogólnego, trójstronnego porównania innych typów danych.
Operator statku kosmicznego
Operator porównania trójstronnego dla liczb jest oznaczony jak <=>w Perl , Ruby , Apache Groovy , PHP , Eclipse Ceylon i C++ , i jest nazywany operatorem statku kosmicznego .
Pochodzenie nazwy wynika z tego, że przypomina Randalowi L. Schwartzowi statek kosmiczny w grze HP BASIC Star Trek . Innym koder zasugerował, że została tak nazwana, ponieważ wyglądał podobnie do Dartha Vadera TIE Fighter w Star Wars Saga.
Przykład w PHP:
echo 1 <=> 1; // 0
echo 1 <=> 2; // -1
echo 2 <=> 1; // 1
Złożone typy danych
Porównania trójczynnikowe mają właściwość łatwego komponowania i tworzenia porównań leksykograficznych typów danych innych niż pierwotne, w przeciwieństwie do porównań dwukierunkowych.
Oto przykład kompozycji w Perlu.
sub compare($$) {
my ($a, $b) = @_;
return $a->{unit} cmp $b->{unit}
|| $a->{rank} <=> $b->{rank}
|| $a->{name} cmp $b->{name};
}
Zauważ, że cmp, w Perlu, jest dla łańcuchów, ponieważ <=>jest dla liczb. Odpowiedniki dwukierunkowe są zwykle mniej zwarte, ale niekoniecznie mniej czytelne. Powyższy wykorzystuje oceny zwarcia z ||operatorem, a fakt, że jest uważany za fałszywy 0 w Perlu. W rezultacie, jeśli pierwsze porównanie jest równe (w ten sposób wylicza 0), „przejdzie” do drugiego porównania i tak dalej, aż znajdzie takie, które jest niezerowe, lub dotrze do końca.
W niektórych językach, takich jak Python , Ruby , Haskell , itp., porównywanie list odbywa się leksykograficznie, co oznacza, że możliwe jest zbudowanie łańcucha porównań, jak w powyższym przykładzie, poprzez umieszczenie wartości na listach w żądanej kolejności; na przykład w Rubim:
[a.unit, a.rank, a.name] <=> [b.unit, b.rank, b.name]