كيف يمكنني زيادة الأداء في البحث عن الخريطة باستخدام نوع المفتاح std::string؟

Question

أنا أستخدم أ std::map (تنفيذ VC++) وهو بطيء بعض الشيء لعمليات البحث عبر طريقة البحث على الخريطة.

نوع المفتاح هو std::string.

هل يمكنني زيادة أداء هذا std::map البحث عبر تجاوز مقارنة مفتاح مخصص للخريطة؟على سبيل المثال، ربما std::string < المقارنة لا تأخذ بعين الاعتبار أمرا بسيطا string::size() قارن قبل مقارنة بياناته؟

أي أفكار أخرى لتسريع المقارنة؟

في حالتي، ستحتوي الخريطة دائمًا على أقل من 15 عنصرًا، ولكن يتم الاستعلام عنها دون توقف ويكون الأداء أمرًا بالغ الأهمية.ربما هناك بنية بيانات أفضل يمكنني استخدامها وستكون أسرع؟

تحديث:تحتوي الخريطة على مسارات الملفات.

التحديث2:تتغير عناصر الخريطة كثيرًا.

Answer 1

أولاً، قم بإيقاف تشغيل كافة ملفات التعريف ومفاتيح DEBUG.هذه يمكن أن تبطئ المحكمة الخاصة بلبنان بشكل كبير.

إذا لم يكن الأمر كذلك، فقد يكون جزء من المشكلة هو أن سلاسلك متطابقة بالنسبة لأول 80-90% من السلسلة.هذا ليس سيئًا بالنسبة للخريطة، بالضرورة، ولكنه مخصص لمقارنات السلسلة.إذا كان الأمر كذلك، فقد يستغرق بحثك وقتًا أطول.

على سبيل المثال، في هذا الكود، من المحتمل أن يؤدي البحث () إلى مقارنتين للسلسلة، لكن كل منهما سيعود بعد مقارنة الحرف الأول حتى "david"، وبعد ذلك سيتم التحقق من الأحرف الثلاثة الأولى.لذلك، سيتم التحقق من 5 أحرف على الأكثر في كل مكالمة.

map<string,int> names;
names["larry"] = 1;
names["david"] = 2;
names["juanita"] = 3;

map<string,int>::iterator iter = names.find("daniel");

من ناحية أخرى، في الكود التالي، من المحتمل أن يتحقق find() من أكثر من 135 حرفًا:

map<string,int> names;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/wilma"] = 1;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/fred"] = 2;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/barney"] = 3;

map<string,int>::iterator iter = names.find("/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/betty");

وذلك لأن مقارنات السلسلة يجب أن تبحث بشكل أعمق للعثور على تطابق لأن بداية كل سلسلة هي نفسها.

إن استخدام size() في مقارنتك للمساواة لن يساعدك كثيرًا هنا نظرًا لأن مجموعة البيانات الخاصة بك صغيرة جدًا.يتم الاحتفاظ بالخريطة std::map مرتبة بحيث يمكن البحث عن عناصرها من خلال البحث الثنائي.يجب أن يؤدي كل استدعاء للبحث إلى أقل من 5 مقارنات للسلسلة للخطأ، ومتوسط ​​مقارنتين للنتيجة.لكن ذلك يعتمد على بياناتك.إذا كانت معظم سلاسل المسار الخاصة بك ذات أطوال مختلفة، فإن التحقق من الحجم كما وصفه موتي يمكن أن يساعد كثيرًا.

الشيء الذي يجب مراعاته عند التفكير في خوارزميات بديلة هو عدد "النتائج" التي تحصل عليها.هل تعود معظم مكالمات البحث () الخاصة بك إلى النهاية () أو نتيجة؟إذا كانت معظم عمليات البحث () الخاصة بك تُرجع النهاية () (تخطئ)، فأنت تبحث في الخريطة بأكملها في كل مرة (مقارنة سلسلة 2logn).

Hash_map فكرة جيدة؛من المفترض أن يقلل وقت البحث إلى النصف تقريبًا؛المزيد عن الأخطاء.

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

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

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

أخيرًا، ابحث عن تطبيقات std::map البديلة.لقد سمعت أشياء سيئة عن بعض أداء كود stl الخاص بـ VC.مكتبة DEBUG على وجه الخصوص سيئة في التحقق منك في كل مكالمة. StlPort لقد كان بديلاً جيدًا، لكنني لم أجربه منذ عدة سنوات.لقد أحببت دائما يعزز أيضاً.

Answer 2

كما <لأ href = "https://stackoverflow.com/questions/256038/how-can-i-increase-the-performance-in-a-map-lookup-with-key-type-stdstring#256052 "> وقال حتى المشغل المستخدمة في set هو < لا ==.

إذا كنت لا تهتم حول ترتيب السلاسل في set الخاص بك يمكنك تمرير set والمقارن مخصصة أداء أفضل من العادية <م> أقل من .

وعلى سبيل المثال إذا كان الكثير من سلاسل لديك البادئات مشابهة (لكنها تختلف في الطول) يمكنك ترتيب النتائج بحسب طول سلسلة (منذ string.length هو سرعة ثابتة).

إذا قمت بذلك حذار خطأ شائع:

struct comp {
    bool operator()(const std::string& lhs, const std::string& rhs)
    {
        if (lhs.length() < rhs.length())
            return true;
        return lhs < rhs;
    }
};

وهذا المشغل لا يحتفظ ضعف الطلب ، هل يمكن أن يكون اثنين من السلاسل التي هي كل منها أقل من الآخر.

string a = "z";
string b = "aa";

واتبع المنطق وسترى أن comp(a, b) == true وcomp(b, a) == true.

وتنفيذ الصحيح هو:

struct comp {
    bool operator()(const std::string& lhs, const std::string& rhs)
    {
        if (lhs.length() != rhs.length())
            return lhs.length() < rhs.length();
        return lhs < rhs;
    }
};

Answer 3

وأول شيء هو محاولة استخدام hash_map إذا كان ذلك ممكنا - أنت على حق أن السلسلة القياسية مقارنة لا الاختيار الأول لحجم (لأنه يقارن lexicographically)، ولكن كتابة التعليمات البرمجية خريطة الخاصة بك هو شيء تريد ان تكون أفضل حالا تجنب. من سؤالك هذا يبدو وكأنه لا تحتاج إلى تكرار عبر نطاقات. في تلك الخريطة حالة لم يكن لديك أي شيء hash_map لا.

وهذا يعتمد أيضا على نوع من المفاتيح لديك في الخريطة الخاصة بك. هم عادة طويلة جدا؟ أيضا ماذا "بطيئة بعض الشيء" يعني؟ إذا لم تكن قد لمحة رمز فمن الممكن جدا أنه جزء تأخذ وقتا مختلفا.

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

Answer 4

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

أسباب الاعتقاد بأن الأمر سيكون أسرع:

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

أسباب الاعتقاد بأنه سيكون أبطأ:

1. الحذف والإضافة يعني تحريك السلاسل في الذاكرة منذ ذلك الحين string'س swap تتسم بالكفاءة وحجم مجموعة البيانات صغير، وقد لا يمثل هذا مشكلة.

Answer 5

والأمراض المنقولة جنسيا :: مقارنة خريطة للا STD :: equal_to انها STD :: أقل، وأنا لست متأكدا ما هي أفضل طريقة لدارة قصيرة <مقارنة بحيث يكون أسرع من المدمج في واحدة.

وإذا كان هناك دائما <15 elems، وربما يمكن استخدام مفتاح بالإضافة إلى الأمراض المنقولة جنسيا :: سلسلة؟

Answer 6

وموتي لديه حلا جيدا. ومع ذلك، وأنا متأكد من أن لمدة 15 العناصر الخاصة بك <خريطة ليست هي الطريق الصحيح لأن النفقات العامة التي سوف يكون دائما أكبر من جدول بحث بسيط مع مخطط التجزئة المناسب. في قضيتك، بل قد يكون كافيا لتجزئة التي كتبها طول وحده، وإذا كان هذا لا يزال ينتج التصادم، واستخدام البحث الخطي من خلال كل مقالات من نفس الطول.

لتحديد ما اذا أنا على حق، والمعيار هو بالطبع مطلوب ولكن أنا متأكد تماما من نتائجها.

Answer 7

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

class HashedString
{
  unsigned m_hash;
  std::string m_string;

public:
  HashedString(const std::string& str)
    : m_hash(HashString(str))
    , m_string(str)
  {};
  // ... copy constructor and etc...

  unsigned GetHash() const {return m_hash;}
  const std::string& GetString() const {return m_string;}
};

وهذا له فوائد الحوسبة تجزئة السلسلة مرة واحدة، على البناء. بعد هذا، هل يمكن تنفيذ وظيفة مقارنة:

struct comp
{
  bool operator()(const HashedString& lhs, const HashedString& rhs)
  {
    if(lhs.GetHash() < rhs.GetHash()) return true;
    if(lhs.GetHash() > rhs.GetHash()) return false;
    return lhs.GetString() < rhs.GetString();
  }
};

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

Answer 8

وربما كنت قد عكس السلاسل قبل استخدامها كمفاتيح في الخريطة؟ يمكن أن يساعد إذا الأحرف القليلة الأولى من كل سلسلة متطابقة.

Answer 9

وفيما يلي بعض الأشياء التي يمكنك النظر فيما يلي:

و0) هل أنت متأكد أن هذا هو المكان الذي عنق الزجاجة الأداء؟ مثل النتائج من قياس، Cachegrind، gprof أو شيء من هذا القبيل؟ لأن عمليات البحث على هذه الخريطة سماب يجب أن يكون سريع إلى حد ما ...

1) يمكنك تجاوز functor يستخدم لمقارنة المفاتيح في الأمراض المنقولة جنسيا :: خريطة <>، هناك معلمة قالب الثانية للقيام بذلك. أشك في أنك تستطيع أن تفعل أفضل بكثير من المشغل <، ولكن.

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

و3) هل العناصر المعروفة في وقت الترجمة؟ هل يمكن استخدام وظيفة تجزئة مثالية لتحسين أوقات بحث إذا كان هذا هو الحال. البحث عن gperf على شبكة الإنترنت.

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

وقد اقترحت هذه بالفعل، ولكن بمزيد من التفصيل:

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

Answer 10

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

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

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

وأنا أكره سلاسل :) لم يكونوا بطيئة للمقارنة، ولكنها يمكن أن القمامة حقا مخابئ وحدة المعالجة المركزية الخاصة بك على برامج عالية الأداء.

Answer 11

وحاول الأمراض المنقولة جنسيا :: :: TR1 unordered_map (وجدت في رأس ). هذا هو عبارة عن خريطة التجزئة، و، في حين أنه لا يحتفظ ترتيب فرز العناصر، من المرجح أن تكون أسرع بكثير من الخريطة العادية.

إذا لم المترجم الخاص بك دعم TR1، والحصول على إصدار أحدث. MSVC ودول مجلس التعاون الخليجي على حد سواء الدعم TR1، وأعتقد أن أحدث إصدارات معظم المجمعين أخرى أيضا الدعم. للأسف، لم يتم تحديثها الكثير من المواقع مرجع مكتبة، لذلك يبقى TR1 قطعة-مجهولة إلى حد كبير من التكنولوجيا.

وآمل C ++ 0X ليس بنفس الطريقة.

وتحرير: لاحظ أن طريقة التجزئة الافتراضية لTR1 :: unordered_map هو TR1 :: التجزئة، الذي يحتاج إلى أن تكون متخصصة للعمل على UDT، وربما

.

Answer 12

عندما يكون لديك سلاسل فرعية مشتركة طويلة، قد تكون المحاولة بنية بيانات أفضل من الخريطة أو hash_map.لقد قلت "ربما"، بالرغم من ذلك - لا تعبر خريطة التجزئة المفتاح إلا مرة واحدة لكل عملية بحث، لذلك يجب أن تكون سريعة إلى حد ما.لن أناقش الأمر أكثر لأن الآخرين فعلوا ذلك بالفعل.

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

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

قد يمثل العثور على تطبيق يرضيك مشكلة.يشير البحث في صفحة Boost الرئيسية إلى أن لديهم شجرة splay وAVL ولكن ليس لديهم محاولة.

لقد ذكرت في تعليق أنه ليس لديك أبدًا بحث يفشل في العثور على أي شيء.لذلك يمكنك من الناحية النظرية تخطي المقارنة النهائية، والتي في شجرة مكونة من 15 < 2 ^ 4 عنصر يمكن أن تمنحك شيئًا مثل تسريع بنسبة 20-25٪ دون القيام بأي شيء آخر.في الواقع، ربما أكثر من ذلك، نظرًا لأن السلاسل المتساوية هي الأبطأ في المقارنة.ما إذا كان الأمر يستحق كتابة الحاوية الخاصة بك فقط من أجل هذا التحسين هو سؤال آخر.

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

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

Answer 13

وhash_map غير القياسية، حاول استخدام unordered_map متاح في TR1 (والذي يتوفر في دفعة إذا لم يكن لديك بالفعل سلسلة أداة الخاص به).

لأعداد صغيرة من السلاسل التي قد يكون من الأفضل استخدام vector، كما يتم تنفيذ map عادة مثل شجرة.

Answer 14

لماذا لا يمكنك استخدام جدول هاش بدلا من ذلك؟ تعزيز :: unordered_map يمكن القيام به. أو يمكنك طرح الحل الخاص بك، وتخزينها اتفاقية حقوق الطفل من سلسلة بدلا من السلسلة نفسها. أو الأفضل من ذلك، وضعت #defines للسلاسل، واستخدام تلك لبحث، منها مثلا،

#define "STRING_1" STRING_1