Zamiana (programowanie komputerowe)
W programowaniu komputerowym akt zamiany dwóch zmiennych odnosi się do wzajemnej wymiany wartości zmiennych. Zwykle odbywa się to z danymi w pamięci . Na przykład w programie dwie zmienne można zdefiniować w następujący sposób (w pseudokodzie ):
element_danych x := 1 element_danych y := 0 zamiana (x, y);
Po wykonaniu swap() x będzie zawierało wartość 0, a y będzie zawierało 1; ich wartości zostały wymienione. Tę operację można uogólnić na inne typy wartości, takie jak ciągi znaków i zagregowane typy danych . Sortowanie porównawcze wykorzystuje zamiany do zmiany pozycji danych.
W wielu językach programowania funkcja zamiany jest wbudowana. W C++ zapewniono przeciążenia, które umożliwiają std::swap wymianę niektórych dużych struktur w czasie O(1) .
Korzystanie ze zmiennej tymczasowej
Najprostszą i prawdopodobnie najczęściej stosowaną metodą zamiany dwóch zmiennych jest użycie trzeciej zmiennej tymczasowej :
zdefiniuj zamianę (x, y) temp := x x := y y := temp
Chociaż jest to koncepcyjnie proste iw wielu przypadkach jedyny wygodny sposób zamiany dwóch zmiennych, wymaga dodatkowej pamięci. Chociaż nie powinno to stanowić problemu w większości aplikacji, rozmiary zamienianych wartości mogą być ogromne (co oznacza, że zmienna tymczasowa może również zajmować dużo pamięci) lub operacja zamiany może wymagać wielokrotnego wykonywania, ponieważ w algorytmach sortowania.
Ponadto zamiana dwóch zmiennych w językach zorientowanych obiektowo, takich jak C++ , może obejmować jedno wywołanie konstruktora klasy i destruktora dla zmiennej tymczasowej oraz trzy wywołania konstruktora kopiującego . Niektóre klasy mogą przydzielać pamięć w konstruktorze i zwalniać ją w destruktorze, tworząc w ten sposób kosztowne wywołania systemu. Konstruktory kopiujące dla klas zawierających dużo danych, np. w tablicy , mogą nawet wymagać ręcznego skopiowania danych.
Zamiana XOR
Zamiana XOR wykorzystuje operację XOR do zamiany dwóch zmiennych numerycznych. Ogólnie reklamuje się, że jest szybsza niż naiwna metoda wspomniana powyżej; ma jednak wady . Zamiana XOR jest zwykle używana do zamiany typów danych niskiego poziomu, takich jak liczby całkowite . Jednak teoretycznie jest w stanie zamienić dowolne dwie wartości, które mogą być reprezentowane przez ciągi bitów o stałej długości .
Zamień przez dodawanie i odejmowanie
Ta metoda zamienia dwie zmienne, dodając i odejmując ich wartości. Jest to rzadko używane w praktycznych zastosowaniach, głównie dlatego, że:
- Może wymieniać tylko zmienne numeryczne; dodawanie lub odejmowanie złożonych typów danych, takich jak kontenery , może nie być możliwe lub logiczne .
- Podczas zamiany zmiennych o stałym rozmiarze problemem staje się przepełnienie arytmetyczne .
- Generalnie nie działa to dla wartości zmiennoprzecinkowych, ponieważ arytmetyka zmiennoprzecinkowa nie jest asocjacyjna .
Wymiana kontenerów
Kontenery , które przydzielają pamięć ze sterty za pomocą wskaźników , mogą być wymieniane w jednej operacji, poprzez zamianę samych wskaźników. Zwykle można to znaleźć w językach programowania obsługujących wskaźniki, takich jak C lub C++ . Standardowa biblioteka szablonów przeciąża swoją wbudowaną funkcję zamiany, aby w ten sposób wydajnie wymieniać zawartość kontenerów.
Ponieważ zmienne wskaźnikowe mają zwykle stały rozmiar (np. większość komputerów stacjonarnych ma wskaźniki o długości 64 bitów ) i są numeryczne, można je szybko zamienić za pomocą XOR swap .
Przydział równoległy
Niektóre języki, takie jak Ruby czy Python , obsługują przypisania równoległe , co upraszcza notację zamiany dwóch zmiennych:
za, b = b, za
Jest to skrót dla operacji obejmującej pośrednią strukturę danych: w Pythonie krotka; w języku Ruby tablica.
Javascript 6+ obsługuje operatory destrukturyzacji, które robią to samo:
[a, b] = [b, a];
Zamiana funkcji
Tutaj dwie zmienne o zasięgu globalnym są przekazywane przez wartość przez funkcję, eliminując potrzebę tymczasowej zmiennej pamięci.
x = 1 ; y = 2 ; konsola . dziennik ( x + " " + y ); // wyjścia 1 2 zamiana funkcji ( a , b ) { x = b ; y = za ; } zamiana ( x , y ); konsola . dziennik ( x + " " + y ); // wyjścia 2 1
Ułatwienie wymiany w nowoczesnych komputerach
Dedykowane instrukcje
Ze względu na wiele zastosowań wymiany danych w komputerach większość procesorów zapewnia teraz możliwość bezpośredniej wymiany zmiennych za pomocą wbudowanych instrukcji. Na przykład procesory x86 zawierają instrukcję XCHG do bezpośredniej zamiany dwóch rejestrów bez konieczności użycia trzeciego rejestru tymczasowego. Instrukcja porównania i zamiany jest nawet dostępna w niektórych architekturach procesorów, która porównuje i warunkowo zamienia dwa rejestry. Służy to wspieraniu wzajemnego wykluczania .
XCHG może nie być tak wydajny, jak się wydaje. Na przykład w procesorach x86 XCHG niejawnie zablokuje dostęp do dowolnych operandów w pamięci , aby zapewnić, że operacja jest atomowa , a więc może nie być wydajna podczas wymiany pamięci. Takie blokowanie jest ważne, gdy jest używane do implementacji synchronizacji bezpiecznej dla wątków, jak w przypadku muteksów . Jednak XCHG jest zwykle najszybszym sposobem zamiany dwóch słów wielkości maszyny znajdujących się w rejestrach . Zmiana nazwy rejestru może być również wykorzystana do wydajnej wymiany rejestrów.
Wykonanie równoległe
Wraz z pojawieniem się potokowego przesyłania instrukcji w nowoczesnych komputerach i procesorach wielordzeniowych ułatwiających przetwarzanie równoległe , można wykonywać jednocześnie dwie lub więcej operacji. Może to przyspieszyć zamianę przy użyciu zmiennych tymczasowych i dać jej przewagę nad innymi algorytmami. Na przykład algorytm wymiany XOR wymaga sekwencyjnego wykonania trzech instrukcji. Jednak przy użyciu dwóch rejestrów tymczasowych dwa procesory działające równolegle mogą zamienić dwie zmienne w dwóch cyklach zegara:
Krok 1 Procesor 1: temp_1 := X Procesor 2: temp_2 := Y Krok 2 Procesor 1: X := temp_2 Procesor 2: Y := temp_1
Wykorzystywanych jest więcej rejestrów tymczasowych i potrzebne są cztery instrukcje zamiast trzech. W każdym razie w praktyce nie można tego zaimplementować w oddzielnych procesorach, ponieważ narusza to warunki Bernsteina dotyczące obliczeń równoległych. Utrzymywanie wystarczającej synchronizacji procesorów ze sobą byłoby niewykonalne, aby ta zamiana miała jakąkolwiek znaczącą przewagę nad tradycyjnymi wersjami. Można go jednak użyć do optymalizacji wymiany dla pojedynczego procesora z wieloma jednostkami ładowania/przechowywania.