当前位置: 首页 > 面试题库 >

与递归函数并行编程?

陆雅志
2023-03-14
问题内容

问题的背景:我正在尝试编写一个难题解决方案算法,该算法利用多核处理器和并行处理的优势。但是,理想/最简单的解决方案是简单的递归函数。

分解解决方案以同时利用并行处理 递归函数的最佳方法是什么?

下面的代码是一种简单的难题解决算法的解决方案(它可以正常工作)。这个例子中的难题很简单-有14个插槽,编号为1-14。每个拼图都有一个唯一的ID,一个告诉您可以在哪里开始和停止的范围(例如6-8表示它

适合6-8插槽)和一个价格。该算法尝试找到使解决方案的价格最大化的解决方案。一个插槽只能容纳1个,并且可以使用空插槽。该解决方案将告诉您使用了哪些部件以及总成本。(为简单起见,还假设必须填充插槽1)。

我尝试将并行性和递归相结合的解决方案是在下面使用的方法:为每个使用插槽1的部件创建一个Task,然后在Task中以递归方式查看其余部件,将它们分配到剩余空间中,同时使成本最大化。这是最好的解决方案(可能不是,这就是为什么我在这里)。如何改善?使用并行/递归解决方案时还有其他好的建议吗?

尽管简单的递归在这里可以很好地工作,但是我正在用一个具有200个插槽和5000个拼图的拼图来描述这种运行方式。

这也是此示例的解决方案:

ID=1 Price=10.0 Range=1-6
ID=12 Price=8.0 Range=9-14
ID=15 Price=3.0 Range=7-8


public class Puzzle
{

    public PuzzleSet calculateResults(PuzzleSet input) throws Exception
    {   
        System.out.println(System.currentTimeMillis());
        PuzzleSet results = getPriceMultithread((PuzzleSet)SerializationUtils.clone(input));
        System.out.println(System.currentTimeMillis());
        return results;
    }

    private PuzzleSet getPriceMultithread(PuzzleSet input) throws Exception
    {
        PuzzleSet initial = input.startsAtPoint(1);

        ExecutorService exec = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors()+1);
        Collection<Callable<PuzzleSet>> tasks = new ArrayList<Callable<PuzzleSet>>();

        for (int i=0; i<initial.size(); i++)
        {
            final PuzzleData d = initial.get(i);
            final PuzzleSet start = input.higherThan(initial.get(i).rangeUpper);
            tasks.add(new Callable<PuzzleSet>() {
                public PuzzleSet call() {
                    PuzzleSet s = new PuzzleSet();
                    s.add(d);
                    s.addAll(getPrice(start));
                    return s;
                }
            });
        }

        List<Future<PuzzleSet>> results = exec.invokeAll(tasks);
        PuzzleSet max = new PuzzleSet();
        double maxD = 0.0;
        for (int i=0; i<results.size(); i++)
        {
            PuzzleSet temp = results.get(i).get();
            double sum = temp.sum();
            if (sum > maxD)
            {
                maxD = sum;
                max = temp;
            }
        }
        return max;
    }

    private PuzzleSet getPrice(PuzzleSet input)
    {
        if (input == null || input.size() == 0)  return new PuzzleSet();

        double maxD = 0.0;
        PuzzleSet max = new PuzzleSet();
        for (int i=0; i<input.size(); i++)
        {
            PuzzleSet vs = input.higherThan(input.get(i).rangeUpper);
            PuzzleSet s = getPrice(vs);
            double d = s.sum();
            double pTemp = input.get(i).price + d;
            if (pTemp > maxD)
            {
                maxD = pTemp;
                s.add(input.get(i));
                max = s;
            }
        }       
        return max;
    }

    public static void main(String arg[]) throws Exception
    {
        PuzzleSet s = new PuzzleSet();

        PuzzleData v1 = new PuzzleData();
        v1.rangeLower = 1;
        v1.rangeUpper = 6;
        v1.price = 10;
        v1.ID = 1;
        s.add(v1);

        PuzzleData v2 = new PuzzleData();
        v2.rangeLower = 7;
        v2.rangeUpper = 11;
        v2.price = 0;
        v2.ID = 2;
        s.add(v2);

        PuzzleData v3 = new PuzzleData();
        v3.rangeLower = 12;
        v3.rangeUpper = 14;
        v3.price = 7;
        v3.ID = 3;
        s.add(v3);

        PuzzleData v5 = new PuzzleData();
        v5.rangeLower = 7;
        v5.rangeUpper = 9;
        v5.price = 0;
        v5.ID = 4;
        s.add(v5);

        PuzzleData v6 = new PuzzleData();
        v6.rangeLower = 10;
        v6.rangeUpper = 14;
        v6.price = 5;
        v6.ID = 5;
        s.add(v6);

        PuzzleData v7 = new PuzzleData();
        v7.rangeLower = 1;
        v7.rangeUpper = 3;
        v7.price = 5;
        v7.ID = 6;
        s.add(v7);

        PuzzleData v8 = new PuzzleData();
        v8.rangeLower = 4;
        v8.rangeUpper = 9;
        v8.price = 0;
        v8.ID = 7;
        s.add(v8);

        PuzzleData v10 = new PuzzleData();
        v10.rangeLower = 1;
        v10.rangeUpper = 5;
        v10.price = 3;
        v10.ID = 8;
        s.add(v10);

        PuzzleData v11 = new PuzzleData();
        v11.rangeLower = 6;
        v11.rangeUpper = 11;
        v11.price = 2;
        v11.ID = 9;
        s.add(v11);

        PuzzleData v12 = new PuzzleData();
        v12.rangeLower = 12;
        v12.rangeUpper = 14;
        v12.price = 7;
        v12.ID = 10;
        s.add(v12);

        PuzzleData v14 = new PuzzleData();
        v14.rangeLower = 4;
        v14.rangeUpper = 8;
        v14.price = 1;
        v14.ID = 11;
        s.add(v14);

        PuzzleData v15 = new PuzzleData();
        v15.rangeLower = 9;
        v15.rangeUpper = 14;
        v15.price = 8;
        v15.ID = 12;
        s.add(v15);

        PuzzleData v16 = new PuzzleData();
        v16.rangeLower = 1;
        v16.rangeUpper = 5;
        v16.price = 3;
        v16.ID = 13;
        s.add(v16);

        PuzzleData v17 = new PuzzleData();
        v17.rangeLower = 6;
        v17.rangeUpper = 8;
        v17.price = 1;
        v17.ID = 14;
        s.add(v17);

        PuzzleData v18 = new PuzzleData();
        v18.rangeLower = 7;
        v18.rangeUpper = 8;
        v18.price = 3;
        v18.ID = 15;
        s.add(v18);

        PuzzleSet x = new Puzzle().calculateResults(s); 
        for (int i=0; i<x.size(); i++)
        {
            System.out.println(x.get(i));
        }

    }
}

public class PuzzleData implements Serializable
{
    public int rangeLower;
    public int rangeUpper;
    public int ID;
    public double price;

    public String toString()
    {
        return "ID=" + ID + " Price=" + price + " Range=" + rangeLower + "-" + rangeUpper;
    }
}

public class PuzzleSet extends ArrayList<PuzzleData> implements Serializable
{
    public PuzzleSet higherThan(int lowBound)
    {
        PuzzleSet s = new PuzzleSet();
        for (int i=0; i<size(); i++)
        {
           if (get(i).rangeLower > lowBound)
               s.add(get(i));
        }
        return s;
    }

    public PuzzleSet startsAtPoint(int point)
    {
        PuzzleSet s = new PuzzleSet();
        for (int i=0; i<size(); i++)
        {
           if (get(i).rangeLower == point)
               s.add(get(i));
        }
        return s;
    }

    public double sum()
    {
        double sum = 0.0;
        for (int i=0; i<size(); i++)
            sum += get(i).price;
        return sum;
    }

    public String toString()
    {
        StringBuffer b = new StringBuffer();
        for (int i=0; i<size(); i++)
        {
            b.append(get(i).toString());
        }
        return b.toString();
    }
}

问题答案:

JSR-166Y旨在通过关注线程协调来促进Java
7中并行递归的实现。您可能会发现他们的讨论,代码和论文(尤其是Doug Lea的论文A Java Fork / Join
Framework)很有用。



 类似资料:
  • 问题 你想在一个函数中调用相同的函数。 解决方案 使用一个命名函数: ping = -> console.log "Pinged" setTimeout ping, 1000 若为未命名函数,则使用 @arguments.callee@: delay = 1000 setTimeout((-> console.log "Pinged" setTimeout arg

  • 在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。 举个例子,我们来计算阶乘n! = 1 x 2 x 3 x ... x n,用函数fact(n)表示,可以看出: fact(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fact(n-1) x n 所以,fact(n)可以表示为n x fact(n-1),

  • 在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。 举个例子,我们来计算阶乘n! = 1 x 2 x 3 x ... x n,用函数fact(n)表示,可以看出: fact(n)=n!=1\times2\times3\times\cdot\cdot\cdot\times(n-1)\times n=(n-1)!\times n=fact(n-1)\times n

  • 我还不太理解递归,我有一些作业我不能解决。有人有主意吗? 任务1:实现一个int方法max(int[]arr,int i),该方法返回arr中所有元素的最大值和索引 这是我迄今为止的代码: 实际上它是有效的,但它的风格很差,所以我的问题是:如果没有私有静态int max,我如何实现递归方法?我不允许向该方法添加第三个参数。 任务2:实现一个布尔方法包含值(int[]arr,int val),如果a

  • Go语言支持递归函数,这里是一个经典的斐波拉切数列的列子。 package main import "fmt" // fact函数不断地调用自身,直到达到基本状态fact(0) func fact(n int) int { if n == 0 { return 1 } return n * fact(n-1) } func main() { fmt.

  • Scala 函数 递归函数在函数式编程的语言中起着重要的作用。 Scala 同样支持递归函数。 递归函数意味着函数可以调用它本身。 以上实例使用递归函数来计算阶乘: object Test { def main(args: Array[String]) { for (i <- 1 to 10) println(i + " 的阶乘为: = " + factori