title: Parallel Median Filter
body: <p>So I've been working on a median filter* (comparing sequential to parallel, since I'm learning how to code concurrently), but the parallel version runs indefinitely for a large input (about 100k; it runs fine for less).  </p>
  
  <p>In essence, the code takes in a file, filters it given a certain window size, then writes it to a new file. New to parallel programming, so I'm kind of lost when it comes to what might be wrong here.</p>
  
  <pre><code>//import everything
  
  public class SecondMedianFilter extends RecursiveAction {
      float[] numbers;
      static int filter;
      int window;
      int length;
      int lo;
      int hi;
  
      static final int SEQUENTIAL_CUTOFF = 500;
  
  
      float[] outArray;
  
      public SecondMedianFilter(float[] numbers, int filter, int lo, int hi) {
          this.numbers = numbers;
          this.filter = filter;
          this.lo = lo;
          this.hi = hi;
          length = numbers.length;
          window = (filter - 1) / 2;
      }
  
      public float[] getRes() {
          return result;
      }
  
  
      protected void compute() {
  
          result = new float[length];
  
          if ((hi - lo) &lt; SEQUENTIAL_CUTOFF) {
  
              for (int a = lo; a &lt; hi; a++) {
  
  
                  for (int i = 0; i &lt; length; i++) {
                      if (i &lt; window || i &gt;= length - window) {
                          result[i] = numbers[i];
                      } else {
                          float[] subArray = Arrays.copyOfRange(numbers, i - window, i + window + 1);
                          Arrays.sort(subArray);
                          float median = subArray[(subArray.length / 2)];
                          result[i] = median;
  
                      }
                  }
  
              }
          } else {
  
              SecondMedianFilter left = new SecondMedianFilter(filtered, filter, lo, (hi + lo) / 2);
              SecondMedianFilter right = new SecondMedianFilter(filtered, filter, (hi + lo) / 2, hi);
              left.fork();
              right.compute();
              left.join();
          }
      }
  
  
      public static void main(String[] args) {
          //reads in a file, processes each line into an array of floats that
          // I call inArray, which gets filtered into outIntArray
  
  
          float[] outIntArray = new float[inArray.length];
  
          if (window &lt; 3 || window &gt; 21 || window % 2 == 0) {
              System.out.println("Window size error.");
          } else {
  
              SecondMedianFilter smf = new SecondMedianFilter(inArray, window, 0, inArray.length);
              smf.compute();
              outIntArray = smf.getRes();
  
  
              // loops through outIntArray and writes to file.
          }//end main           
      }
  }
  </code></pre>
  
  <p>Doing it sequentially appears to work (under a second for about 1 000 000 elements), and yet my concurrent version takes almost 4 just to do 10 000 elements. As I said, brand new to parallel programming, so I'm quite lost. Is there an approach to doing a median filter in parallel that I'm missing?</p>
  
  <p>(* Median filter = take a certain window of the array, sort them and replace the original element at that index with the median of the sorted sub-array; for example: 2, 80, 6, 3, 1 results in 2, 6, 6, 3, 1.)</p>
  
  <p>*For example: </p>
  
  <pre><code>Taking in this file: 
  5.0
  13.2
  -2.6
  22.3
  12.4
  -0.21
  23.1
  -0.2454
  </code></pre>
  
  <p>It'll read that into an array [5.0, 13.2, -2.6, 22.3, 12.4, -0.21, 23.1, -0.2454]
      With a window size of, say, 3.  In order to be applicable for filtering, an element must have n elements before it and n elements after it, where n = (window - 1)/2; hence, an element, in the case of window = 3, must have 1 element on either side of it.  If it doesn't satisfy that condition, that element is taken as-is. </p>
  
  <p>So 5.0 will remain, given that it doesn't have an element before it. But 13.2 satisfies the condition - hence, a sub-array is taken [5.0, 13.2, -2.6]. This array is then sorted (using .sort(): [-2.6, 5.0, 13.2]), then the median is taken to be 5.0. 13.2 is subsequently replaced with 5.0 in the final array, which now looks like [5.0, 5.0,...]. </p>
  
  <p>Next it moves on to -2.6 - it has an element before and one after, so the sub-array [-2.6, 22.3, 12.4] is taken, sorted, and the median of 12.4 is added to the final array: [5.0, 5.0, 12.4,...]. It repeats this process until all elements in the original array have been visited. It then writes the final array to a file, but this isn't particularly relevant (unless this can be done in parallel somehow - which I doubt, but as I said: complete noob here). </p>