title: Weighted random pick
body: <p>I have a set of items. I need to randomly pick one. The problem is that they each have a weight of 1-10. A weight of 2 means that the item is twice as likely to be picked than a weight of 1. A weight of 3 is three times as likely. </p>
  
  <p>I currently fill an array with each item. If the weight is 3, I put three copies of the item in the array. Then, I pick a random item. </p>
  
  <p>My method is fast, but uses a lot of memory. I am trying to think of a faster method, but nothing comes to mind. Anyone have a trick for this problem? </p>
  
  <p>EDIT: My Code...</p>
  
  <p>Apparently, I wasn't clear. I do not want to use (or improve) my code. This is what I did.</p>
  
  <pre><code>//Given an array $a where $a[0] is an item name and $a[1] is the weight from 1 to 100.
  $b = array();
  foreach($a as $t)
      $b = array_merge($b, array_fill(0,$t[1],$t));
  $item = $b[array_rand($b)];
  </code></pre>
  
  <p>This required me to check every item in $a and uses max_weight/2*size of $a memory for the array. I wanted a COMPLETELY DIFFERENT algorithm.</p>
  
  <p>Further, I asked this question in the middle of the night using a phone. Typing code on a phone is nearly impossible because those silly virtual keyboards simply suck. It auto-corrects everything, ruining any code I type.</p>
  
  <p>An yet further, I woke up this morning with an entirely new algorithm that uses virtual no extra memory at all and does not require checking every item in the array. I posted it as an answer below.</p>