代码之家  ›  专栏  ›  技术社区  ›  Vinny

并发方法是加速长迭代的好方法吗?

  •  2
  • Vinny  · 技术社区  · 14 年前

    我有一个应用程序,做一个迭代,以创建一个图表上的点随着时间的推移。 当我收集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); 
            }     
        }
    }
    
    7 回复  |  直到 14 年前
        1
  •  2
  •   meriton    14 年前

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

    如果您详细说明您正在尝试解决的问题和您当前的解决方案,我们可以在此提供帮助。

    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);
    }
    

    对于每一辆重要的汽车,实在没有必要反复研究所有的汽车,只是为了找到那些拥有相同制造商的汽车。。。

        2
  •  2
  •   Tim Bender    14 年前

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

    如果不知道你的确切问题,就很难给出确切的答案。

        3
  •  2
  •   Affe    14 年前

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

        4
  •  1
  •   Bill K    14 年前

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

        5
  •  0
  •   erickson    14 年前

    Fork-Join 框架将使这种程序变得简单。你可以得到一个早期的access版本,或者在某种程度上模仿它。

        6
  •  -1
  •   cafebabe    14 年前

        7
  •  -2
  •   mhshams    14 年前

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

    我的经历: 尝试摆脱递归调用,这是使应用程序更快的最好方法。