Prohození hodnot

Technology

12 hours ago

Author

Albert Flores

Prohození hodnot je úlohou z oboru programování, jejímž cílem je prohodit hodnoty dvou proměnných, tedy obvykle vyměnit dvě hodnoty na různých pozicích v operační paměti. Objevuje se jako podúloha například v řadicích algoritmech. Některé programovací jazyky mají pro tuto operaci vestavěnou standardní funkci (obvykle pojmenovanou v angličtině stručně ) a některé instrukční sady mají pro tuto operaci zvláštní strojovou instrukci, ale někdy ji programátor musí implementovat nově.

Přehled postupů

Dočasná proměnná

Konvenčním řešením je použít dočasnou pomocnou proměnnou, pomocí které je postup zapsaný v pseudokódu následující:

define swap(x,y): temp := x x := y y := temp

Nevýhodou tohoto řešení je potřeba další paměti. Často není vytvoření pomocné proměnné velký problém, ale někdy ano. +more Jsou-li například požadované proměnné paměťově náročné, je paměťově náročná i dočasná proměnná. Dalším problémem je použití tohoto postupu v objektově orientovaném programování, jsou-li proměnné ve skutečnosti instancemi třídy s netriviálním konstruktorem a destruktorem. Vytváření a opuštění proměnné takového typu je pak drahé.

Prohození XORem

Prohození hodnot XORem využívá bitovou operaci úplné disjunkce. Zapsáno v pseudokódu vypadá takto:

X := X XOR Y Y := Y XOR X X := X XOR Y

Nepotřebuje žádnou paměť navíc, ale i ono má své nevýhody. Mezi jednotlivými řádky je silná závislost: musí proběhnout přesně v tomto pořadí a každá až poté, kdy je znám výsledek předchozí. +more Na moderních architekturách počítačů je ale často pro zvýšení efektivity rutinně používáno překrývané zpracování strojových instrukcí, jehož efektivitu takováto striktní závislost narušuje.

Prohození sčítáním a odčítáním

Prohození hodnot sčítáním a odčítáním funguje podobně jako výše popsané #Prohození XORem|prohození XORem, ale s operacemi sčítání a odčítání:

X := X + Y Y := X - Y X := X - Y

Při neopatrné implementaci na běžných celých číslech hrozí přetečení. Pro datové typy, pro které je sčítání a odčítání prakticky implementováno jako operace modulární aritmetiky, ovšem zdánlivé přetečení nevadí. +more Obecně se tento postup neužívá, neboť oproti variantě s XORem nabízí jen riziko přetečení - dává smysl jen na platformě, kde není dostupný XOR.

Prohození pomocí ukazatelů

Je-li potřeba prohodit rozsáhlé datové struktury v dynamicky alokované paměti, bývá vhodnější pracovat v programu pouze s ukazateli na ně a prohodit pouze cíle těchto ukazatelů. Takový postup je tradiční například v C nebo v C++, kde takto implementuje prohození kontejnerů i standardní knihovna STL.

Pro samotné prohození hodnot ukazatelů, které bude každopádně o hodně rychlejší, protože ukazatele mají jen několik bajtů, lze použít jiný ze zmíněných postupů.

Podpora v programovacích jazycích

Je-li ve vyšším programovacím jazyce nabízena nějaká funkce pro zrealizování prohození, bývá nejlepší použít tu a nechat na tvůrcích překladače nebo interpreteru, aby ji zrealizovali na dané platformě nejefektivnějším způsobem.

Některé programovací jazyky, například Ruby nebo Python, přitom nabízí paralelní přiřazení, takže lze prohození implementovat následovně:

a, b = b, a

Podobně v JavaScriptu od verze ES6:

[a, b] = [b, a];

Hardwarová podpora

Zvláštní instrukce

Protože prohození hodnot je poměrně běžnou operací, má pro ni řada moderních procesorů zvláštní strojovou instrukci. Například na procesorech architektury x86 je instrukce XCHG, která prohodí hodnoty ve dvou registrech.

Ani přítomnost zvláštní instrukce ještě neznamená, že nejefektivnější je její použití. Zmíněná instrukce XCHG na architektuře x86 totiž při přístupu do paměti zamyká přístup, aby si zajistila svou atomicitu. +more Překladač tedy může v rámci svých optimalizací dát přednost například technice přejmenování registrů.

Paralelní provádění

Vícejádrové procesory umožňující paralelní výpočty by mohly provádět prohození hodnot xorováním ve dvou krocím: Krok 1 Jádro 1: temp_1 := X Jádro 2: temp_2 := Y

Krok 2 Jádro 1: X := temp_2 Jádro 2: Y := temp_1

Celkově ovšem tímto postupem stoupl jak počet instrukcí (na čtyři), tak počet potřebných pomocných proměnných (na dvě).