In-place swap je technika, pomocí níž můžeme prohodit obsah dvou různých proměnných stejného typu, aniž by bylo nutné vytvořit novou pomocnou proměnnou.

XOR swap

Nejobvyklejší implementací je využití bitové operace XOR, respektive její vlastnosti (A \\oplus B) \\oplus A = B. Celé prohazovací schéma vypadá pro proměnné a a b následovně:


\\begin{array}{l|l}
        Operace & Význam \\\\
        \\hline
        a = a \\oplus b & a = A \\oplus B\\\\
        b = b \\oplus a & b = B \\oplus ( A \\oplus B ) = A \\\\
        a = a \\oplus b & a = ( A \\oplus B ) \\oplus A = B
\\end{array}

Kód

/**
 * In-place swap pomoci operace XOR
 */
void xorSwap(int *a, int *b) {
    if (a != b) {
        *a ^= *b; // a = A XOR B
        *b ^= *a; // b = B XOR ( A XOR B ) = A 
        *a ^= *b; // a = ( A XOR B ) XOR A = B
    }
}

V případě XOR swapu je zapotřebí nejprve ošetřit situaci, kdy předané proměnné ukazují na stejné místo paměti. Pokud by tomu tak bylo a neošetřili bychom tuto situaci, tak by algoritmus obě proměnné vynuloval již v prvním kroku schématu.

Add swap

Druhou obvyklou implementací in-place swapu je nahrazení XORu operacemi sčítání a odčítání (add swap). Technicky vzato lze místo XORu použít libovolnou jinou reverzibilní binární operaci.


\\begin{array}{l|l}
        Operace & Význam \\\\
        \\hline
        a = a + b & a = A + B\\\\
        b = a - b & b = A + B - B = A \\\\
        a = a - b & a = A + B - A = B 
\\end{array}

Kód

/**
 * In-place swap pomoci scitani a odcitani
 */
void addSwap(int *a, int *b) {
    if(a != b){
        *a = *a + *b; // a = A + B
        *b = *a - *b; // b = A + B - B = A
        *a = *a - *b; // a = A + B - A = B  
    }
}

/**
 * Add Swap - vymena dvou celociselnych promenych bez vytvoreni treti pomocne promenne
 * @param $a
 * @param $b
 * @author Thomas (www.adamjak.net)
 */

function add_swap($a, $b) {
    $a = $a + $b;
    $b = $a - $b;
    $a = $a - $b;
    
}

Add swap nelze použít v případech (jazycích), ve kterých přetečení sčítaného typu způsobí chybu. Naopak vše proběhne v pořádku, pokud se případné přetečení vyřeší pomocí modulární aritmetiky (např. sečtení dvou velkých kladných čísel skončí v záporných číslech) nebo pokud má daný číselný typ neomezený počet cifer.

Nevýhody in-place swapu

Prostor pro použití in-place swapu je v dnešní době velmi omezený. Prvním důvodem je, že moderní překladače umí kód využívající pomocnou proměnnou optimalizovat tak, aby byl paměťově stejně náročný jako in-place swap, ale proběhl rychleji. Zadruhé si také procesory umí s konvenčním přístupem poradit lépe. Zatřetí lze prohazovat pouze objekty stejné délky (případně samotné ukazatele na ně). Poslední nevýhodou je nízká čitelnost tohoto algoritmu.

Litaratura

  • XOR swap algorithm. In Wikipedia : the free encyclopedia [online]. St. Petersburg (Florida) : Wikipedia Foundation, 9 March 2009, last modified on 13 December 2010 [cit. 2010-12-14]. Dostupné z WWW: <http://en.wikipedia.org/wiki/XOR_swap_algorithm>.

SEO od společnosti Digital Pylon


Online casino s algoritmem

České casino online online slot-vegas.cz

Hrajte nejlepší hry jako je GoodGame Empire.





Zajímavé články: Jak najít práci snů? Zvolte kariéru v IT!, Češi mají rádi hrací automaty online, Jak funguje algoritmické obchodování Casino, Online výuka Algoritmus a online marketing mají svá pravidla, Automaty, Matematický vliv, Ratings, Jak fungují algoritmy hazardních her online: více znalostí, více peněz, SYPWAI - nástroj pro vědecký vývoj, Vynikají na globálním trhu: Nejlepší vývojáři softwaru pro online výherní automaty, Jak si vybrat nejlepší české online casino, Proč byste měli hrát online casino VPN revoluce, Kde najdeme algoritmy v každodenním životě?, Čeká vás pracovní pohovor mimo město? Podívejte se, jak dokonale zvládnout včasný příchod, 5 úžasných technologií ze světa hazardních her, Mirror and access to Mostbet, Svou kancelář můžete mít stále po ruce, Jaké výhody má digitalizovaná firma oproti off-line konkurenci?, Jaký systém vybrat pro snadné řízení výroby?, Nahradí umělá inteligence ajťáky?, Důvody, proč používat SnapTik ke stahování videí TikTok, Dokonalý den na pláži: Co si vzít s sebou, aby byl výlet zábavný a bezpečný?, Jak přežít dlouhý let?, Go pay GoodGame Empire, Blockchain, Rozhovor


Doporučujeme

Internet pro vaši firmu na míru

https://www.algoritmy.net