ShimPossible

When swapping variables most people use

tmp = a
a = b
b = tmp


This requires using an extra variable tmp to store A while it is overwritten with b.  Wouldn’t it be great if you could swap the two without using an extra variable?  The XOR swap algorithm is just what you need

a^=b^=a^=b

This ends up with A and B swapped.  Still 3 assignments but with out the extra variable.  If you want a good explaination of how that works read the wikipedia article.

A word of warning though, the above code only works in C/C++.   It will not work in an VM language like Java or .NET.    This has to do with how the languages are implemented.  Java and .NET are stack based VMs where as C/C++ is register based (and not a VM).  This means that values are pushed onto the stack and then poped off to calculate values.

For example

int a = 1;
int b = 1;
int c1 = (a++) + a;
int c2 = b + (b++);


c1 will be set to 3 and c2 will be set to 2.   Written in C/C++ both will give the answer of 2.  The operator a++ will increment a by 1 but return its original value.  With a stack base, the 1st part of the equation, (a++), is calculated and the answer ( 1 ) push onto the stack.   The next part of the equation (a) is calculated and the answer (2) and push onto the static.   Why is the 2nd part of the equation 2?  When the add operation is run, it retrieves the actual values of the variable one of which is the returned ‘original value’ of a and the other is the current value of A.

An alternate way of writing the XOR swap that works on stack based (and non stack based) VMs is as follows.

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

Note:  This does not work if A and B are the same object.  You shouldn’t be swapping in the case any ways.

The short moral of the story is dont use shortcut code to put a bunch of commands on the same line.  It may not do what you think it will.

I have been working on a project in Adobe flash for the last few months. It basically does a ton of animation and math on every screen. So i put all the code in onEnterFrame, the standard way to run continuous code, so it ran on each frame. Over the months I have done by best to optimize it for speed and efficiency but it had still ran slow, and used a lot of CPU power. How can I make it faster I thought?

The first most obvious thing to try was to up the FPS. Flash defaults it to 12, which seems rather slow for animation doesn’t it? So I updated it to 30, which didn’t seem the to change anything. 60fps offered a slight improvement. So it logically concludes that 120fps (the max you can set in flash) would give the best performance, and it seemed like it did. But the program was still using a ton of CPU power, and had a very low fps.

Was there a way i could squeeze a few more fps out of the program? Well there happens to be a function called updateAfterEvent() which basically tells the program to issue another screen refresh immediately. The only problem is that you can only call it from certain functions., one of which is NOT onEnterFrame. It would only work if called from an event, such as a mouse movement or key press. It also would work for a periodically ran function called through setInterval(). This looked like the option to try.

The function has this basic format:

setInterval(function, ms, params)

It takes a pointer to a function, the number of milliseconds in between calls to the function, and any params you would like to send it. That sounded wonderful, just set a really low ms, and pass in the function that does the same thing my current onEnterFrame does, and it should run as fast as I want. Well, not really. The one gotcha with this function is that it will only call the function at most, as often as onEnterFrame is called. The resolution of this timer is only as fine as the FPS in the movie. Even if i set the ms to 0, it would still only be called as often as onEnterFrame. Back the square one again, or was I? The new difference now was that I could call updateAfterEvent in the function, because it was called through setInterval. Yea! So i put the new code in, removed the old onEnterFrame, left out updateAfterEVents, set the ms to 10 and watched to see if there was any improvement.

Suddenly there was a 10x speed up. The animation wasn’t as sluggish and it responded to the uses key presses immediately. That didn’t make any sense. The same amount of code was being ran on every frame, the program should run the same speed. I tried changing the ms down to 1 and the animation only got faster. I changed the FPS of the program down to 12, and the animation was still just as smooth. I wondered if the function was being called more often the the screen updated, so I turned the FPS down to 1. A FPS of 1 resulted in jerky animation just as expected. So the function was still only being called as often as the screen updated. Turning the fps back to 12 (the default). I ran the program and watched the cpu usage, it was only around 10-20%, instead of the whopping 70% it was using before. Changing the FPS had the most effect on the CPU usage. A higher FPS resulted in more processor usage. But changing the MS in setInterval had barely any effect on CPU usage. Hmmm…. So i went around and changed all my onEnterFrame to setInterval code. This resulted in a much more responsive program, that had lower CPU usage. I still don’t know what the problem with putting code in onEnterFrame is, but I dont think I’ll be useing onEnterFrame much anymore.

The moral of the story:

DO NOT USE onEnterFrame in flash, its slow. Only use it if you absolutely must, but I don’t know why you would.
Changing the FPS does NOT result in faster code. Only MORE CPU usage.
USE setInterval(…) instead with a lowish FPS (such as 12)

I’m sure you have all heard about the problems with certain mp3 players and their ‘random’ play lists. Some people think they repeat some songs more than others. Well here a way to get a truly random shuffle of the list in constant time. That means it takes the same amount of time no matter how big the list is.

This class takes takes an Array of items (data) and divides it into two sections. The first section is the already randomized items, the other is the items that haven’t been shuffled yet. When you request the next item, it picks a random item from the remaining set and swaps it onto the end of the shuffled set. When the non-shuffled set is empty, it starts from the beginning of the array again. At this point the whole array would have been shuffled already so no more swapping will be needed.
Here is the entire class in C#
class Shuffle
{
Random r = new Random();
Object[] data;

int split; // where the split is in the array
bool shuffled = false; // has the entire array been shuffled
public Shuffle(Object[] q)
{
split = 0;
data = q;
}

public Object Next()
{
if (split == data.Length)
{
split = 0;
shuffled = true;
}

if (!shuffled)
{
// find the next one
int idx = r.Next(data.Length – split);
// swap the positions
Object tmp = data[split];
data[split] = data[idx];
data[idx] = tmp;
}

return data[split++];
}
}This class shuffles the list in constant time. It only shuffles when a new item is requested from the list, and only shuffles that one item. This is many many times faster than shuffling all the items at once.

Enjoy.

Given a set of n jugs of different sizes, how would you dump water between them to get a specific amount? If you have ever watched Diehard III, you might have seen this with 2 jugs. In the movie they are given 4 and 5 gallon jugs and are asked to make 3 gallons.

I originally tried to write a program to solve this problem using a brute force method. Needless to say, this was very slow and almost never ran to completion. I thought about it for a while and finally figured it out. It boils down to just solving a graph of connected nodes. Since I wanted to learn ruby, I used this to learn the language.

The basic idea to solve this is:

Have we reach the end state (desired amount)?
Loop through each from jug (i)
Loop through each to jug (j)
Calculate the new state of the jugs (water level in each)
Have we seen this “state” before? If not, store the new state. If we have, then move on
If this is a new state, go to step 1 with new state
old state, continue looping

Obviously, this wont find the optimal solution, but it will find a solution. If you want to find the optimal, you will have to store the steps to get to a state, and see if you have found a quicker path to a state. If you want, I still have the ruby file to solve this.