0

ソートされた配列で最も近い double 要素を見つける C++ ルーチンを作成しました。スピードアップする方法はありますか？

降順でソートされているreversed場合、 boolean の値に基づいて 2 つの分岐があります。reversed

 void findNearestNeighbourIndex_new(real_T value, real_T* x, int_T x_size, int_T& l_idx)
{
    l_idx = -1;

    bool reversed= (x[1] - x[0] < 0);

    if ((!reversed&& value <= x[0]) 
                  || (reversed&& value >= x[0])){ 
        // Value is before first position in x
        l_idx = 0;
    }
    else if ((!reversed&& value >= x[x_size - 1]) 
                    || (reversed&& value <= x[x_size - 1])){ 
        // Value is after last position in x
        l_idx = x_size - 2;
    }
    else // All other cases
    {
        if (reversed)
        {
            for (int i = 0; i < x_size - 1; ++i)
            {
                if (value <= x[i] && value > x[i + 1])
                {
                    l_idx = i;
                    break;
                }
            }
        }
        else{
            for (int i = 0; i < x_size - 1; ++i)  
            {
                if (value >= x[i] && value < x[i + 1])
                {
                    l_idx = i;
                    break;
                }
            }
        }   
    }
}

配列がソートされているまさにこのケースでは、より良い方法がわかりません。したがって、プロファイリングでは、比較if (value <= x[i] && value > x[i + 1])が高価であることがわかります。

編集

lower_bound() で試した

std::vector<real_T> x_vec(x, x + x_size);

l_idx = std::upper_bound(x_vec.begin(), x_vec.end(), value) - x_vec.begin() - 1;
4

4 に答える 4

12

std::lower_boundを使用して、要求された以上の要素を見つけてから、イテレータを後方に移動して前の値も確認できます。これはバイナリ検索を使用し、O(log n) のコストがかかります。これにより、標準の STL コンパレータなどが有効になります。

于 2015-07-15T13:14:06.797 に答える
3

実際に使用するベクトルがupper_bound()ない場合は、O(n) 操作になるため、作成する必要はありません。 upper_bound()あなたが持っている配列で動作します。以下を使用できます。

l_idx = std::upper_bound(x, x + size, value) - x - 1;

テストケース：

#include <iostream>
#include <functional>
#include <algorithm>

int main()
{
    const int size = 9;
    int x[9] = {1,2,3,4,5,6,7,8,9};

    auto pos = std::upper_bound(x, x + size, 5) - x;

    std::cout << "position: " << pos;

    return 0;
}

出力：

5

upper_bound()ポイントの結果として6 (実際の例) に私たちを。

于 2015-07-15T14:01:43.543 に答える
0

方法は、サイズに 1 を差し引いて (最大値を超えるようにするため)、正確にするためにターゲット値に 0.5 を差し引くことです。

#include <iostream>
#include <functional>
#include <algorithm>
using namespace std;

int main()
{
    float x[10] = { 2,3,4,5,6,7,8,9,10,11 },y;
    int size = sizeof(x) / sizeof(x[0]),pos;


    y = 4.1; pos = std::upper_bound(x, x + size - 1, y - 0.5) - x;
    std::cout << "position: " << pos << " target value=" << y << " upper_bound=" << x[pos] << endl;
    y = 4.9; pos = std::upper_bound(x, x + size - 1, y - 0.5) - x;
    std::cout << "position: " << pos << " target value=" << y << " upper_bound=" << x[pos] << endl;
    y = -0.5; pos = std::upper_bound(x, x + size - 1, y - 0.5) - x;
    std::cout << "position: " << pos << " target value=" << y << " upper_bound=" << x[pos] << endl;
    y = 100; pos = std::upper_bound(x, x + size - 1, y - 0.5) - x;
    std::cout << "position: " << pos << " target value=" << y << " upper_bound=" << x[pos] << endl;
    getchar();
    return 0;
}
于 2021-05-20T08:25:15.163 に答える