3

サイズが1000から10000（1k .. 10k）の配列があります。各要素はint64です。私の仕事は、配列の2つの最小要素、最小要素と残りの要素から最小要素を見つけることです。

IntelCore2またはCorei7用のC++で可能な限り最速のシングルスレッドコードを取得したい（CPUモードは64ビット）。

この関数（配列から2つを最小にする）はホットスポットであり、反復回数が非常に多い2つまたは3つのforループにネストされています。

現在のコードは次のようなものです。

int f()
{
    int best; // index of the minimum element
    int64 min_cost = 1LL << 61;
    int64 second_min_cost = 1LL << 62;
    for (int i = 1; i < width; i++) {
     int64 cost = get_ith_element_from_array(i); // it is inlined
     if (cost < min_cost) {
        best = i;
        second_min_cost = min_cost;
        min_cost = cost;
     } else if (cost < second_min_cost) {
        second_min_cost = cost;
     }
    }
    save_min_and_next(min_cost, best, second_min_cost);
}
4

7 に答える 7

8

見てpartial_sort、nth_element

std::vector<int64_t> arr(10000); // large

std::partial_sort(arr.begin(), arr.begin()+2, arr.end());
// arr[0] and arr[1] are minimum two values

2番目に低い値のみが必要な場合は、nth_elementが最適です。

于 2011-10-17T12:08:36.447 に答える
5

ifを反転してみてください：

if (cost < second_min_cost) 
{ 
    if (cost < min_cost) 
    { 
    } 
    else
    {
    }
}

そして、おそらくint64の最大値を使用してmin_costとsecond_min_costを同じ値で初期化する必要があります（またはqbert220の提案を使用することをお勧めします）

于 2011-10-17T12:14:17.333 に答える
3

いくつかの小さなこと（すでに起こっているかもしれませんが、私が推測する価値があるかもしれません）。

  1. ループを少し展開します。たとえば、8のストライドで繰り返し（つまり、一度にキャッシュラインを）、本体の次のキャッシュラインをプリフェッチしてから、8つのアイテムを処理します。多くのチェックを回避するには、終了条件が8の倍数であることを確認し、残ったアイテム（8未満）をループの外側で処理する必要があります-展開...

  2. 興味のないアイテムについては、ボディで2つのチェックを行っていますが、1つにトリミングできますか？つまり、costが未満の場合は、同様second_minにチェックminします。それ以外の場合は、気にする必要はありません。

于 2011-10-17T12:17:47.693 に答える
2

結果を変更する必要がある唯一の条件であるため、最初にsecond_min_costを確認することをお勧めします。このようにして、メインループに2つではなく1つのブランチを取得します。これはかなり役立つはずです。

それ以外に、最適化することはほとんどありません。あなたはすでに最適に近づいています。展開すると役立つ場合がありますが、このシナリオで大きな利点が得られるとは思えません。

だから、それはなります：

int f()
{
    int best; // index of the minimum element
    int64 min_cost = 1LL << 61;
    int64 second_min_cost = 1LL << 62;
    for (int i = 1; i < width; i++) {
    int64 cost = get_ith_element_from_array(i); // it is inlined
    if (cost < second_min_cost)
    {
      if (cost < min_cost) 
      {
        best = i;
        second_min_cost = min_cost;
        min_cost = cost;
      } 
      else second_min_cost = cost;
    }
    save_min_and_next(min_cost, best, second_min_cost);
}
于 2011-10-26T14:04:03.857 に答える
1

そこにあるものはO(n)、ランダムデータに最適です。つまり、あなたはすでに最速です。

これを改善できる唯一の方法は、配列に特定のプロパティを与えることです。たとえば、配列を常に並べ替えたままにするか、ヒープにすることです。

于 2011-10-17T12:02:48.723 に答える
1

良い点は、アルゴリズムが数値を1回スキャンすることです。あなたは最適です。

速度低下の重要な原因は、要素の配置方法にある可能性があります。それらが配列内にある場合、つまり、すべての要素が連続しているC配列（またはC ++ベクトル）を意味し、それらを前方にスキャンすると、メモリに関しても最適になります。そうでなければ、あなたはいくつかの驚きを持つ可能性があります。たとえば、要素がリンクリストにある場合、またはスキャッターが収集されている場合、メモリアクセスにペナルティが課せられる可能性があります。

于 2011-10-17T12:08:14.020 に答える
1

不必要なキャッシュミスが発生しないように、配列の読み取りが正しく動作することを確認してください。

このコードは、配列の読み取りが単純であると仮定すると、おそらく最新のCPUの帯域幅に非常に近いはずです。CPU最適化の余地があると思われる場合は、プロファイリングおよび/または計算する必要があります。

于 2011-10-17T12:10:29.647 に答える