17+ sposobów na zamianę wartości w dwóch zmiennych bez użycia trzeciej.

Jakiś czas temu natrafiłem na wpis, w którym padło pytanie o sposób zamiany wartości w dwóch zmiennych, bez użycia tymczasowej trzeciej. Zaczęło mnie to zastanawiać i zanim przeczytałem odpowiedź, starałem się sam na to pytanie odpowiedzieć (czego wyniki znajdują się poniżej). Dziś zatem mamy kolejny wpis z gatunku tych, które raczej nikomu do niczego się nie przydadzą, ale są ciekawe :)

O co chodzi

Zadaniem jest zamiana miejscami wartości w dwóch zmiennych, bez użycia trzeciej zmiennej. Pokażę to na przykładzie PHP.

Zazwyczaj, jeśli chcemy zamienić miejscami wartości w dwóch zmiennych robimy to mniej więcej tak:

<?php

$a = 100;
$b = 234;

echo "Przed:\na=$a\nb=$b\n";

$c = $a;
$a = $b;
$b = $c;

unset($c);

echo "Po:\na=$a\nb=$b\n";

Czego wynikiem jest:

# php 0.php
Przed:
a=100
b=234
Po:
a=234
b=100

Ale jak wykonać taką zamianę bez użycia trzeciej zmiennej? Odpowiedź jest bardzo prosta. A nawet odpowiedzi, bo jest na to kilkadziesiąt sposobów. Który z nich jest najlepszy? Na to pytanie też postaram się odpowiedzieć.

 

Sposoby na rozwiązanie zadania dla liczb

1. Operacje arytmetyczne – dodawanie

Pierwszym sposobem są proste operacje arytmetyczne przy użyciu dodawania i odejmowania (pamiętacie, ze odejmowanie, to też dodawanie, ale liczby ujemnej? ;) ).

<?php

$a = 100;
$b = 234;

echo "Przed:\na=$a\nb=$b\n";

$a = $a + $b;
$b = $a - $b;
$a = $a - $b;

echo "Po:\na=$a\nb=$b\n";

I wynik:

# php 1.php
Przed:
a=100
b=234
Po:
a=234
b=100

W dalszej części nie będę już przytaczał wyników za każdym razem, gdyż będą one takie same. :) Nie będę również wklejał pełnego kodu PHP, tylko najważniejszą część – reszta pozostaje bez zmian.

Zatem co tu się dzieje? Podzielmy to na 3 kolejne kroki z powyższego kodu:

krok  a    b
     100  234
 1   334  234  // a <= a + b
 2   334  100  // b <= a - b
 3   234  100  // a <= a - b

Najpierw do a przypisujemy sumę a i b:
a <= a + b = 100 + 234 = 334
Następnie do b przypisujemy równicę nowego a i b:
b <= a – b = 334 – 234 = 100
I w ostatnim kroku do a przypisujemy różnicę nowego a i b:
a <= a – b = 334 – 100 = 234

W ten sposób zamieniliśmy wartości obu zmiennych bez użycia dodatkowej zmiennej.

2. Operacje arytmetyczne – dodawanie (inaczej)

Można nieco zamieszać w zmiennych:

$a = $a - $b;
$b = $a + $b;
$a = $b - $a;

Takich zmian w zmiennych i operatorach plus i minus można by zrobić jeszcze więcej, ale z powodu podobieństwa i takiej samej zasady działania, nie będę ich przytaczał.

3. Operacje arytmetyczne – dodawanie (jednolinijkowiec)

Czas na przykład jednolinijkowca:

>$a = $b - $a + ($b = $a);

Dlaczego to działa? Jeżeli zerkniemy w priorytety operatorów w PHP, dowiemy się, że operator przypisania ma mniejszy priorytet od operatora dodawania, a gdy konkuruje ze sobą kilka operatorów o równej ważności, są one przetwarzane w odpowiedniej kolejności. Dla operatorów dodawania przetwarzanie następuje od lewej do prawej. Nawiasy służą wymuszeniu przypisania przed dodaniem. gdyby zatem w świetle tych reguł przejść krok po kroku, wyglądało by to mniej więcej tak:

$a = $b - $a + ($b = $a);
$a = 234 - 100 + ($b = $a);
$a = 134 + ($b = $a);
$a = 134 + ($b = 100); // tu następuje próba dodania zawartości
                       // nawiasu, wykonana zostaje operacja
                       // przypisania wartości 100 do $b
$a = 134 + 100;        // $b = 100
$a = 234;              // $b = 100

4. Operacje arytmetyczne – dodawanie (jednolinijkowiec #2)

Jednolinijkowca da się zapisać także w ten sposób:

$a -= $b += $a -= $b = -$b;

5. Operacje arytmetyczne – dodawanie (jednolinijkowiec #3)

A nawet w taki:

$b = ($a += $b -= $a) - $b;

6. Operacje arytmetyczne – mnożenie

Ta sama zasada ma zastosowanie także dla operacji mnożenia i dzielenia:

$a = $a * $b;
$b = $a / $b;
$a = $a / $b;

7. Operacje arytmetyczne – mnożenie (inaczej)

Tutaj też można nieco zamieszać:

$a = $a / $b;
$b = $a * $b;
$a = $b / $a;

I podobnie jak w przypadku dodawania i odejmowania – tu też można namnożyć jeszcze kilka rozwiązań działających na tej zasadzie.

8. Operacje arytmetyczne – mnożenie (jednolinijkowiec)

Czas na przykład jednolinijkowca:

$a = $b / $a * ($b = $a);

Jest on analogiczny jak w przypadku dodawania.

9. Operacje arytmetyczne – mnożenie (jednolinijkowiec #2)

Analogicznie jak w przypadku dodawania:

$a /= $b *= $a /= $b = 1/$b;

10. Operacje arytmetyczne – mnożenie (jednolinijkowiec #3)

I tutaj również… przez analogię do dodawania taka forma:

$b = ($a *= $b /= $a) / $b;

11. Operacje logiczne – XOR

Tu sytuacja jest podobna do dodawania i mnożenia, choć bardziej ciekawa:

$a = $a ^ $b;
$b = $a ^ $b;
$a = $a ^ $b;

Ten sposób też wymaga kilku słów wyjaśnienia. W powyższych przykładach operatory były używane parami – dodawanie i odejmowanie, mnożenie i dzielenie. Tu posługujemy się tylko XOR-em. XOR to inaczej alternatywa wykluczająca. Po więcej szczegółów odsyłam do materiałów zewnętrznych, np. Wikipedii. W naszym przypadku wystarczy tablica prawdy z której dowiadujemy się, że wynikiem XOR-a jest 0 jeśli obie liczby są takie same, lub 1 gdy są różne:

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

Wróćmy zatem do naszego przykładu – jak wyglądają operacje w kolejnych krokach:

krok      a         b
         100       234     (dziesiętnie)
      01100100  11101010   (binarnie)
 1    10001110  11101010 // a <= a ^ b = 01100100b ^ 11101010b
                                       = 10001110b = 142
 2    10001110  01100100 // b <= a ^ b = 10001110b ^ 11101010b
                                       = 01100100b = 100
 3    11101010  01100100 // a <= a ^ b = 10001110b ^ 01100100b
                                       = 11101010b = 234

12. Operacje logiczne – XOR (prościej)

Powyższy przykład da się zapisać prościej:

$a ^= $b;
$b ^= $b;
$a ^= $b;

Jest to możliwe dzięki konstrukcji języka – jeśli do zmiennej przypisujemy wartość będącą wynikiem działania na tej zmiennej i dowolnej innej, wolno nam skrócić zapis.

13. Operacje logiczne – XOR (jednolinijowiec)

Powyższe rozwiązanie da się skrócić do jednolinijkowca:

$a ^= $b ^= $a ^= $b;

Dlaczego to działa? Z prostej przyczyny. PHP przetwarza tą konstrukcję od prawej do lewej przypisując wartości do kolejnych zmiennych (mamy tam operatory przypisania) – jak wspominałem, gdy konkurują ze sobą operatory o równej ważności, przetwarzane są one kolejno – w przypadku dodawania było to od lewej do prawej, ale w przypadku operatorów przypisania kolejność jest odwrotna.

Kolejno wygląda to tak:

$a ^= $b ^= $a ^= $b;
$a ^= $b ^= ($a = $a ^ $b = 100 ^ 234);
$a ^= $b ^= ($a = 142); // do $a zostaje przypisana wartość 142
$a ^= $b ^= 142;
$a ^= ($b = $b ^ $a = 234 ^ 142);
$a ^= ($b = 100); // do $b zostaje przypisana wartość 100
$a ^= 100;
$a = $a ^ $b = 142 ^ 100;
$a = 234; // do $a zostaje przypisana wartość 234

14. Funkcje w PHP

W PHP do tego zadania można podejść w całkiem inny sposób:

list($b, $a) = array($a, $b);

W tym przypadku tworzona jest tablica z wartościami obu zmiennych, które ponownie są przypisywane do zmiennych w odwrotnej kolejności. Ten sposób wydaje się zużywać najwięcej pamięci, choć jest najbardziej czytelny ze wszystkich.

15. Operacje na ciągach

Zamienić dwie zmienne możemy także w taki sposób:

$b .= $a;
$a = (int)substr($b, 0, strlen($b) - strlen($a));
$b = (int)substr($b, -(strlen($b) - strlen($a)));

Najpierw łączymy obie zmienne w jeden ciąg – tu nastąpi zmiana typu z int na string, ponieważ wymusza to operator. Następnie już z długości obu ciągów reprezentujących liczby możemy wyliczyć ich oryginalne wartości. Cały czas jednak polegamy na ręcznym typowaniu (czyli ręcznej zmianie typów i elastyczności PHP w tym zakresie).

16. Operacje na tablicach

To jest jeszcze bardziej zakręcony sposób:

$b = array_merge(str_split($b), $a = str_split($a));
$a = (int)implode("", array_splice($b, 0, count($b) - count($a)));
$b = (int)implode("", $b);

Aby go bardziej zobrazować, rozbiję go na mniejsze kroki:

$a = str_split($a)
$b = str_split($b);
$b = array_merge($b, $a);
$a = array_splice($b, 0, count($b) - count($a));
$a = (int)implode("", $a);
$b = (int)implode("", $b);

Najpierw oba ciągi reprezentujące liczby są zamieniane na tablice w których każdy element zawiera jedną cyfrę, następnie tablice są łączone i z ilości elementów wybierane są elementy w odpowiedniej ilości. Na koniec elementy są ponownie łączone w ciągi i typowane na liczby. Tutaj też jest to możliwe dzięki elastyczności typowania w PHP.

17. Operacje na tablicach (prościej)

Da się to jednak zrealizować na tablicach o wiele prościej.

$b = array($a, $b);
$a = array_pop($b);
$b = array_pop($b);

Pomijam tutaj rożne wariacje tego rozwiązania, które działają tak samo.

 

Jeden słuszny sposób (czyli jednak nie działa)?

Powyżej znalazło się 17 różnych sposobów rozwiązania zadania, ale większość z nich niestety nie jest prawidłowa. Niektóre mogą być prawidłowe w innych językach programowania (np XOR w C), ale w przypadku PHP już nie. Postaram się zatem krótko streścić w czym problem (numery odpowiadają numerom powyższych rozwiązań):

1-5. Operacje dodawania w rożnych formach

Przed:
a=9.22337203685E+18   // pow(2,63)
b=4294967291          // pow(2,32) - 5
Po:
a=4294967296          // tutaj wartość jest nieprawidłowa
b=9.22337203685E+18

W tym przypadku jeśli używamy zbyt dużych liczb, tracimy najmniej znaczące części liczby, zatem operacje arytmetyczne tego typu tracą sens. Problem w tym, że dodanie tych dwóch liczb do siebie powoduje utratę najmniej znaczącego miejsca także w przypadku mniejszej liczby.

6-10. Operacje mnożenia w rożnych formach

W przypadku mnożenia, ten problem nie jest widoczny, choć ma miejsce. Dało by się to zauważyć, gdyby dokładniej przypatrzeć się liczbom. Występuje to za to o wiele poważniejszy problem:

Przed:
a=9.22337203685E+18   // pow(2,63)
b=0

Warning: Division by zero in /mnt/hgfs/www/test/swap/test.php
 on line 10

Warning: Division by zero in /mnt/hgfs/www/test/swap/test.php
 on line 11
Po:
a=
b=

Tak, to problem dzielenia przez zero.

11-13. XOR

Mogło by się wydawać, że przynajmniej XOR powinien działać prawidłowo, ponieważ nic nie dodajemy i nie mnożymy, aby wyjść poza maksymalną wartość, oraz nie dzielimy (przez zero). No to przykład:

Przed:
a=9.22337203685E+18  // pow(2,63)
b=4294967291         // pow(2,32) - 5
Po:
a=4294967291
b=-9223372036854775808   // tutaj wartość jest nieprawidłowa

Oczywiście problemem tutaj nie jest sam XOR, który działa tak, jak powinien, a utrata dokładności liczby, gdy zbyt duża liczba nie mieści się w zmiennej. W każdym razie otrzymany wynik jest nieprawidłowy.

14,17. list() i array()

Te sposoby działają tak jak powinny i będą działać zawsze. Ich używanie ma jednak dość ograniczony sens. Dlaczego? Dlatego, że musi zostać utworzona dodatkowa tablica w pamięci, która zawiera wartości obu zmiennych a następnie jej składniki są dopiero przypisywane ponownie do zmiennych. Czy jest to lepsze rozwiązanie od użycia 3 zmiennych? Odpowiedź znajduje się niżej w testach.

15-16. Operacje na ciągach i tablicach

Czy to nie wygląda, jak wytaczanie armaty na muchę? ;) Osiągnięty wynik będzie zbliżony do tego który osiągnęliśmy w przypadku dodawania i mnożenia, przy czym nie występuje tu problem dzielenia przez zero.

0. 3 zmienne

Czyżby zatem użycie trzeciej zmiennej miało być nadal najlepszym sposobem?

 

Sposoby na rozwiązanie zadania dla innych typów danych

1. Ciągi tekstowe

W przypadku ciągów śmiało można zastosować rozwiązania 14, 15, 16 i 17 pozbywając się z nich typowania na liczby.

2. Tablice

W przypadku tablic można użyć rozwiązań 14, 16 i 17 i tutaj podobnie – bez typowania, ale i bez łączenia tablic w ciągi (i wstępnego dzielenia ciągów na tablice).

3. Obiekty

W przypadku obiektów zadziałają rozwiązania 14 i 17.

4. Zmienne logiczne (TRUE/FALSE)

Zmienne logiczne mają tylko dwie wartości – TRUE i FALSE. Możemy je typować na liczby i zadziałają wszystkie powyższe rozwiązania, ale musimy mieć na uwadze dzielenie przez zero. Bez typowania, tylko rozwiązania 14 i 17 zadziałają.

5. Zmienne z danymi rożnych typów

Tutaj nie mamy zbyt wielkiego pola do popisu. Jedyne pewne sposoby to rozwiązania 14 i 17.

 

Metodologia testów

Testy wykonałem jedynie dla liczb. W przypadku danych innych typów, rozwiązania są bardzo podobne i można je porównać posługując się poniższymi wynikami.

Chciałbym też tutaj dodać ważną uwagę – wyżej zostały wymienione słabości rożnych rozwiązań. Testy były wykonane przy założeniu, że znamy te słabości i je akceptujemy, np. mamy pewność, że zmienne nie będą zawierały określonych wartości (jak $b = 0 w przypadku mnożenia/dzielenia), albo algorytmy są stosownie zabezpieczone (np. instrukcjami warunkowymi).

W przypadku testów zużycia pamięci, pierwsze wywołania memory_get_usage() służą zaalokowaniu pamięci przez tą funkcję i zmienne, do której wartości będą przypisywane. Wynika to z działania optymalizatora w PHP. W tym momencie podczas mierzenia ilości pamięci przed i po testowanym kodzie nie będzie już dodatkowych alokacji, które zakłóciły by pomiar.

Przykład testu na zużycie pamięci:

<?php

$a = 100;
$b = 234;

$x = memory_get_usage();
$y = memory_get_usage();
$x = memory_get_usage();
$y = memory_get_usage();

$x = memory_get_usage();

$a = $a + $b;
$b = $a - $b;
$a = $a - $b;

$y = memory_get_usage();

echo ($y - $x)."\n";

Test szybkości działania jest podobny do tego, który opisywałem w echo vs. print. Zmienne ustawiam przed pomiarem czasu i nie ustawiam ich przy każdym pomiarze, ponieważ nie ma tu znaczenia, jakie będą miały wartości (wartości będą się zamieniać miejscami przy każdym pomiarze). Przykład testu:

<?php

// require benchmark file
require("benchmark.php");

$a = 100;
$b = 234;

$time1 = microtime(TRUE);

//code to be benchmarked
for($i = 0; $i < $repeats; $i++){
    $a = $a + $b;
    $b = $a - $b;
    $a = $a - $b;
}

$time2 = microtime(TRUE);

// empty loop
for($i = 0; $i < $repeats; $i++){
}

$time3 = microtime(TRUE);

// save log
logResult();

 

Testy

Wyniki testów:

Test z zerowym numerem, to standardowe podejście z dodatkową trzecią zmienną. Wyniki pamięci podane są w bajtach, a czas w mikrosekundach. Dla czasu dodałem drugi wykres tak, aby było widać różnice przy szybszych rozwiązaniach.

Pod względem użycia pamięci najlepiej wypadają wszystkie rozwiązania, które nie korzystają z dodatkowych funkcji, a samych operatorów. Nie potrzebują one w ogóle dodatkowej pamięci. Rozwiązanie z tablicami wypadło zdecydowanie najgorzej.

Jeśli weźmiemy pod uwagę czas potrzebny na zamianę zmiennych miejscami, okazuje się, ze standardowe podejście z dodatkową zmienną jest wolniejsze od wszelkich operacji arytmetycznych (choć trzeba tu zaznaczyć, że dla zmiennych innego typu własność ta nie musi zostać zachowana). Użycie dodatkowych funkcji w PHP wydłuża czas potrzebny na zamianę wartości w zmiennych. Tutaj ponownie dwa ostatnie rozwiązania wypadły zdecydowanie najgorzej.

Najszybszym i nie potrzebującym w ogóle dodatkowej pamięci okazało się rozwiązanie z XOR w jednej linijce. Jest ono ponad 2x szybsze od rozwiązania z użyciem dodatkowej zmiennej, a dodatkowo nie wymaga w ogóle dodatkowej pamięci.

 

Podsumowanie

We wpisie nie użyłem wszystkich możliwych kombinacji, ponieważ możliwych wariacji było by zbyt dużo. Można było wymyślić także inne rozwiązania operujące na rożnych funkcjach, ale jak wynika z testów, nawet użycie array() i list() jest już sporo wolniejsze od operacji z użyciem samych operatorów i dodatkowej zmiennej.

Oczywiście ten wpis ma równie ograniczony sens jak echo vs. print a jego wyniki można zaliczyć do mikrooptymalizacji. Jedna operacja zamiany potrzebowała setne części mikrosekundy. Jeśli jednak operacji takiej wymagał by jakiś skrypt, w którym występowała by ona wiele razy (np.  w pętli), takie właśnie optymalizacje potrafią znacznie przyspieszyć jego szybkość.

A Wy znacie jeszcze jakieś ciekawe sposoby na zamianę wartości w zmiennych bez użycia dodatkowej zmiennej?

 

Ten wpis został opublikowany w kategorii Benchmark, Debian, Linux, PHP, Programowanie, Serwery, WWW i oznaczony tagami , , , . Dodaj zakładkę do bezpośredniego odnośnika.

4 odpowiedzi na „17+ sposobów na zamianę wartości w dwóch zmiennych bez użycia trzeciej.

  1. No tak, ale po co to komu? zysk z przechowania jednej zmiennej? w PHP i tak nie mam Garbage Collectora więc po co to komu?

    • Zacytuję może wstęp: “Dziś zatem mamy kolejny wpis z gatunku tych, które raczej nikomu do niczego się nie przydadzą, ale są ciekawe :)”.
      Nie wszystko musi mieć sens. :)

      Ten wpis powstał z czystej ciekawości. Ja staram się kod możliwie mocno optymalizować. To są raczej mikrooptymalizacje, które zazwyczaj nie mają sensu, ale zastanawiało mnie co będzie najbardziej optymalnej, a skoro już zrobiłem kilka testów, podzieliłem się wiedzą z innymi.

      • Najbardziej optymalna będzie ucieczka z PHP gdzieś indziej :), polecam Scale i np. Play Framework, jako były PHPowiec polecam ta ścieżkę – język nie tak restrykcyjny jak inne kompilowany, np Java (np można bezpośrednio się dobierać do wartości w tabeli / hashmapie jak w PHP, tj zamiast cos.get(“dupa”) piszemy cos(“dupa”) ala phpowe $cos["dupa"] ), a jednocześnie bardzo bardzo szybki, bez automatycznego rzutowania i o wiele łatwiejszy w pisaniu i nauce od PHP.

        • Dlaczego najbardziej optymalna? Jeśli PHP jest takie złe i powolne, to czemu tyle oprogramowania nadal jest tworzona w tym języku. Nawet duże projekty działające pod dużym obciążeniem. :)
          Polecasz Play Framework – ja jestem przeciwnikiem “wszystkomogących i wszystkomających” frameworków, bo to one dopiero są koszmarnie powolne. NIe znam tego frameworka, wiec nie jestem w stanie powiedzieć czy w jego przypadku też tak jest.

Dodaj komentarz

Musisz się zalogować (także Facebook, Google+, Twitter), aby móc dodać komentarz.