W idealnym świecie transakcja wymiany powinna zapewnić obopólną satysfakcję. Niestety nie zawsze tak się dzieje, szczególnie jeśli trafi się na mistrza biznesu, który tak szybko jak się pojawił, tak szybko znika, a my pozostajemy z pustymi rękami. Dzisiejszy wpis będzie namiastką tego idealnego świata, bowiem zajmiemy się zjawiskiem zamiany dwóch zmiennych, a żeby nie być posądzonym o paserstwo, zrobimy to z wykorzystaniem tylko i wyłącznie tychże dwóch.
Trio z Rio.
Standardowo i dosyć często, aby zamienić dwie zmienne wykorzystuje się trzecią, tzw. zmienną tymczasową. W pseudokodzie wygląda to tak:
a = 1
b = 2
tmp = a
a = b
b = tmp
Aby nie nadpisać zmiennej a, jej wartość została tymczasowo przechowana w zmiennej tmp. A kiedy już jest nam potrzebna, przepisujemy do zmiennej b. Kiedy popatrzymy na ten kod wydaje się niemożliwe nieużywanie trzeciej zmiennej, bo przecież jeśli przepiszemy wartość b do a, to stracimy wartość b. Niezły klin, co?
Czego oczy nie widzą...
Jest jednak kilka sposobów na podziękowanie trzeciemu koledze. Zaczniemy od metody, która "pod spodem", czyli na najniższej warstwie implementacji bardzo prawdopodobne, że używa nie tylko jednej dodatkowej zmiennej, ale kilku. Jednak na wysokim poziomie, czyli tym, którego my używamy, wcale tego nie widać.
Wraz z pojawieniem się ECMAScript 6, dostaliśmy w JavaScript możliwość destrukturyzacji obiektów i tablic. W tym momencie należy odrzucić destrukcyjne myśli, bo destrukturyzacja i destrukcja, to dwa inne pojęcia. Niczego nie niszczymy, ale wyodrębniamy, czy też mówiąc kolokwialnie, wyciągamy informacje z określonej struktury. Wyciągamy tylko to co chcemy, pomimo, że nazwa tego procesu sugerowałaby rozczłonkowanie całej struktury na drobne elementy.
Destrukturyzację w kodzie zapisujemy podobnie do deklaracji obiektu, ale robimy to po stronie deklaracji zmiennej. Zacznijmy od destrukturyzacji obiektu:
let obiekt = {
zmienna1: "wartosc_1",
zmienna2: "wartosc_2"
}
let {zmienna1, zmienna2} = obiekt;
Ten drugi fragment to właśnie destrukturyzacja. Tu nastąpiła pełna, bo obiekt ma dwie zmienne i tyle samo wyodrębniliśmy. Nazwy zmiennych odpowiadają właściwościom obiektu. Jeśli zadeklarowalibyśmy zmienną nieistniejącą w obiekcie, po prostu będzie ona niezdefiniowana.
Analogicznie można postąpić z tablicą:
let tablica = [1, 2];
let [a, b] = tablica;
Tu jest o tyle fajniej, że zmienne dla destrukturyzacji wcale nie nawiązują do indeksów tablicy - możemy nazwać je dowolnie. W powyższym kodzie otrzymamy zmienną a o wartość 1 oraz zmienną b o wartości 2. Zmieńmy trochę ten kod:
let a = 1;
let b = 2;
let tablica = [b, a];
let [a, b] = tablica;
Na podstawie zmiennych a i b, tworzymym tablicę o wartości [2, 1]. Następnie używając destrukturyzację, wyciągamy kolejne wartości z tablicy do tych samych zmiennych, których użyliśmy do utworzenia tablicy. Jakie będą mieć teraz wartości? To już chyba wiesz!
No ale używamy jednak trzecią zmienną (tablica). Zauważ jednak, że tablicę możemy zdefiniować ad hoc - jako anonimową:
let a = 1;
let b = 2;
let [a, b] = [b, a];
Tym sposobem uniknęliśymy użycia trzeciej zmiennej.
Dzisiejszy wpis nawiązuje również do backendowej strony programowania i tu pewnie dla wielu z Was wyniknie zaskoczenie. W PHP od wersji 4 mamy możliwość destrukturyzacji tablic. Niektórzy pewnie jej używali nie mając świadomości, że to robią. A służy temu funkcja list.
$a = 1;
$b = 2;
list($a, $b) = [$b, $a];
Analogicznie do trzeciego przykładu JS, tu również tworzymy anonimową tablicę ze zmiennych, a list w błyskawiczny sposób wyłuska z niej wartości do tychże samych zmiennych.
Podróż do (kontra)Walencji.
Choć to rozwiązanie zwane jest też alternatywą wykluczającą, absolutnie nie wykluczymy go z branych pod uwagę możliwości rozwiązania tytułowego problemu. Być może znasz je również pod nazwą XOR. Być może niekoniecznie z płaszczyzny programowania, ale obiło Ci się o uszy podczas rozmów o elektronice. XOR jest funkcją boolowską dwuargumentową (podobnie jak OR czy AND), co oznacza, że musimy jej dostarczyć dwie wartości: prawda i fałsz lub po prostu 1 i 0, a w wyniku otrzymamy odpowiednio prawda/fałsz lub 0/1. Ponieważ jak wiemy w tematyce komputerowej wszystko opiera się na liczbach binarnych, a te składają się właśnie z zer i jedynek, to możemy tu wykorzystać tą funkcję. Najpierw jednak zacznijmy od przykładu jej działania, czyli tzw. tablicy prawdy:
| a | b | f |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Wartość 0 otrzymujemy kiedy bity są takie same, a 1 kiedy różnią się.
I po tym obszernym wykładzie możemy przystąpić do omówienia zamiany dwóch zmiennych z wykorzystaniem tej metody, czyli tzw. metody XOR swap. Aby zamienić dwie zmienne musimy przeprowadzić trzykrotną operację XOR pomiędzy nimi:
a = a XOR b
b = a XOR b
a = a XOR b
Dziwnie to wygląda, ale jeśli nie wierzysz, że działa, to sprawdźmy na przykładowych liczbach wykorzystując tablicę prawdy. Weźmy liczby 9 oraz 15. W zapisie binarnym mają postać:
| 1 | 0 | 0 | 1 |
oraz
| 1 | 1 | 1 | 1 |
Wykonajmy pierwszy krok:
| a | 1 | 0 | 0 | 1 |
| b | 1 | 1 | 1 | 1 |
| XOR | 0 | 1 | 1 | 0 |
Otrzymujemy 6 (bity o wartości 2 oraz 4) i tą wartość przypisujemy a. Zróbmy drugi krok:
| a | 0 | 1 | 1 | 0 |
| b | 1 | 1 | 1 | 1 |
| XOR | 1 | 0 | 0 | 1 |
Otrzymujemy... 9! I to jest wartość dla b.
I ostatni krok:
| a | 0 | 1 | 1 | 0 |
| b | 1 | 0 | 0 | 1 |
| XOR | 1 | 1 | 1 | 1 |
Tak, tak, otrzymaliśmy 15 i przypisujemy tą wartość do b. Tym sposobem a=15, b=9.
Trzeba wziąć pod uwagę, że metoda nadaje się głównie do zamiany liczb całkowitych, w innym przypadku możemy otrzymać nieoczekiwany wynik. Choć nie zawsze, bo zależy to od sposobu przechowywanie liczb w pamięci przez interpreter/kompilator.
JS:
let a = 9;
let b = 15;
a = a ^ b;
b = a ^ b;
a = a ^ b;
PHP:
$a = 9;
$b = 15;
$a = $a ^ $b;
$b = $a ^ $b;
$a = $a ^ $b;
Podstawiając w obydwu przypadkach liczby zmiennoprzecinkowe otrzymamy zamienione zmienne, ale już bez wartości dziesiętnych. Prawdopodobnie przed operacją XOR zachodzi rzutowanie zmiennych do całkowitych. Jeśli rzutowanie by nie zachodziło i obydwie zmienne byłyby przechowywane w ten sam sposób, tj. jako zwykłe zmienne lub jako wskaźniki oraz o tej samej długości binarnej, to również możliwa jest zamiana liczb z przecinkiem.
Co ciekawe w PHP możliwa jest również zamiana stringów. Z testów, które przeprowadziłem wynika, że operacja XOR jest dokonywana przez interpreter bezpośrednio na wartości takich zmiennych, a nie na wskaźnikach do nich. Ale są dwa warunki:
- stringi powinny posiadać tyle samo znaków, jeśli nie zawierają wielobajtowych znaków,
- stringi muszą mieć taką samą długość w bajtach, jesli zawierają znaki wielobajtowe, ale te nie muszą znaleźć się na identycznych pozycjach.
/* OK
*/
$a = "abc";
$b = "def";
/* OK, ale otrzymamy
$a = "de";
$b = "abc";
*/
$a = "abc";
$b = "de";
/* OK
*/
$a = "abć";
$b = "dęf";
/* Źle
*/
$a = "abć";
$b = "dę";
Modyfikacją XOR swap jest arytmetyczny swap wykorzystujący dodawanie oraz odejmowanie lub mnożenie wraz z dzieleniem:
a = a - b;
b = b + a;
a = b - a;
a = a * b;
b = a / b;
a = a / b;
Ten zadziała również na liczbach zmiennoprzecinkowych zarówno w JS jak i PHP, ale oczywiście nie zadziała na stringach.
Czyli co, nie zamieniasz się z nikim zamieniać i mogę oczekiwać Ciebie w następnym wpisie? Do przeczytania!
Przydatne linki:
Funkcja logiczna XOR.
XOR swap w Wikipedii.
Funkcja list w PHP.