3

Is there an efficient method of finding the index of a value in a Vector, closest to a reference value?

4

2 に答える 2

10

計算上、ベクトルがソートされていない場合、O(n) 未満のものは期待できません。そうでない場合は、データ構造を変更する必要があります。その場合は、次のように使用できますstd::min_element。

#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
    int refElem = 42;
    std::vector<int> v{1, 5, 36, 50};
    auto i = min_element(begin(v), end(v), [=] (int x, int y)
    {
        return abs(x - refElem) < abs(y - refElem);
    });

    std::cout << std::distance(begin(v), i); // Prints 2
}

一方、ベクトルがソートされている場合は、対数複雑度を持つstd::lower_bound()とを使用できます。std::upper_bound()

複雑さがパフォーマンスの問題であると思われる場合は、データ構造の変更を決定する前に、いくつかの測定を行ってください。ベクトルは要素をメモリの連続した領域に格納するため、高いキャッシュ ヒット率をもたらす線形検索は、その要素をメモリ内のあちこちに割り当てるデータ構造に対する計算効率の高いアルゴリズムよりもパフォーマンスが高く、キャッシュ ミスが頻繁に発生します。

于 2013-04-06T18:41:44.123 に答える
1

  1. 線形検索があなたの選択のようです（少なくともソートされていないベクトルの場合。検索のためだけにベクトルをソートしても意味がないようです。

  2. 一般に、すべては「最も近い」の下で何を意味するかによって異なります。この「最も近い」は、おそらく単項述語として実装する必要があります。要素が等しい場合、述語は 0 のような値を返す必要があり、要素が参照から離れているほど大きい値が返されます。

  3. <algorithm> からわかるように、必要なものに最も近いアルゴリズムはstd::min_elementですが、範囲パラメーターだけでなく参照要素 (または参照する要素が「どれだけ近いか」を決定する述語) も必要です。

  4. おそらく、要素が等しいかどうかを確認し、等しい場合はループを中断することで、ある程度の利益を得ることができます。

于 2013-04-06T19:05:19.130 に答える