البحث في ناقل C++<custom_class> عن التواجد الأول/الأخير للقيمة

Question

أحاول إيجاد أفضل طريقة للبحث عن متجه من النوع "Tracklet" (فئة أنشأتها بنفسي) للعثور على التواجد الأول والأخير لقيمة معينة لأحد متغيراته.على سبيل المثال، لدي الفئات التالية (مبسطة لهذا المثال):

class Tracklet {
    TimePoint *start;
    TimePoint *end;
    int angle;

    public:
        Tracklet(CvPoint*, CvPoint*, int, int);
}

class TimePoint {
    int x, y, t;

    public:
        TimePoint(int, int, int);
        TimePoint(CvPoint*, int);
        // Relevant getters and setters exist here   
};

لدي ناقل "vector<Tracklet> tracklets" وأحتاج إلى البحث عن أي مسارات ذات قيمة معينة "t" للنقطة الزمنية النهائية.يتم ترتيب المتجه من حيث وقت الانتهاء (أي. tracklet.end->t).

يسعدني ترميز خوارزمية بحث، ولكني غير متأكد من المسار الذي يجب اتباعه معها.لست متأكدًا من أن البحث الثنائي سيكون مناسبًا، حيث يبدو أنني أتذكر أنه لن يجد بالضرورة الأول.كنت أفكر في طريقة أستخدم فيها البحث الثنائي للعثور على فهرس لعنصر بالوقت الصحيح، ثم التكرار مرة أخرى للعثور على الأول ثم إعادة التوجيه للعثور على الأخير.أنا متأكد من أن هناك طريقة أفضل من ذلك، لأنها تهدر عمليات البحث الثنائية O(log n) بالتكرار.

نأمل أن يكون هذا منطقيًا:لقد كافحت لشرح ذلك قليلاً!هتافات!

Answer 1

إذا يتم فرز ناقلات ويحتوي على القيمة، وstd::lower_bound تعطيك مكرر إلى العنصر الأول بقيمة معينة، وسوف std::upper_bound تعطيك مكرر لعنصر واحد الماضي آخر واحد يحتوي على قيمة. مقارنة القيمة مع العنصر عاد لمعرفة ما إذا كان موجودا في ناقلات. كل من هذه الوظائف استخدام البحث الثنائي، لذلك الوقت هو O (logN).

لمقارنة على tracklet.end->t، الاستخدام:

bool compareTracklets(const Tracklet &tr1, const Tracklet &tr2) {
    return (tr1.end->t < tr2.end->t);
}

ووتمرير compareTracklets كما الوسيطة الرابعة لlower_bound أو upper_bound

Answer 2

وكنت مجرد استخدام find و <لأ href = "HTTP: //www.cplusplus.com/reference/algorithm/find_end "يختلط =" نوفولو noreferrer "> find_end ، ثم تفعل شيئا أكثر تعقيدا إلا إذا أظهر الاختبار أن يكون بطيئا للغاية.

إذا كنت حقا تشعر بالقلق إزاء أداء البحث، قد نظر في بنية بيانات مختلفة، مثل map مع الطابع الزمني كمفتاح وvector أو list من العناصر كقيمة.

Answer 3

وبحث ثنائي يبدو وكأنه الخيار الأفضل هنا، ما دام ناقلات بك فرزها. انها متطابقة في جوهرها، والأداء الحكيم، لأداء البحث في شجرة هيكل ثنائي.

Answer 4

يشار ديركينلي إلى مقارنة التحسين الحلو.لكنني في الواقع لن أستخدم أ std::vector لهذا.

عادةً، عندما أقرر استخدام حاوية STL، لا أعتبر حقًا جانب الأداء، لكنني أضع في الاعتبار واجهتها فيما يتعلق بنوع العملية التي أرغب في استخدامها.

std::set<T>::find
std::set<T>::lower_bound
std::set<T>::upper_bound
std::set<T>::equal_range

حقًا، إذا كنت تريد تسلسلًا مرتبًا، خارج إعداد المفتاح/القيمة، std::set هو أسهل في الاستخدام من أي شيء آخر.

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

بالطبع، تريد أيضًا أن يتألق مسند المقارنة الخاص بك حقًا (يأمل أن يقوم المترجم بتضمين تنفيذ عامل التشغيل ())، في كل حالة.

ولكن في الحقيقة، إذا لم تكن مقتنعًا، فجرب البناء باستخدام std::vector والإدراج/البحث اليدوي (باستخدام ملف <algorithm> header) وحاول إنشاء آخر باستخدام std::set.

قارن حجم التطبيقات (عدد أسطر التعليمات البرمجية)، وقارن عدد الأخطاء، وقارن السرعة، ثم قرر.

في أغلب الأحيان، يكون "التحسين" الذي تهدف إليه هو في الواقع التشاؤم, ، وفي تلك الأوقات النادرة لا يكون الأمر كذلك، بل إنه معقد للغاية لدرجة أنه لا يستحق كل هذا العناء.

تحسين:

• لا
• خبير فقط:لا تفعل ذلك، فنحن نعني ذلك

Answer 5

<اقتباس فقرة>   

وهو أمر متجه من حيث الوقت

ووقت البدء أو وقت النهاية؟

ما هو الخطأ مع O السذاجة (ن) بحث؟ تذكر أنك تبحث فقط وليس الفرز. هل يمكن استخدام وعاء فرزها وكذلك (إذا كان ذلك لا يتعارض مع التصميم الأساسي).