Трехстороннее сравнение
В информатике трехстороннее сравнение берет два значения A и B, принадлежащие к типу с общим порядком , и определяет, является ли A < B, A = B или A > B за одну операцию в соответствии с математическим законом трихотомия .
Его можно реализовать в виде функции (например, strcmp в C ), метод (например, compareTo в Java ) или оператор (например, оператор космического корабля <=> в Perl , PHP и C++ ).
Вычисления на машинном уровне
[ редактировать ]Многие процессоры имеют наборы команд , поддерживающие такую операцию с примитивными типами. Некоторые машины имеют целые числа со знаком , основанные на представлении знака и величины или дополнении до единиц (см. Представления чисел со знаком ), оба из которых допускают дифференцированный положительный и отрицательный ноль . Это не нарушает трихотомию, пока принят последовательный общий порядок: допустимо либо −0 = +0, либо −0 < +0. Однако у распространенных типов с плавающей запятой есть исключение из трихотомии: существует специальное значение «NaN» ( не число ), такое что x < NaN, x > NaN и x = NaN являются ложными для всех значений с плавающей запятой x. (включая сам NaN).
Языки высокого уровня
[ редактировать ]Способности
[ редактировать ]В C функции strcmp и memcmp выполнить трехстороннее сравнение между строками и буферами памяти соответственно. Они возвращают отрицательное число, если первый аргумент лексикографически меньше второго, ноль, если аргументы равны, и положительное число в противном случае. Это соглашение о возврате «знака разницы» распространяется на произвольные функции сравнения с помощью стандартной функции сортировки. qsort, который принимает функцию сравнения в качестве аргумента и требует ее соблюдения.
В Perl (только для числовых сравнений cmp используется для лексического сравнения строк), PHP (начиная с версии 7), Ruby и Apache Groovy , «оператор космического корабля». <=> возвращает значения -1, 0 или 1 в зависимости от того, A < B, A = B или A > B соответственно. Питон 2.x cmp(удалено в версии 3.x), OCaml compareи Котлин compareTo функции вычисляют одно и то же. В Haskell стандартной библиотеке функция трехстороннего сравнения compare определяется для всех типов в Ord сорт ; он возвращает тип Ordering, чьи значения LT (меньше, чем), EQ (равный), и GT (больше чем): [1]
data Ordering = LT | EQ | GT
Многие объектно-ориентированные языки программирования трехстороннего сравнения имеют функцию , которая выполняет трехстороннее сравнение между объектом и другим заданным объектом. Например, в Java любой класс, реализующий Comparable интерфейс имеет compareTo метод, который либо возвращает отрицательное целое число, ноль или положительное целое число, либо выдает NullPointerException (если один или оба объекта null). Аналогично, в платформе .NET любой класс, реализующий IComparable интерфейс имеет такой CompareTo метод. В C++ любой класс, допускающий трехстороннее сравнение, может быть параметром экземпляров std::compare_three_way, std::strong_order, std::weak_order, или std::partial_order.
Начиная с версии Java 1.5, то же самое можно вычислить с помощью Math.signum статический метод, если разницу можно узнать без вычислительных проблем, таких как арифметическое переполнение, упомянутое ниже. Многие компьютерные языки допускают определение функций, поэтому сравнение (A,B) может быть разработано соответствующим образом, но вопрос в том, может ли его внутреннее определение использовать какой-то трехсторонний синтаксис или же оно должно прибегать к повторным тестам.
При реализации трехстороннего сравнения, где оператор или метод трехстороннего сравнения еще не доступен, обычно объединяют два сравнения, например A = B и A < B или A < B и A > B. В принципе , компилятор мог бы прийти к выводу, что эти два выражения можно заменить только одним сравнением с последующей многократной проверкой результата, но упоминания об этой оптимизации нельзя найти в текстах по этой теме.
В некоторых случаях трехстороннее сравнение можно смоделировать путем вычитания A и B и проверки знака результата, используя специальные инструкции для проверки знака числа. Однако для этого требуется, чтобы типы A и B имели четко выраженную разницу. Целые числа со знаком фиксированной ширины могут переполняться при вычитании, числа с плавающей запятой имеют значение NaN с неопределенным знаком, а строки символов не имеют разностной функции, соответствующей их общему порядку. На машинном уровне переполнение обычно отслеживается и может использоваться для определения порядка после вычитания, но эта информация обычно недоступна для языков более высокого уровня.
В одном случае трехстороннего условного выражения, предоставляемого языком программирования, в Фортране ныне устаревший трехсторонний арифметический оператор IF учитывает знак арифметического выражения и предлагает три метки для перехода в соответствии со знаком результата:
IF (expression) negative,zero,positive
Общая библиотечная функция strcmp в C и родственных языках представляет собой трехстороннее лексикографическое сравнение строк; однако в этих языках отсутствует общее трехстороннее сравнение других типов данных.
Оператор космического корабля
[ редактировать ]Оператор трехстороннего сравнения или «оператор космического корабля» для чисел обозначается как <=> в Perl , Ruby , Apache Groovy , PHP , Eclipse Ceylon и C++ и называется оператором космического корабля . [2]
В C++ версия C++20 добавляет оператор космического корабля <=>, которое возвращает значение, определяющее, равны ли два значения, меньше, больше или неупорядочены, и может возвращать разные типы в зависимости от строгости сравнения. [3]
Происхождение названия связано с тем, что оно напоминает Рэндалу Л. Шварцу космический корабль из игры HP BASIC Star Trek . [4] Другой программист предположил, что он был назван так потому, что был похож на СИД-истребитель Дарта Вейдера из саги «Звездные войны» . [5]
Пример на PHP:
echo 1 <=> 1; // 0
echo 1 <=> 2; // -1
echo 2 <=> 1; // 1
Пример на С++:
1 <=> 1; // evaluates to std::strong_ordering::equal
1 <=> 2; // evaluates to std::strong_ordering::less
2 <=> 1; // evaluates to std::strong_ordering::greater
Составные типы данных
[ редактировать ]Трехсторонние сравнения имеют свойство легко составлять и строить лексикографические сравнения непримитивных типов данных, в отличие от двусторонних сравнений.
Вот пример композиции в Perl.
sub compare($$) {
my ($a, $b) = @_;
return $a->{unit} cmp $b->{unit}
|| $a->{rank} <=> $b->{rank}
|| $a->{name} cmp $b->{name};
}
Обратите внимание, что cmpв Perl предназначен для строк, поскольку <=> это для цифр. Двусторонние эквиваленты обычно менее компактны, но не обязательно менее разборчивы. Вышеупомянутое использует преимущества оценки короткого замыкания || оператор и тот факт, что 0 считается ложным в Perl. В результате, если первое сравнение равно (т. е. оценивается как 0), оно «провалится» ко второму сравнению и так далее, пока не будет найдено ненулевое сравнение или пока оно не достигнет конца.
В некоторых языках, включая Python , Ruby , Haskell и т. д., сравнение списков выполняется лексикографически, что означает, что можно построить цепочку сравнений, как в приведенном выше примере, помещая значения в списки в желаемом порядке; например, в Руби:
[a.unit, a.rank, a.name] <=> [b.unit, b.rank, b.name]
В С++:
std::tie(a.unit, a.rank, a.name) <=> std::tie(b.unit, b.rank, b.name)
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Данные.Слово
- ^ «Математика::Комплекс» . Документация по программированию на Perl . Проверено 26 сентября 2014 г.
- ^ Херб Саттер предложил добавить в стандарт C++ оператор трехстороннего сравнения с помощью
<=>синтаксис в статье под названием «Последовательное сравнение». См. «Последовательное сравнение». Он был успешно объединен с черновиком C++20 в ноябре 2017 года. - ^ «История космического корабля (было Re: [dart-misc] протоколы заседания DEP)» .
- ^ «Оператор суперкосмического корабля» . 08.12.2000 . Проверено 6 августа 2014 г.