Swap (datorprogrammering)

I datorprogrammering hänvisar handlingen att byta två variabler till att ömsesidigt utbyta variablernas värden. Vanligtvis görs detta med data i minnet . Till exempel, i ett program kan två variabler definieras så här (i pseudokod ):

data_item x := 1 data_item y := 0 swap (x, y);

Efter att swap() har utförts kommer x att innehålla värdet 0 och y kommer att innehålla 1; deras värderingar har utbytts. Denna operation kan generaliseras till andra typer av värden, som strängar och aggregerade datatyper . Jämförelsesorter använder swappar för att ändra positionerna för data.

I många programmeringsspråk är swap -funktionen inbyggd. I C++ tillhandahålls överbelastningar som tillåter std::swap att byta ut några stora strukturer i O(1)-tid .

Använder en temporär variabel

Den enklaste och förmodligen mest använda metoden för att byta två variabler är att använda en tredje temporär variabel :

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

Även om detta är konceptuellt enkelt och i många fall det enda bekväma sättet att byta två variabler, använder det extra minne. Även om detta inte borde vara ett problem i de flesta applikationer, kan storleken på de värden som byts ut vara enorma (vilket innebär att den temporära variabeln kan uppta mycket minne också), eller så kan bytesoperationen behöva utföras många gånger, eftersom i sorteringsalgoritmer.

Dessutom kan byte av två variabler i objektorienterade språk som C++ innebära ett anrop till klasskonstruktorn och destruktorn för den temporära variabeln och tre anrop till copy constructor . Vissa klasser kan allokera minne i konstruktorn och avallokera det i destruktorn, vilket skapar dyra anrop till systemet. Kopieringskonstruktörer för klasser som innehåller mycket data, t.ex. i en array , kan till och med behöva kopiera data manuellt.

XOR-byte

XOR swap använder XOR -operationen för att byta två numeriska variabler. Det anses allmänt vara snabbare än den naiva metoden som nämns ovan; men det har nackdelar . XOR swap används vanligtvis för att byta datatyper på låg nivå, som heltal . Den är dock teoretiskt kapabel att byta vilka två värden som helst som kan representeras av bitsträngar med fast längd .

Byt mellan addition och subtraktion

Denna metod byter två variabler genom att addera och subtrahera deras värden. Detta används sällan i praktiska tillämpningar, främst på grund av:

Den kan bara byta numeriska variabler; det kanske inte är möjligt eller logiskt att lägga till eller subtrahera komplexa datatyper, som behållare .
När man byter variabler av en fast storlek blir aritmetiskt överflöde ett problem.
Det fungerar generellt inte för flyttalsvärden, eftersom aritmetik med flyttal är icke-associativ .

Byta behållare

Behållare som allokerar minne från högen med hjälp av pekare kan bytas ut i en enda operation, genom att enbart byta pekarna. Detta finns vanligtvis i programmeringsspråk som stöder pekare, som C eller C++ . Standardmallbiblioteket överbelastas sin inbyggda växlingsfunktion för att utbyta innehållet i behållare effektivt på detta sätt .

Eftersom pekarvariabler vanligtvis har en fast storlek (t.ex. har de flesta stationära datorer pekare som är 64 bitar långa), och de är numeriska, kan de snabbt bytas med XOR swap .

Parallelluppdrag

Vissa språk, som Ruby eller Python stöder parallella tilldelningar , vilket förenklar notationen för att byta två variabler:

a, b = b, a

Detta är en förkortning för en operation som involverar en mellanliggande datastruktur: i Python, en tupel; i Ruby, en array.

Javascript 6+ stöder destruktureringsoperatorer som gör samma sak:

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

Funktionsbyte

Här skickas två globalt omfångade variabler efter värde genom en funktion, vilket eliminerar behovet av en temporär lagringsvariabel.

  
  

     

   
    
    


 

      x  =  1  ;  y  =  2  ;  konsol  .  log  (  x  +  " "  +  y  );  //  ger 1 2  funktionsbyte  (  a  ,  b  )  {  x  =  b  ;  y  =  a  ;  }  swap  (  x  ,  y  );  konsol  .  log  (  x  +  " "  +  y  );  // utgångar 2 1

Underlättande av byte i moderna datorer

Dedikerade instruktioner

På grund av de många tillämpningarna för att byta data i datorer ger de flesta processorer nu möjligheten att byta variabler direkt genom inbyggda instruktioner. x86- processorer, till exempel, inkluderar en XCHG- instruktion för att byta två register direkt utan att kräva att ett tredje temporärt register används. En jämför-och-byt- instruktion tillhandahålls till och med i vissa processorarkitekturer, som jämför och villkorligt byter två register. Detta används för att stödja tekniker för ömsesidig uteslutning .

XCHG kanske inte är så effektivt som det verkar. Till exempel, i x86 -processorer kommer XCHG implicit att låsa åtkomst till alla operander i minnet för att säkerställa att operationen är atomic , och därför kanske inte är effektiv när man byter minne. Sådan låsning är viktig när den används för att implementera trådsäker synkronisering, som i mutexes . En XCHG är dock vanligtvis det snabbaste sättet att byta två maskinstorleksord som finns i register . Registerbyte kan också användas för att byta register effektivt.

Parallellt utförande

Med tillkomsten av instruktionspipelining i moderna datorer och flerkärniga processorer som underlättar parallell beräkning , kan två eller flera operationer utföras samtidigt. Detta kan påskynda bytet med hjälp av temporära variabler och ge det en fördel gentemot andra algoritmer. Till exempel XOR-swapalgoritmen sekventiell exekvering av tre instruktioner. Men med två temporära register kan två processorer som körs parallellt byta två variabler i två klockcykler:

 Steg 1  Processor 1: temp_1 := X Processor 2: temp_2 := Y  Steg 2  Processor 1: X := temp_2 Processor 2: Y := temp_1

Fler tillfälliga register används och fyra instruktioner behövs istället för tre. I alla fall kunde detta i praktiken inte implementeras i separata processorer, eftersom det bryter mot Bernsteins villkor för parallell beräkning. Det skulle vara omöjligt att hålla processorerna tillräckligt synkroniserade med varandra för att detta utbyte skulle ha någon betydande fördel jämfört med traditionella versioner. Den kan dock användas för att optimera utbyte för en enda processor med flera laddnings-/lagerenheter.