Trevägsjämförelse
Inom datavetenskap tar en trevägsjämförelse två värden A och B som tillhör en typ med en total ordning och avgör om A < B, A = B eller A > B i en enda operation, i enlighet med den matematiska lagen för trikotomi .
Beräkning på maskinnivå
Många processorer har instruktionsuppsättningar som stödjer en sådan operation på primitiva typer. Vissa maskiner har förtecknade heltal baserat på en tecken-och-storlek eller ens komplementrepresentation (se representationer av tecken med tecken ), som båda tillåter en differentierad positiv och negativ nolla . Detta bryter inte mot trikotomi så länge som en konsekvent total ordning antas: antingen −0 = +0 eller −0 < +0 är giltigt. Vanliga flyttalstyper har dock ett undantag från trikotomi: det finns ett speciellt värde "NaN" ( Not a Number ) så att x < NaN, x > NaN och x = NaN alla är falska för alla flyttalsvärden x (inklusive själva NaN).
Språk på hög nivå
Förmågor
I C utför funktionerna strcmp och memcmp en trevägsjämförelse mellan strängar respektive minnesbuffertar. De returnerar ett negativt tal när det första argumentet är lexikografiskt mindre än det andra, noll när argumenten är lika, och ett positivt tal annars. Denna konvention att returnera "skillnadens tecken" utökas till godtyckliga jämförelsefunktioner av standardsorteringsfunktionen qsort , som tar en jämförelsefunktion som ett argument och kräver att den följer den.
I C++ lägger C ++20 -revisionen till " rymdskeppsoperatorn " <=> , som på samma sätt returnerar tecknet på skillnaden och kan också returnera olika typer (som kan konverteras till tecken med heltal) beroende på hur strikt jämförelsen är.
I Perl (endast för numeriska jämförelser, cmp- operatorn används för stränglexikaliska jämförelser), PHP (sedan version 7), Ruby och Apache Groovy , returnerar "rymdskeppsoperatorn" <=> värdena −1, 0 eller 1 beroende på om A < B, A = B respektive A > B. Funktionerna Python 2.x cmp (borttaget i 3.x), OCaml compare och Kotlin compareTo beräknar samma sak. I Haskells standardbibliotek är trevägsjämförelsefunktionen compare definierad för alla typer i klassen Ord ; den returnerar typen Ordering , vars värden är LT (mindre än), EQ (lika) och GT (större än):
databeställning = LT | _ EQ | GT
Många objektorienterade språk har en trevägsjämförelsemetod , som utför en trevägsjämförelse mellan objektet och ett annat givet objekt. Till exempel, i Java har alla klasser som implementerar Comparable- gränssnittet en compareTo- metod som antingen returnerar ett negativt heltal, noll eller ett positivt heltal, eller kastar ett NullPointerException (om ett eller båda objekten är null ). På liknande sätt, i .NET Framework , har alla klasser som implementerar IComparable- gränssnittet en sådan CompareTo- metod.
Sedan Java version 1.5 kan densamma beräknas med den statiska metoden Math.signum om skillnaden kan vara känd utan beräkningsproblem såsom aritmetiskt spill som nämns nedan. Många datorspråk tillåter definition av funktioner så att en jämförelse(A,B) kan utformas på lämpligt sätt, men frågan är om dess interna definition kan använda någon sorts trevägssyntax eller inte måste falla tillbaka på upprepade tester.
Vid implementering av en trevägsjämförelse där en trevägsjämförelseoperator eller metod inte redan finns tillgänglig är det vanligt att kombinera två jämförelser, såsom A = B och A < B, eller A < B och A > B. I princip , kan en kompilator dra slutsatsen att dessa två uttryck kan ersättas av endast en jämförelse följt av flera tester av resultatet, men omnämnandet av denna optimering finns inte i texter om ämnet.
I vissa fall kan trevägsjämförelse simuleras genom att subtrahera A och B och undersöka resultatets tecken, med hjälp av speciella instruktioner för att undersöka tecknet för ett tal. Detta kräver dock att typen av A och B har en väldefinierad skillnad. Signerade heltal med fast bredd kan svämma över när de subtraheras, flyttalstal har värdet NaN med odefinierat tecken, och teckensträngar har ingen skillnadsfunktion som motsvarar deras totala ordning. På maskinnivå spåras overflow vanligtvis och kan användas för att bestämma ordning efter subtraktion, men denna information är vanligtvis inte tillgänglig för språk på högre nivå.
I ett fall av trevägsvillkor som tillhandahålls av programmeringsspråket, tar Fortrans nu utfasade trevägsarithmetiska IF - sats tecknet på ett aritmetiskt uttryck och erbjuder tre etiketter att hoppa till enligt resultatets tecken:
OM ( uttryck ) negativ , noll , positiv
Den vanliga biblioteksfunktionen strcmp i C och relaterade språk är en trevägs lexikografisk jämförelse av strängar; dessa språk saknar dock en generell trevägsjämförelse av andra datatyper.
Rymdskeppsoperatör
Trevägsjämförelseoperatorn för siffror betecknas som <=> i Perl , Ruby , Apache Groovy , PHP , Eclipse Ceylon och C++ och kallas rymdskeppsoperatören .
Namnets ursprung beror på att det påminner Randal L. Schwartz om rymdskeppet i ett HP BASIC Star Trek- spel. En annan kodare har föreslagit att den hette så eftersom den liknade Darth Vaders TIE-fighter i Star Wars- sagan.
Exempel i PHP:
eko 1 <=> 1 ; // 0 eko 1 <=> 2 ; // -1 eko 2 <=> 1 ; // 1
Sammansatta datatyper
Trevägsjämförelser har egenskapen att vara lätta att komponera och bygga lexikografiska jämförelser av icke-primitiva datatyper, till skillnad från tvåvägsjämförelser.
Här är ett kompositionsexempel i Perl.
sub compare ($$) { my ( $a , $b ) = @_ ; returnera $a -> { enhet } cmp $b -> { enhet } || $a -> { rank } <=> $b -> { rank } || $a -> { namn } cmp $b -> { namn }; }
Observera att cmp , i Perl, är för strängar, eftersom <=> är för siffror. Tvåvägsekvivalenter tenderar att vara mindre kompakta men inte nödvändigtvis mindre läsbara. Ovanstående drar fördel av kortslutningsutvärdering av || operatorn och det faktum att 0 anses vara falsk i Perl. Som ett resultat, om den första jämförelsen är lika (därmed utvärderas till 0), kommer den att "falla igenom" till den andra jämförelsen, och så vidare, tills den hittar en som inte är noll, eller tills den når slutet.
I vissa språk, inklusive Python , Ruby , Haskell , etc., görs jämförelse av listor lexikografiskt, vilket innebär att det är möjligt att bygga en kedja av jämförelser som exemplet ovan genom att placera värdena i listor i önskad ordning; till exempel i Ruby:
[ a . enhet , en . rang , en . namn ] <=> [ b . enhet , b . rang , b . namn ]