7

問題

入力タイムスタンプに最も近い既存のタイムスタンプを取得するために、タイムスタンプに基づいて検索する必要があるタイムスタンプ付きデータがあります。
できれば、これは STL で解決する必要があります。boost::* または stl::tr1::* (Featurepack を使用した VS9 から) も可能です。
タイムスタンプ付きデータの例:

struct STimestampedData
{
 time_t m_timestamp; // Sorting criterion
 CData m_data;       // Payload
}

stl::vector、 、sort()でアプローチequal_range()

maporsetは正確な一致を見つけることしかできないため、これらのいずれかを使用してそれ以上取得することはできません。これで、入ってくるデータを追加するがvectorできました。検索する前に を使用し、カスタム比較関数を指定します。 その後、's'を使用して、指定された値の 2 つの隣接値を見つけます。これらの 2 つの値から、どちらが最も近いかを確認し、最適な一致を見つけます。<algorithm>sort()
<algorithm>equal_range()xx


これはそれほど複雑ではありませんが、もっと洗練された解決策があるのではないかと思います。
たぶん、STLにはすでにそれを行うアルゴリズムがあるので、ここで何かを再発明していませんか?

更新: 線形対二分探索

処理するデータが非常に多いため、直線的に検索する必要がないことを忘れていました。
ベクトルを並べ替える理由はsort()、map. a を使用すると、2 倍の対数複雑度で検索を実行mapできません。 私は正しいですか？equal_range()

4

4 に答える 4

7

そのようなことにも equal_range を使用します。

ベクターで毎回 sort() を使用している場合は、常に自動的にソートされるマップ (またはセット) を使用し、メンバー equal_range を使用することをお勧めします。

ただし、それは挿入/クエリ/データ量の量によって異なります。（ただし、クエリを実行するときに常にソートする必要があるものについては、マップが最初の選択肢であり、非常に正当な理由がある場合にのみベクターを使用します）

于 2008-10-20T14:10:13.723 に答える
7

set::lower_bound を使用して、一致する値またはそれより大きい値を見つけてから、イテレータをデクリメントして、次に低い値をチェックします。キーはオブジェクトに埋め込まれているため、std::map ではなく std::set を使用する必要があります。タイムスタンプ メンバーを比較するファンクターを提供する必要があります。

struct TimestampCompare
{
    bool operator()(const STimestampedData & left, const STimestampedData & right) const
    {
        return left.m_timestamp < right.m_timestamp;
    }
};
typedef std::set<STimestampedData,TimestampCompare> TimestampedDataSet;

TimestampedDataSet::iterator FindClosest(TimestampedDataSet & data, STimestampedData & searchkey)
{
    if (data.empty())
        return data.end();
    TimestampedDataSet::iterator upper = data.lower_bound(searchkey);
    if (upper == data.end())
        return --upper;
    if (upper == data.begin() || upper->m_timestamp == searchkey.m_timestamp)
        return upper;
    TimestampedDataSet::iterator lower = upper;
    --lower;
    if ((searchkey.m_timestamp - lower->m_timestamp) < (upper->m_timestamp - searchkey.m_timestamp))
        return lower;
    return upper;
}
于 2008-10-20T14:55:18.203 に答える
0 
//the function should return the element from iArr which has the least distance from input
double nearestValue(vector<double> iArr, double input)
{
    double pivot(0),temp(0),index(0);
    pivot = abs(iArr[0]-input);
    for(int m=1;m<iArr.size();m++)
    {           
        temp = abs(iArr[m]-input);

        if(temp<pivot)
        {
            pivot = temp;
            index = m;
        }
    }

    return iArr[index];
}

void main()
{
    vector<double> iArr;

    srand(time(NULL));
    for(int m=0;m<10;m++)
    {
        iArr.push_back(rand()%20);
        cout<<iArr[m]<<" ";
    }

    cout<<"\nnearest value is: "<<lib.nearestValue(iArr,16)<<"\n";
}
于 2011-06-28T14:26:57.890 に答える
0

使用状況に応じて、並べ替えの代わりに単純な線形検索を実行できます。「距離」関数を考え出し、これまでの最良の一致とその距離を追跡します。より良い一致を見つけたら、前の一致を忘れて、新しい一致とその距離を保ちます。すべてをループしたら、マッチが完了です。

これは O(N*S) となります。ここで、N はベクトル内のアイテムの数、S は検索の数です。

あなたの現在の方法は O((N+S)*LogN) です。これは、検索数が少なく制限されている場合に大きくなります。それ以外の場合は、ソート/バイナリ検索の方が優れています。

于 2008-10-20T14:08:55.177 に答える