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 . Celé prohazovací schéma vypadá pro proměnné
a
následovně:
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.
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>.