title: Reduce memory complexity in a bootstrap algorithm
body: <p>I wrote this function for bootstrapping. </p>
  
  <pre><code>from __future__ import division
  import numpy as np
  
  
  def bootstrap(array):
      """
      :type array: np.ndarray
      :param array: a 1D NumPy array, where array[i] is the count of the
                    i-th item.
      :rtype: np.ndarray
      """
      size = int(array.sum())
      probabilities = array / size
      values = np.arange(arr.shape[0])
      bins = np.cumsum(probabilities)
      result = np.zeros(arr.shape[0])
  
      for val in values[np.digitize(np.random.random_sample(size), bins)]:
          result[val] += 1
  
      return result
  </code></pre>
  
  <p>I don't like the fact, that this line <code>values[np.digitize(np.random.random_sample(size), bins)]</code> creates the array of size <code>array.sum()</code>. I'd like to keep the memory complexity <code>O(n)</code>, where <code>n</code> is the <code>array</code>'s length. How can I make it lazier without significant speed sacrifices? </p>
  
  <p>P.S.
  In case you want to point me at the slow <code>for</code>-loop, I've Cythonised the real version to remove the slow Python loop. </p>