العثور على "أفضل مفتاح مطابقة" للحصول على مفتاح معين في حاوية STL فرز

Question

مشكلة

ولدي بيانات قتية، وأنا بحاجة للبحث على أساس زمني من أجل الحصول على الطابع الزمني الحالي واحد والذي يطابق بلدي إدخال الطابع الزمني أقرب.
ويفضل هذا يجب أن تحل مع المحكمة الخاصة بلبنان. تعزيز :: * أو STL :: :: TR1 * (من VS9 مع Featurepack) ممكنة أيضا.
مثال على البيانات طابع زمني:

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

النهج مع stl::vector، sort() وequal_range()

وبما أن map أو set يسمح لي فقط للعثور على مطابقة تامة، أنا لا أحصل على أي زيادة استخدام واحد من هؤلاء. وحتى الآن لدي vector التي أشرت إلحاق البيانات كما هو الحال في القادمة. قبل البحث يمكنني استخدام <algorithm> sort() وتزويدها وظيفة مقارنة مخصصة.
بعد ذلك يمكنني استخدام <algorithm> equal_range() للعثور على الجارتين من x القيمة المحددة. من هاتين القيمتين I تحقق واحد الذي هو الأقرب إلى x ثم لدي أفضل مباراة لي.

و
في حين أن هذا ليست معقدة جدا، وأنا أتساءل عما إذا كان هناك حلول أكثر أناقة لهذا.
ربما STL بالفعل خوارزمية التي تفعل ذلك تماما لذلك أنا لا إعادة اختراع شيء هنا؟

تحديث: خطي مقابل البحث الثنائي

ونسيت أن أذكر أن لدي الكثير جدا من البيانات للتعامل مع ذلك أنا لا أريد أن يكون للبحث خطيا.
السبب أنا فرز متجه مع sort() هو لأنه يحتوي المكررات الوصول العشوائي الذي ليس هو الحال مع map. سوف تستخدم map لن تسمح equal_range() للقيام بعملية بحث مع ضعف التعقيد لوغاريتمي.
أنا صحيح؟

Answer 1

وأود أن استخدام تشكيلة :: LOWER_BOUND للعثور على مطابقة أو قيمة أكبر، ثم إنقاص مكرر للتحقق من قيمة النواب المقبلة. يجب عليك استخدام الأمراض المنقولة جنسيا :: مجموعة بدلا من الأمراض المنقولة جنسيا :: خريطة لأن جزءا لا يتجزأ من المفتاح الخاص في الكائن - ستحتاج إلى توفير functor أن يقارن أعضاء الطابع الزمني

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;
}

Answer 2

وأود أن استخدام equal_range جدا لشيء من هذا القبيل.

إذا كنت تستخدم نوع () في كل مرة على ناقلات الخاصة بك قد يكون من الأفضل استخدام خريطة (أو مجموعة)، وهذا ما دائما مرتبة تلقائيا، واستخدام equal_range عضو

ولكن ذلك يعتمد على كمية إدراج / استفسارات / كمية البيانات. (على الرغم من أن لشيء يحتاج دائما إلى أن يتم فرز عندما الاستعلام، وخريطة سيكون خياري الأول، وكنت فقط استخدام ناقلات إذا كان هناك سبب وجيه جدا)

Answer 3

واعتمادا على ما هو استخدامك، هل يمكن أن تفعل في البحث الخطي البسيط بدلا من الفرز. التوصل إلى "المسافة" وظيفة، حلقة من خلال تتبع أفضل مباراة حتى الآن، وبعدها. عند العثور على تطابق أفضل، وننسى سابقتها، والحفاظ على واحد جديد وبعدها. عندما كنت قد يحلق من خلال كل شيء، لديك مباراة الخاص بك.

وهذا يعمل ليكون O (N * S) حيث N هو عدد العناصر في النواقل وS هو عدد عمليات البحث.

والطريقة الحالية الخاصة بك هو O ((N + S) * LogN) وهو أكبر إذا كان عدد من عمليات التفتيش صغير ويحدها. وإلا فإن نوع / البحث الثنائي هو أفضل.

Answer 4

//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";
}