Categories Bez kategoriiPosted on

Wariacje na temat zamiany miejscami dwóch wartości

Paweł Sołtysiak2 komentarze do Wariacje na temat zamiany miejscami dwóch wartości

Zamiana dwóch liczb (a=5 b=89) miejscami, że (a=89 b=5), jest prostą rzeczą do zaprogramowania. Ale nawet tak prostą, rzeczy można skomplikować, do takiego stopnia, że wymagane jest wprowadzenie komentarzy.

Algorytm jest prosty:

  1. Utwórz zmienną pomocniczą tmp
  2. Przypisz do tmp wartość a
  3. Przypisz do a wartość b
  4. Przypisz do b wartość tmp
W języku C można wykorzystać funkcję (z koniecznym wykorzystaniem wskaźników):

void swap_int(int* a, int*b)
{
    int tmp =*a;
    *a=*b;
    *b=tmp;

}
/* Wywołanie funkcji */
int main(){
    int a=15,b=75;
    swap_int(&a,&b);
}

Jednak powyższe rozwiązanie ma dwie wady:

  1. Funkcja nie działa dla każdego typu danych
  2. Wywołanie funkcji jest spowolnione, ponieważ jest funkcją. (tzw. koszt wywołania funkcji, związany z assemblerową instrukcją call)
Sposób na rozwiązanie tego problemu jest wykorzystanie makr. I to nie byle jakich makr. Kod pochodzi z biblioteki standardowej (dołączanej do kompilatora) glibc, zwianej bezpośrednio z GCC. (a dokładnej pliku funkcji Quicksort – /stdlib/qsort.c)
#define SWAP(a, b, size)      
do               
{               
    register size_t __size = (size);  
    register char *__a = (a), *__b = (b);  
    do              
    {              
        char __tmp = *__a;       
        *__a++ = *__b;       
        *__b++ = __tmp;          
    } while (--__size > 0);     
} while (0)

Przypomnijmy, że makra to dosyć chamskie zastąpienie tekstu dlatego takie użycie makra (wyświetlenie hello world – pod warunkiem że funkcja display_hello zwróci wartość true):
#define TWO_PRINTF()  
    printf("%s","Hello ");
    printf("%s","World")
    
if(display_hello())
    TWO_PRINTF();
Zostanie rozwinięte do postaci:
if(display_hello())
    printf("%s","Hello ");
    printf("%s","World");

Co nie do końca jest o co nam chodziło, ponieważ słowo 'world’ zawsze zostanie wyświetlone.

Ten boczny wywód na temat makr, jest ważny dla zrozumienia dlaczego występuje pętla do{…]while(0). Taka pętla wykona się zawsze jeden raz ponieważ  warunek sprawdzający jest zawsze fałszywy. Pętla posiada kilka ważnych cech dla działania marka

  1. Pozwala uniknąć błędu z if’em który został wcześniej opisany
  2. Pozwala na zadeklarowanie zmiennych w akurat tym miejscu programu
  3. Dodaje wartość czysto stylistyczną wywołanie makra musi się kończyć średnikiem, więc makro wygląda jakby było normalną funkcją.
Backslashe ” są używane wtedy gdy makro zawiera się w więcej niż jedną linijkę.
Dla przypomnienia słowo kluczowe register przed zmienną służy do powiedzenia kompilatorowi że dana zmienna będzie często wykorzystywana i aby tą zmienną przechowywał w rejestrze procesora. Tak naprawdę to tylko sugestia, kompilator może to słowo kluczowe zupełnie zignorować. Niezależnie od tego czy kompilator słowo register bierze pod uwagę czy nie, z takiej zmiennej nie można uzyskać adresu zmiennej, ponieważ zgodnie z założeniami zmienna nie jest przechowywana w pamięci komputera.

Ciekawym trickiem wykorzystanym w makrze jest utworzenie kolejnych zmiennych o nazwach __a  i __b ponieważ to zapobiega wpadnięciu w pułapkę kiedy do makra poda się na przykład SWAP(pa++,pb++,sizeof(char)) wtedy wskaźnik może zostać przysunięty nie tylko jeden raz.

Makro operuje na wskaźnikach typu char *, dla zmiennych większych niż char jest potrzebne rzutowanie w dół. Przykładowe wykorzystanie makra SWAP dla dwóch zmiennych int:
int a,b;
int *pa,*pb;
pa=&a;
pb=&b;

SWAP((char *) pa,(char *)pb,sizeof(int));
Druga pętla do{…}while(–__size > 0); zamienia bajt po bajcie. Czyli przykładowo dla zmiennej typu int potrzebne jest wykonanie 4 zamian ponieważ rozmiar int’a w bajtach to 4.

Jak widać stworzenie wydajnej i działającej na wszystkich typach funkcji w języku C jest nieco skomplikowane.

W językach wysokiego poziomu, np Pythonie wystarczy jedna linijka kodu:

a, b = b, a

Powyższa linijka działa dla każdego typu zmiennych od liczb całkowitych, przez liczby zmiennoprzecinkowych po zmienne typu string