2

我有一个应用程序，它会随着时间的推移在图表上创建点。虽然我正在收集 x 轴上每个点的数据，但我还必须执行递归查找，这实际上意味着我在另一个循环中有一个循环。这不是很好地缩放。我没有看到很多在迭代中使用“分而治之”解决方案的例子。我正在考虑使用 Java 的 Executor 并发框架在它自己的线程中运行每个循环，等待答案，收集结果并返回它们。我得到的初步测试结果似乎并没有那么快。我知道我应该展示一些代码，但我首先想知道的是，与我可能不熟悉的更好的方法相比，这种方法是否具有优点。提前致谢！

添加一些 groovyish/javaish 伪代码来帮助思考这个问题：

class Car {
    id
    model 
    make
    weight
}

for (number in listOfImportantCarIDs) {
    Car car = carsMap.get(number) // find the car we care about
    String maker = car.make //get it's 'parent' 

    // get amount of all related cars
    Iterator<Car> allcars = carsMap.values().iterator();
    while (allcars.hasNext()) {
        Car aCar = alldocs.next();
        if (maker.equals(aCar.make)) {
            totalCarCount++;  // increment total related cars 
            BigDecimal totalWeightofAllCars = totalWeightofAllCars.add(aCar.getWeight()); // add weight to total

            // a ghetto cache to prevent double  counting
            countedMaufacturers.add(make); 
        }     
    }
}
4

7 回答 7

2

如果计算每个 x 值的 y 值的任务对于每个 x 值都是完全原子的，那么我认为这非常适合执行程序服务。大多数性能问题只需要衡量，即使在对解决方案进行了大量推理之后。CPU 绑定问题的最佳线程数是 p 或 p+1，请记住这一点。

你看过动态编程方法吗？它适用于您的问题吗？本质上，递归意味着您要一遍又一遍地解决相同的问题，但输入值要小一些。当运行相同递归算法的多次迭代时，程序往往会重新解决相同的确切问题。相反，动态编程方法可能会将解决方案存储在缓存中，并在第二次计算解决方案之前引用缓存。

不知道你的确切问题，很难给出准确的答案。

于 2010-08-27T20:30:10.340 回答
2

这取决于是什么让你的循环变慢。他们是否在执行数据库查询？访问硬盘？否则会做一些导致他们等待外部 I/O 操作的事情吗？在这种情况下，你最好的办法是开始添加线程，直到你不再看到它们的回报，你基本上必须调整它。

如果它们只是因为 Java 中的内存中发生原始处理而变慢，那么您可以尝试在您的机器上为每个 CPU 内核添加一个线程，但除此之外可能不会看到太多好处。

于 2010-08-27T20:30:49.083 回答
2

使用线程将通过一些小的常数因子加速您的应用程序，但代价是显着增加了线程间通信的复杂性。如果存在更好的算法，那可以为您节省几个数量级。因此，我强烈建议您首先验证确实没有二次算法来解决您的问题。

也许如果您详细说明了您要解决的问题以及您当前的解决方案，我们可以在这里提供帮助。

编辑：天哪，找到一个更好的算法一点也不难：

for (Car car : cars {
    Stats s = stats.get(car.maker);
    if (s == null) {
        s = new Stats();
        stats.put(car.maker, s);
    }
    stats.count++;
    stats.totalWeight+=car.weight;
}

for (Car car in importantCars) {
    stats.get(car.maker);
}

对于每辆重要的汽车，真的没有必要重复所有汽车，只是为了找到那些具有相同制造商的汽车......

于 2010-08-27T20:40:54.260 回答
1

如果您的“源”数据没有被您的算法修改，或者每次迭代仅对其自己的数据进行操作（不会更改附近的数据），它可以在双核上为您提供（最大）2 倍的速度提升。

这不是一个很好的解决方案，并且随着当前解决方案的时间增长，这将增长 1/2，如果您处于双嵌套循环中，这仍然是相当昂贵的。O(X^2/2) 仍然几乎等于 O(X^2)。

如果你能找到一种方法来优化你的算法，这种方法具有更高的真正成功潜力，而且更不可能花费大量时间来修复错误。

于 2010-08-27T20:35:15.927 回答
0

可以并行计算沿 X 轴的每个点吗？如果是这样，那是您通过多线程提高性能的机会。

Fork-Join框架将使这种程序变得简单。您可以获得早期访问版本，或者在某种程度上自己模仿它。

于 2010-08-27T20:37:50.553 回答
-1

“另一个循环内的循环”应该响铃;）。外部循环总是在等待内部循环。所以这是一个串行执行，使用线程不会改变一点。除非每个循环都将结果写入中央服务，否则您的 x 轴上的后续事件（循环）可以查询该中央服务。所以服务将是有状态的......

于 2010-08-27T20:32:20.330 回答
-2

我不认为并发可以使您的应用程序更快。它可以帮助您在应用程序中运行多个任务，但不会使它们更快。

我的经验：尝试摆脱递归调用，这是使应用程序更快的最佳方法。

于 2010-08-27T20:25:46.227 回答