Трехстороннее сравнение - Three-way comparison

В Информатика, а трехстороннее сравнение принимает два значения A и B, принадлежащих типу с общий заказ и определяет, является ли A B за одну операцию, в соответствии с математическим закон трихотомии.

Вычисление на уровне машины

Многие процессоры имеют наборы инструкций которые поддерживают такую ​​операцию с примитивными типами. некоторые машины подписали целые числа основанный на знаке и величине или дополнительном представлении (см. представление числа со знаком ), оба из которых позволяют дифференцировать положительные и отрицательные нуль. Это не нарушает трихотомию до тех пор, пока принят согласованный общий порядок: допустимо либо -0 = +0, либо -0 <+0. Общие плавающая точка типы, однако, имеют исключение для трихотомии: существует специальное значение "NaN" (Не число ) такие, что Икс Икс > NaN и Икс = NaN все ложны для всех значений с плавающей запятой Икс (включая сам NaN).

Языки высокого уровня

Возможности

В C, функции strcmp и memcmp выполнить трехстороннее сравнение между строками и буферами памяти соответственно. Они возвращают отрицательное число, если первым аргументом является лексикографически меньше второго, ноль, если аргументы равны, и положительное число в противном случае. Это соглашение о возврате «знака различия» распространяется на произвольные функции сравнения стандартной функцией сортировки. qsort, который принимает функцию сравнения как аргумент и требует, чтобы он его соблюдал.

В C ++, то C ++ 20 доработка добавляет "оператор космического корабля" <=>, который аналогичным образом возвращает знак различия, а также может возвращать различные типы (конвертируемые в целые числа со знаком) в зависимости от строгости сравнения.^[1]

В Perl (только для числовых сравнений cmp используется для лексических сравнений строк), PHP (начиная с версии 7), Рубин, и Apache Groovy, "оператор космического корабля" <=> возвращает значения -1, 0 или 1 в зависимости от того, A B, соответственно. В Python 2.x cmp (удалено в 3.x), OCaml и Котлин, то cmp, сравнить и сравнить с функции вычисляют одно и то же соответственно. в Haskell стандартная библиотека, функция трехстороннего сравнения сравнить определен для всех типов в Ord класс; он возвращает тип Заказ, значения которого равны LT (меньше, чем), Эквалайзер (равно), и GT (лучше чем):^[2]

данные Заказ = LT | Эквалайзер | GT

Многие объектно-ориентированные языки имеют трехстороннее сравнение метод, который выполняет трехстороннее сравнение между объектом и другим заданным объектом. Например, в Ява, любой класс, реализующий Сопоставимый интерфейс имеет сравнить с метод, который либо возвращает отрицательное целое число, ноль или положительное целое число, либо выдает Исключение нулевого указателя (если один или оба объекта значение NULL). Точно так же в .NET Framework, любой класс, реализующий IComparable интерфейс имеет такой Сравнить с метод.

Начиная с версии Java 1.5, то же самое можно вычислить с помощью Math.signum статический метод, если разница может быть известна без вычислительных проблем, таких как арифметическое переполнение упомянуто ниже. Многие компьютерные языки позволяют определять функции, поэтому сравнить (A, B) можно было бы соответствующим образом разработать, но вопрос в том, может ли его внутреннее определение использовать какой-то трехсторонний синтаксис или же оно должно прибегать к повторным тестам.

При реализации трехстороннего сравнения, когда оператор или метод трехстороннего сравнения еще не доступны, обычно объединяют два сравнения, например A = B и A B. , компилятор может сделать вывод, что эти два выражения могут быть заменены только одним сравнением, за которым следует несколько проверок результата, но упоминания об этой оптимизации нельзя найти в текстах по этой теме.

В некоторых случаях трехстороннее сравнение можно смоделировать, вычитая A и B и проверяя знак результата, используя специальные инструкции для проверки знака числа. Однако для этого требуется, чтобы типы A и B имели четко выраженную разницу. Целые числа фиксированной ширины со знаком могут переполняться при вычитании, числа с плавающей запятой имеют значение NaN с неопределенным знаком, а символьные строки не имеют функции разницы, соответствующей их общему порядку. На машинном уровне переполнение обычно отслеживается и может использоваться для определения порядка после вычитания, но эта информация обычно недоступна для языков более высокого уровня.

В одном случае трехходовой условный предоставляемый языком программирования, Фортран устаревший трехходовой арифметический IF Оператор рассматривает знак арифметического выражения и предлагает три метки для перехода в соответствии со знаком результата:

     ЕСЛИ (выражение) отрицательный,нуль,положительный

Функция общей библиотеки strcmp в C и родственные языки - трехстороннее лексикографическое сравнение строк; однако в этих языках отсутствует общее трехстороннее сравнение других типов данных.

«Оператор космического корабля»

Оператор трехстороннего сравнения чисел обозначается как <=> в Perl, Рубин, Apache Groovy, PHP, Затмение Цейлон, и C ++, и называется оператор космического корабля.^[3]

Происхождение названия связано с тем, что оно напоминает Рэндал Л. Шварц космического корабля в HP BASIC Звездный путь игра.^[4] Другой программист предположил, что он был назван так, потому что был похож на Дарта Вейдера TIE истребитель в Звездные войны сага.^[5]

Пример на PHP:

эхо 1 <=> 1; // 0эхо 1 <=> 2; // -1эхо 2 <=> 1; // 1

Составные типы данных

Трехсторонние сравнения имеют свойство легко составлять и строить лексикографический сравнения непримитивных типов данных, в отличие от двусторонних сравнений.

Вот пример композиции на Perl.

    суб сравнить($$) {        мой ($ а, $ млрд) = @_;        вернуть $ а->{единица измерения} cmp $ млрд->{единица измерения}            || $ а->{классифицировать} <=> $ млрд->{классифицировать}            || $ а->{имя} cmp $ млрд->{имя};    }

Обратите внимание, что cmpв Perl - для строк, так как <=> для чисел. Двусторонние эквиваленты обычно менее компактны, но не обязательно менее разборчивы. Вышеуказанное использует преимущества оценка короткого замыкания из || оператор, и тот факт, что 0 считается ложным в Perl. В результате, если первое сравнение равно (таким образом, оценивается как 0), оно «провалится» до второго сравнения и так далее, пока не найдет одно, отличное от нуля, или пока не достигнет конца.

На некоторых языках, в том числе Python, Рубин, Haskell и т.д. сравнение списков выполняется лексикографически, что означает, что можно построить цепочку сравнений, как в приведенном выше примере, помещая значения в списки в желаемом порядке; например, в Ruby:

[а.единица измерения, а.классифицировать, а.имя] <=> [б.единица измерения, б.классифицировать, б.имя]

Смотрите также

• strcmp

использованная литература