並列化ソート済み配列をバイナリ検索ツリー関数に変換する

Question

ソート済み配列をJavaのBSTプログラムに並列化しようとしています。私の関数はDivide and Conquerの仕方で実行されるので、私はそれが並列化可能だと信じていますが、実装には固執しています。あなたがスレッドをここに適用する方法を教えてもらえると非常に役に立ちます。

ありがとうございます！

// Definition for a binary tree node. 
public class TreeNode { 
    int val; 
    TreeNode left; 
    TreeNode right; 
    TreeNode(int x) { val = x; } 
} 

public class Solution { 
    public TreeNode sortedArrayToBST(int[] nums) { 
     if (nums == null) { 
      return null; 
     } 
     return sortedArrayToBST(nums, 0, nums.length - 1); 
    } 

    private TreeNode sortedArrayToBST(int[] nums, int start, int end) { 
     if (start > end) { 
      return null; 
     } 

     int mid = start + (end - start)/2; 
     TreeNode node = new TreeNode(nums[mid]); 
     node.left = sortedArrayToBST(nums, start, mid - 1); 
     node.right = sortedArrayToBST(nums, mid + 1, end); 

     return node; 
    } 
} 

Answer 1

アンドレアスはコメントで示唆したように、あなたは、バイナリツリーの作成を並列化するためにforkjoinpoolを使用することができますが

class TreeNode { 
    int val; 
    TreeNode left; 
    TreeNode right; 
    TreeNode(int x) { val = x; } 
} 

class Task extends RecursiveTask<TreeNode> 
{ 
    int[] nums; 
    int start,end; 
    public Task(int[] nums,int start,int end) 
    { 
     this.nums =nums; 
     this.start = start; 
     this.end = end; 
    } 
    protected TreeNode compute() 
    { 
     if(start>end) 
     { 
      return null; 
     } 
     int mid = start + (end - start)/2; 
     TreeNode node = new TreeNode(nums[mid]); 
     Task leftSubTask = new Task(nums,start,mid-1); 
     Task rightSubTask = new Task(nums,mid+1,end); 
     leftSubTask.fork(); 
     rightSubTask.fork(); 
     node.left = leftSubTask.join(); 
     node.right = rightSubTask.join(); 
     return node; 

    } 
} 
class Main 
{ 
    public static void main (String[] args) throws java.lang.Exception 
    { 
     // your code goes here 
     int nums[] = {1,5,7,8,9}; 
     Task task = new Task(nums,0,nums.length-1); 
     ForkJoinPool forkJoinPool = new ForkJoinPool(4); 
     TreeNode root = forkJoinPool.invoke(task); 
    } 
}