الفرق بين ناقلين<MyType*> A وB

Question

لقد حصلت على اثنين vector<MyType*> الكائنات تسمى A و B.تحتوي فئة MyType على حقل ID وأريد الحصول على MyType* التي هي في A ولكن ليس في B.أنا أعمل على تطبيق لتحليل الصور وكنت آمل أن أجد حلاً سريعًا/مُحسّنًا.

Answer 1

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

struct CompareId
{
    bool operator()(const MyType* a, const MyType* b) const
    {
        return a>ID < b->ID;
    }
};
...
sort(A.begin(), A.end(), CompareId() );
sort(B.begin(), B.end(), CompareId() );

vector<MyType*> C;
set_difference(A.begin(), A.end(), B.begin(), B.end(), back_inserter(C) );

حل آخر هو استخدام حاوية مرتبة مثل STD :: تعيين مع CompareID المستخدمة في وسيطة قالب strictweakordering. أعتقد أن هذا سيكون أفضل إذا كنت بحاجة إلى تطبيق الكثير من العمليات المحددة. يحتوي هذا على النفقات العامة الخاصة به (كونها شجرة) ولكن إذا وجدت حقًا أن هذه مشكلة في الكفاءة ، فيمكنك تنفيذ مخصص للذاكرة السريع لإدراج العناصر بسرعة فائقة (ملاحظة: قم بذلك فقط إذا قمت بتحديد هذا الأمر عنق الزجاجة).

تحذير: الدخول في منطقة معقدة إلى حد ما.

هناك حل آخر يمكنك مراعاته والذي يمكن أن يكون سريعًا جدًا إذا كان ذلك ممكنًا ولا تقلق أبدًا بشأن فرز البيانات. في الأساس ، قم بعمل أي مجموعة من كائنات mytype التي تشترك في نفس المتجر مع عداد مشترك (على سبيل المثال: مؤشر إلى int غير موقعة).

سيتطلب ذلك إنشاء خريطة للمعرفات إلى العدادات ويتطلب جلب العداد من الخريطة في كل مرة يتم فيها إنشاء كائن myType بناءً على معرفه. نظرًا لأن لديك كائنات myType ذات معرفات مكررة ، يجب ألا تضطر إلى إدراج الخريطة كلما قمت بإنشاء كائنات myType (ربما يمكن أن يجلب معظمها عدادًا موجودًا).

بالإضافة إلى ذلك ، احصل على عداد "اجتياز" عالمي يتم زيادة كلما تم جلبه.

static unsigned int counter = 0;
unsigned int traversal_counter()
{
    // make this atomic for multithreaded applications and
    // needs to be modified to set all existing ID-associated
    // counters to 0 on overflow (see below)
    return ++counter;
}

الآن دعنا نعود إلى حيث لديك ناقلات A و B تخزن mytype*. لإحضار العناصر في A ليست في B ، ندعو أولاً traversal_counter (). على افتراض أنها المرة الأولى التي نسميها ، فإن ذلك سوف يمنحنا قيمة اجتياز قدرها 1.

الآن تكرار من خلال كل كائن mytype* في B وقم بتعيين العداد المشترك لكل كائن من 0 إلى قيمة اجتياز ، 1.

الآن تكرار من خلال كل كائن mytype* في A. تلك التي لها قيمة مضادة لا تتطابق مع قيمة اجتياز الحالية (1) هي العناصر في A غير موجودة في B.

ماذا يحدث عندما تتفوق على عداد اجتياز؟ في هذه الحالة ، نتكرر من خلال جميع العدادات المخزنة في خريطة الهوية ونعيدها إلى الصفر مع عداد اجتياز نفسه. لن يلزم أن يحدث هذا إلا مرة واحدة في حوالي 4 مليارات تمريرات إذا كانت 32 بت غير موقعة.

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

Answer 2

فرز كلا المتجهين (std::sort) وفقا للمعرف ثم استخدم std::set_difference. ستحتاج إلى تحديد مقارنة مخصصة لتمرير كل من هذه الخوارزميات ، على سبيل المثال

struct comp
{
    bool operator()(MyType * lhs, MyType * rhs) const
    {
        return lhs->id < rhs->id;
    }
};

Answer 3

انظر أولاً إلى المشكلة.تريد "كل شيء في أ وليس في ب".هذا يعني أنه سيتعين عليك زيارة "كل شيء في A".سيتعين عليك أيضًا زيارة كل شيء في B للتعرف على ما هو موجود وما هو غير موجود في B.وهذا يشير إلى أنه يجب أن يكون هناك O(n) + O(m) الحل، أو الحرية في حذف الفرق بين n وm، O(2n).

دعونا نفكر في std::set_difference يقترب.كل نوع هو O(n log n), وset_difference هو O(n).لذا فإن نهج الفرز والفرز والاختلاف هو O(n + 2n log n).دعونا نسمي ذلك O(4n).

هناك طريقة أخرى تتمثل في وضع عناصر B أولاً في مجموعة (أو خريطة).التكرار عبر B لإنشاء المجموعة هو O(n) بالإضافة إلى الإدراج O(log n) لكل عنصر، متبوعًا بالتكرار عبر A O(n)، مع البحث عن كل عنصر من عناصر A (log n)، يعطي الإجمالي: O(2n log n).دعونا نسمي ذلك O(3n), ، وهو أفضل قليلا.

أخيرًا، باستخدام مجموعة غير مرتبة (أو خريطة غير مرتبة)، وبافتراض أننا حصلنا على حالة متوسطة لـ O(1) الإدراج و O(1) البحث، لدينا النهج الذي هو O(2n).اها!

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

Answer 4

إذا كان B preexists إلى A ، ثم أثناء ملء A ، يمكنك مسك الدفاتر في ناقل C.