title: How to perform Cumulative count cut analysis without taking all the numbers in the memory?
body: <p>I saw an answer on quora to find the median without taking all the number
  <a href="https://qr.ae/TWndxb" rel="nofollow noreferrer">Quora Answer</a></p>
  
  <blockquote>
    <p>How can you calculate the median of a large array of integers without
    keeping all the values in memory? </p>
    
    <p><a href="https://www.quora.com/What-is-the-distributed-algorithm-to-determine-the-median-of-arrays-of-integers-located-on-different-computers" rel="nofollow noreferrer">https://www.quora.com/What-is-the-distributed-algorithm-to-determine-the-median-of-arrays-of-integers-located-on-different-computers</a>    </p>
    
    <p>Dhruv Matani Dhruv Matani, Kuriosity Answered Oct 18, 2012</p>
    
    <p>Actually, Anders Kaseorg covers the case in which O(1) additional memory is used to compute the  median. I'll try to explain the general idea of the
    solution.   </p>
    
    <p>Quickselect:</p>
    
    <ol>
    <li><p>Select a RANDOM number 'Z' (random being key here). Just to be sure,  call rand() a couple of times to make sure it's random. (no I
    was just  kidding).</p></li>
    <li><p>Pick out all number less than Z into one array and numbers >= Z into another.</p></li>
    <li><p>If the set with the numbers &lt; Z has cardinality &lt; N/2, then the  median is the N/2 - |Z| ranked element in the other set.</p></li>
    <li><p>If the set with the numbers >= Z has cardinality &lt; N/2, then the median is the N/2 ranked in the current set.</p></li>
    <li><p>3 &amp; 4 can be done recursively.</p></li>
    </ol>
    
    <p>Now,  suppose, we don't have extra memory to store these sets, we can
    use  <a href="https://gregable.com/2007/10/reservoir-sampling.html" rel="nofollow noreferrer">Reservoir Sampling</a> to select a random  number
    from a list. We skip over elements that we know are not in the 
    required range. i.e. We always have a range (a,b) between which if the
    number falls, we consider to be a part of the list.</p>
  </blockquote>
  
  <p>I have a java code which does cumulative sum and finds the required values. But, the number of values is in the order of 1000000s (it is an image) and it sometimes leads to <code>OutOfMemory error: Java Heap space is out of memory</code>, which is unreliable.</p>
  
  <pre class="lang-java prettyprint-override"><code>/**
   * author Tarun
   * This code is not extensible and cannot be used as getting cumulative standalone.
   * Please check the working before use.
   * You need to use the max first to get a proper min value.
   * Threshold isn't adjustable.
   */
  package imagedisplay.imgops;
  
  import java.util.logging.Level;
  import java.util.logging.Logger;
  import java.util.stream.DoubleStream;
  import java.util.stream.IntStream;
  import java.util.stream.Stream;
  
  public class Cumulative 
  {
      static float max = 0.0f, min = 0.0f;
  
      public static float max(float[][] a,int nrow, int ncol)
      {
          System.gc();
          double arr[];//=new double[nrow*ncol];
          int total=nrow*ncol;
          int mul1 = (int)Math.ceil(total*0.98);
          int mul2 = (int)Math.ceil(total*0.02);
          try
          {
              DoubleStream mapToDouble[] = new DoubleStream[nrow];
              for(int i=0;i&lt;nrow;i++){
                  final float row_a[] = a[i];
                  mapToDouble[i] = IntStream.range(0, ncol).parallel().mapToDouble(x-&gt;{
                      return Float.isNaN(row_a[x])?0:row_a[x];});
              }
              System.gc();
              arr = Stream.of(mapToDouble).parallel().flatMapToDouble((doubleStream)-&gt;doubleStream).sorted().toArray();
              System.gc();
              max = (float)arr[mul1];
              min = (float)arr[mul2];
          }
          catch(OutOfMemoryError ex)
          {
              Logger.getLogger(Cumulative.class.getCanonicalName()).log(Level.SEVERE,"Calclulation of Cumulative Count Cut failed.",ex);
          }
          return max;
      }
  
      public static float min(float[][] a,int nrow, int ncol)
      {
          return min;
      }
  }
  </code></pre>
  
  <p>I tried using <a href="http://www.mapdb.org/" rel="nofollow noreferrer">MapDB</a>, but it turned out to be very slow. Is there a way similar to above mentioned median which can be done with values on the disk, to do the cumulative count cut?</p>