平行中值滤波器

Question

所以我一直在研究中值滤波器*（比较顺序到并行，因为我学习如何并发编码），但并行版本无限期地运行一个大的输入（大约100k;它运行罚款少）。

本质上，代码需要一个文件，在给定的窗口大小的情况下对其进行过滤，然后将其写入新文件。并行编程的新手，所以当涉及到什么可能是错误的时候，我有点失落。

//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) < SEQUENTIAL_CUTOFF) { 

      for (int a = lo; a < hi; a++) { 


       for (int i = 0; i < length; i++) { 
        if (i < window || i >= 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 < 3 || window > 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   
    } 
} 

做这顺序似乎工作（第二下约1 000 000元），可是我的并发版本需要近4只是做10 000元。正如我所说，全新的并行编程，所以我很迷茫。是否有一种方法可以并行执行中位数过滤器，而我错过了？ （*中值过滤器=取数组的某个窗口，对它们进行排序，并将该索引处的原始元素替换为排序子数组的中值;例如：2，80，6，3，1结果在图2，6,6，3，1）

*例如：

Taking in this file: 
5.0 
13.2 
-2.6 
22.3 
12.4 
-0.21 
23.1 
-0.2454 

这将读取到一个数组[5.0，13.2，-2.6，22.3，12.4，-0.21， 23.1，-0.2454] 窗口大小为3，为了适用于过滤，一个元素必须先有n个元素，后面有n个元素，其中n =（窗口-1）/ 2;因此，在窗口= 3的情况下，元素的两侧必须有1个元素。如果它不满足该条件，则该元素将按原样进行。

因此，5.0将保持，因为它没有一个元素之前。但13.2满足条件 - 因此，一个子数组取[5.0，13.2，-2.6]。然后对该数组进行排序（使用.sort（）：[-2.6，5.0，13.2]），然后中位数取为5.0。随后在最终数组中使用5.0替换13.2，现在看起来像[5.0，5.0，...]。

接下来它移动到-2.6 - 它有一个元素之前和之后，所以子数组[-2.6,22.3,12.4]被采取，排序，并且12.4的中值被添加到最终数组：[5.0，5.0，12.4，...]。它重复这个过程，直到原始数组中的所有元素都被访问过。然后它将最后一个数组写入一个文件，但这不是特别相关的（除非这可以以某种方式并行完成 - 我怀疑，但正如我所说：这里是完整的noob）。

Answer 1

您正在处理的是完全平行的。事实上，您可以为每个元素的子集计算中值滤波器（因为您不会在计算中更改原始数组的内容）。所以，是的，你可以同时做到这一点。

说这话的，即使我不知道RecursiveAction的所有细节，我会说，你错过了整个线程一部分。我检查了一下，任何递归动作都应该由ForkJoinPool类调​​用。这个人然后处理线程和叉/加入他们。

Furthmore，右分裂操作和左（有两个不同的电话），您需要叉和后来加入两者。

我希望这样的事情有一个工作的配置：

public class SecondMedianFilter extends RecursiveAction { 
... 

protected void compute() { 

    result = new float[length]; 

    if ((hi - lo) < SEQUENTIAL_CUTOFF) { 

     for (int a = lo; a < hi; a++) { 


      for (int i = 0; i < length; i++) { 
       if (i < window || i >= 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(); 
     //CODE CHANGES FROM HERE 
     right.fork(); 
     //right.compute(); <- IS IMPLICIT IN THE FORK 
     left.join(); 
     right.join(); 
     //TO HERE 
    } 
} 


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 < 3 || window > 21 || window % 2 == 0) { 
     System.out.println("Window size error."); 
    } else { 
     // CODE CHANGES FROM HERE 
     ForkJoinPool pool = new ForkJoinPool(); // WHO HANDLES THE THREADS 
     SecondMedianFilter smf = new SecondMedianFilter(inArray, window, 0, inArray.length); 
     //smf.compute(); <- DUTY OF THREAD POOL 
     pool.invoke(smf); // START OF PROCESSING 
     outIntArray = smf.getRes(); 


     // loops through outIntArray and writes to file. 
    }//end main   
} 

}

我会为您提供两个环节，他们会解释不够详细，整个过程是如何工作的（其中一个显示了并行和顺序方法）。

http://www.concretepage.com/java/jdk7/example-of-recursiveaction-in-java

http://www.logicbig.com/how-to/java/fork-and-join-recursive-action/

编辑 我没有检查你是如何算法的工作（我期望它拆分数组中的两个上，当涉及到的约束情况下），所以我刚刚根据你写的内容添加了一些代码。