Kiedy zacząłem pracować, programista asemblera na komputerze mainframe pokazał mi, jak zamieniają się na wartości bez korzystania z tradycyjnego algorytmu:
a = 0xBABE
b = 0xFADE
temp = a
a = b
b = temp
To, czego używali do zamiany dwóch wartości - z nieco na duży bufor - to:
a = 0xBABE
b = 0xFADE
a = a XOR b
b = b XOR a
a = a XOR b
teraz
b == 0xBABE
a == 0xFADE
co zamieniło zawartość 2 obiektów bez potrzeby utrzymywania trzeciej temperatury.
Moje pytanie brzmi: czy ten algorytm wymiany XOR jest nadal w użyciu i gdzie nadal ma zastosowanie?
algorithms
Quinton Bernhardt
źródło
źródło
Odpowiedzi:
Podczas używania
xorswapistnieje niebezpieczeństwo podania tej samej zmiennej jako obu argumentów do funkcji, która zeruje wymienioną zmienną, ponieważ jest onaxorze sobą, co powoduje, że wszystkie bity zostają wyzerowane. Oczywiście samo to spowodowałoby niepożądane zachowanie niezależnie od zastosowanego algorytmu, ale zachowanie może być zaskakujące i nieoczywiste na pierwszy rzut oka.Tradycyjnie
xorswapbył stosowany w implementacjach niskiego poziomu do wymiany danych między rejestrami. W praktyce istnieją lepsze alternatywy dla zamiany zmiennych w rejestrach. Na przykład Intel x86 maXCHGinstrukcję, która zamienia zawartość dwóch rejestrów. Wiele razy kompilator obliczy semantykę takiej funkcji (zamienia zawartość przekazywanych do niej wartości) i może w razie potrzeby dokonywać własnych optymalizacji, więc próba zoptymalizowania czegoś tak trywialnego jak funkcja zamiany tak naprawdę nic nie kupuje w praktyce. Najlepiej jest zastosować oczywistą metodę, chyba że istnieje udowodniony powód, dla którego gorsze byłoby powiedzenie xorswap w obrębie problematycznej dziedziny.źródło
a: 0101 ^ 0101 = 0000; b: 0101 ^ 0000 = 0101; a: 0101 ^ 0000 = 0101;-1->+1.a=10, b=10, a jeśli to zrobiszxorswap(a,b), zadziałałoby i nie wyzerowało zmiennych, które są fałszywe, a teraz usunięte. Ale jeśli niexorswap(a, a)wtedyadostanie wyzerowany które pierwotnie oznaczało, ale głupi. :)Kluczem do odpowiedzi jest pytanie - „praca programisty asemblera na komputerach mainframe” - na kilka dni przed kompilatorem. Kiedy ludzie skulili się z instrukcjami montażu i ręcznie opracowali dokładne rozwiązania dla konkretnego elementu sprzętu (który może, ale nie musi działać na innym modelu tego samego komputera - problemy, takie jak synchronizacja dysków twardych i pamięci bębna, miały wpływ na sposób kodowania napisane - przeczytaj Historię Mela, jeśli czujesz potrzebę nostalgii).
W dawnych czasach rejestrów i pamięci brakowało, a każda sztuczka polegająca na tym, że nie trzeba było prosić o kolejny bajt lub słowo pamięci od głównego architekta, oszczędzała czas - zarówno przy pisaniu kodu, jak i czasu wykonania.
Te dni minęły. Sztuczka polegająca na zamianie dwóch rzeczy bez użycia trzeciej jest sztuczką. Pamięć i rejestry są obfite we współczesnym środowisku komputerowym, a ludzie nie piszą już asemblera. Nauczyliśmy wszystkich naszych sztuczek naszych kompilatorów i robią to lepiej niż my. Możliwe, że kompilator zrobił coś jeszcze lepszego niż to, co byśmy zrobili. W większości przypadków czasem z jakiegoś powodu musimy napisać asembler w wewnętrznej pętli ... ale to nie jest zapisanie rejestru ani słowa pamięci.
Może się to przydać ponownie, jeśli pracujesz w szczególnie ograniczonym mikrokontrolerze, ale optymalizacja zamiany nie jest prawdopodobnie źródłem problemu - próbowanie bycia zbyt sprytnym jest bardziej prawdopodobne.
źródło
Czy to zadziała? Tak.
Czy powinieneś go użyć? Nie.
Tego rodzaju mikrooptymalizacja miałaby sens, gdyby:
spojrzałeś na kod generowany przez kompilator, aby w prosty sposób to zrobić (przypisanie i tymczasowe) i zdecydowałeś, że podejście XOR generuje szybszy kod
Twoja aplikacja została sprofilowana i okazało się, że koszt prostego podejścia przeważa nad przejrzystością kodu (i skutkuje oszczędnościami w utrzymaniu)
Do pierwszego punktu, chyba że wykonałeś ten pomiar, powinieneś zaufać kompilatorowi. Kiedy semantyka tego, co próbujesz zrobić, jest jasna, kompilator może wykonać wiele sztuczek, w tym zmienić porządek dostępu do zmiennych, aby zmiana nie była wcale potrzebna, lub wstawienie instrukcji na poziomie maszyny zapewniających najszybsze zamień dla danego typu danych. „Sztuczki”, takie jak zamiana XOR, utrudniają kompilatorowi zobaczenie, co próbujesz zrobić, a tym samym zmniejszają możliwości zastosowania takich optymalizacji.
Do drugiego punktu, co zyskujesz na dodatkową złożoność? Nawet jeśli zmierzyłeś i znalazłeś podejście XOR szybciej, czy ma to wystarczający wpływ, aby uzasadnić mniej jasne podejście? Skąd wiesz?
Na koniec powinieneś sprawdzić, czy istnieje standardowa funkcja zamiany dla twojej platformy / języka - na przykład C ++ STL zapewnia funkcję zamiany szablonów, która będzie wysoce zoptymalizowana dla twojego kompilatora / platformy.
źródło
Mój kolega powiedział, że jest to podstawowa sztuczka, której nauczył na studiach uniwersyteckich dla programisty systemów automatycznych. Wiele takich systemów jest wbudowanych z ograniczonymi zasobami i mogą brakować bezpłatnego rejestru, aby zachować tymczasową wartość; w takim przypadku taka trudna wymiana (lub jej analog z dodawaniem i odejmowaniem) staje się niezbędna, więc nadal jest używana.
Należy jednak dbać o to, aby te dwie lokalizacje nie mogły być identyczne, ponieważ w tym drugim przypadku skutecznie wyzeruje obie wartości. Zwykle ogranicza się to do oczywistych przypadków, takich jak wymiana rejestru i lokalizacja pamięci.
W przypadku x86 instrukcje xchg i cmpxchg w większości przypadków spełniają tę potrzebę, ale RISC na ogół nie są nimi objęte (z wyjątkiem Sparc).
źródło