Saturday, May 8, 2010

Making Random Suck Less

One of the biggest complaints I get about WallSwitch is that the random switching sucks. It repeats images too frequently and just doesn't 'feel right'. I couldn't agree more, so when I ran across this article, I figured I could do something about it.

The problem is that random numbers don't work how the human brain expects. The article above explains it in detail, but suffice it to say that pure/pseudo random numbers suck for most things a user interacts with. What I wanted was a way to provide selections that are still nondeterministic, but closer to what users expect.

The method itself is nothing more than random selection using weighted items. I wanted to keep a feeling of randomness, but make sure more recent selections were less likely to appear. This being Java, the first thing I did was make an interface to hold the object and it's priority:

public interface BetterRandomItem {
 int getPriority();
 void setPriority(int newPriority);
}


Then, I made a choice() function (name taken from Python's random.choice) that uses this priority.

public static BetterRandomItem choice(List items) {
  if(items == null || items.size() == 0)
   throw new IllegalArgumentException("items is null or empty");
  
  // Sum all the priority values
  int itemSpace = 0;
  for(int i = 0; i < items.size(); i++)
   itemSpace += items.get(i).getPriority();  
  
  // Pull an int from that space
  int target = new Random().nextInt(itemSpace + 1);
  
  // Match the int to the corresponding item
  int tmpVal = 0;
  for(int i = 0; i < items.size(); i++){
   tmpVal += items.get(i).getPriority();
   if(tmpVal >= target)
    return items.get(i);
  }
  
  // If that failed, return the last in the list, I guess
  return items.get(items.size() - 1);
 }


Not the most complex piece of code ever written, but it'll go a long way to making users a bit happier with 'random' selections. Since putting this in, the emails and comments about my random function sucking have completely stopped.

Note: For my implementation, I kept track of the last 50 images displayed and gave them weights 1-50. Any unseen images were weighted as (num seen images * 10), giving them significantly more weight than those that had been seen.

Another Note: Watch out for int overflows in itemSpace. It would be nice if Random.nextLong took an argument.

9 comments:

  1. This article should be titled "making Random suck more - running in O(n) time"

    ReplyDelete
  2. Why not just construct a random ordering of the images ahead of time in which each one appears once, in the same way that one would shuffle a deck of cards, then deal them out one at a time?

    ReplyDelete
  3. Another Idea, put the items in a hash, with the key being their Priority, and then track the sum of the Priorities with a separate variable, then you won't have to iterate through the entire list of items twice.

    Also wanted to let you know that when I wake my phone up and unlock the screen, I get rapid switching = number of switches that should have occurred while the phone was asleep.

    ReplyDelete
  4. I love the app and especially the residing feature; it works much better than the stock android residing option. I know the whole point of your program is to switch randomly but I think this app would be a 5/5 if you were able to select a single image to set as wallpaper. Just my two cents.

    ReplyDelete
  5. Love the app... except that huge widget. It's great that you included the widget, but can you just make is smaller like a 1x1 toggle switch? That would make your app perfect, IMO.

    ReplyDelete
  6. Is there a way to make the wallswitching profile independent? I have 3 different profiles and would prefer to use 3 different folders, one for each, but it only uses the 1 folder I select on the initial profile.

    ReplyDelete
  7. Loving your app! I'd really like the option for sequential wallpapers, I think that it's the only missing option.
    It's great to have a different wallpaper every minute :) Thanks a lot!

    ReplyDelete
  8. I wrote about WallSwitch in my recent syndicated column Techlife about Personal History. Funny enough I even commented about the algorithm used. I love it. Going to add my comments to Google Play as well. "What Did You Do One Year Ago Today?" - http://bit.ly/P6HI6Q

    ReplyDelete
  9. Great little app. Needs to be updated to account for hi-dpi displays like the SGS3. There seem to be a lot of problem with font sizes too.

    ReplyDelete