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

スレッドを使用すると、スレッド間通信の複雑さが大幅に増すという代償を払って、アプリケーションが一定の小さな要因で高速化されます。より優れたアルゴリズムがあれば、桁違いに節約できます。したがって、問題を解決する二次二次アルゴリズムが実際に存在しないことを最初に確認することを強くお勧めします。

おそらく、解決しようとしている問題と現在の解決策について詳しく説明していただければ、ここで支援できます。

編集：よかった、より良いアルゴリズムを見つけることはまったく難しいことではありません：

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 に答える
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 に答える
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 に答える