VTV Lab

VTV Lab

Swap values experiments on using different approaches

Folks, we all know one typical interview question around swapping values for two variables. And maybe all of us remember by heart that there are multiple ways to do so.

The most straightforward way which everyone must know during school is using a temp variable.

Such as:

int a = 10, int b = 5;

int tmp = a;

a = b; b = tmp;

The second way is to use arithmetic operations such as addition/subtraction or multiplication/division

Code is like

int a = 10; int b = 5;

a = a + b; b = a – b; a = a – b;

The good thing is we don’t need to use a temp variable here and it means less memory/register used.

Same logic goes for multiplication and division. However, another interesting way which is often asked is using XOR.

a = a ^ b; b = a ^ b; a = a ^ b;

Three assignments with same expression. Nothing easier to remember.

But it seems few people have ask which one is better except the memory assigned for the extra variable. I did some simple benchmark today and would like to share with you guys. In a block of 100k “swap” operations, I increment it one block at a time and measure the time it takes using three different above approaches.

Set up:

System: runs on a Intel Core i5 3Ghz x 4, 64 bits, Java 7

Input are all primitive integers, time measure in nano second. Before running, did some “warm up” for JVM to be ready.

What I found out is there are no significant difference between using a tmp variable and using arithmetic operation. The time taken fluctuates around 300 ns regardless of the number of block of operation (be it 100k swap or 50 times more).

Using XOR, a clearly linear trend in the time taken can be observed. Approximately 230k ns is needed for one block (100,000 swaps).  This is 1000 times as slow as other traditional methods.

Conclusion: Using XOR approach is a crappy theory which is only valid in interview/text book context!

Attaching a graph of the result swap_experiment

Welcome any comments or question.

Advertisements

Single Post Navigation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: