7

问题

我有时间戳数据，我需要根据时间戳进行搜索，以便获得与我的输入时间戳最接近的一个现有时间戳。
最好用 STL 解决这个问题。boost::* 或 stl::tr1::* （来自带有 Featurepack 的 VS9）也是可能的。
时间戳数据示例：

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

使用stl::vector,sort()和equal_range()

由于 a maporset只允许我找到完全匹配，因此我不再使用其中一个。所以现在我有一个vector我在数据进入时追加数据的地方。在搜索之前，我使用<algorithm>'ssort()并为其提供自定义比较功能。
之后，我使用<algorithm>'sequal_range()查找指定值的两个邻居x。从这两个值中，我检查哪一个最接近x，然后我有我的最佳匹配。


虽然这不是太复杂，但我想知道是否有更优雅的解决方案。
也许 STL 已经有一个算法可以做到这一点，所以我不会在这里重新发明一些东西？

更新：线性与二进制搜索

我忘了提到我有很多数据要处理，所以我不想线性搜索。
我对向量进行排序的原因sort()是它具有随机访问迭代器，而map. 使用 amap不允许equal_range()进行具有两倍对数复杂度的搜索。
我对么？

4

4 回答 4

7

对于这样的事情，我也会使用 equal_range 。

如果您每次都在向量上使用 sort()，最好使用映射（或集合），因为它总是自动排序，并使用成员 equal_range

但这取决于插入/查询/数据量的数量。（虽然对于查询时总是需要排序的东西，地图将是我的首选，如果有充分的理由，我只会使用矢量）

于 2008-10-20T14:10:13.723 回答
7

我会使用 set::lower_bound 来查找匹配或更大的值，然后递减迭代器以检查下一个较低的值。您应该使用 std::set 而不是 std::map 因为您的密钥嵌入在对象中 - 您需要提供一个比较时间戳成员的函子。

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

根据您的用途，您可以进行简单的线性搜索而不是排序。想出一个“距离”函数，循环跟踪迄今为止的最佳匹配及其距离。当你找到更好的匹配时，忘记前一个，保持新的和它的距离。当您遍历所有内容时，您就有了比赛。

结果为 O(N*S)，其中 N 是向量中的项目数，S 是搜索次数。

您当前的方式是 O((N+S)*LogN) 如果搜索次数少且有界则更大。否则排序/二进制搜索会更好。

于 2008-10-20T14:08:55.177 回答
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 回答