Tr1 :: Hash for Boost :: Read :: ID؟

Question

بدأت في استخدام unordered_set فئة من tr1 مساحة الاسم لتسريع الوصول ضد STL العادي (القائمة على الأشجار) map. وبعد ومع ذلك، أردت تخزين المراجع إلى معرف المواضيع في دفعة (boost::thread::id) وأدرك أن واجهة برمجة تطبيقات هؤلاء المعرفات غير مبهمة للغاية بأنك لا يمكنك الحصول عليها بوضوح تجزئة منه.

والمثير للدهشة، دفعة تنفذ أجزاء من tr1 (بما فيها hash و unordered_set)، لكنه لا يحدد فئة التجزئة القادرة على تهزم معرف مؤشر الترابط.

النظر إلى وثائق boost::thread::id لقد وجدت أن معرفات الخيط يمكن أن تكون إخراجها إلى دفق، لذلك كان حلاي للقيام بالتجزئة نوعا من:

struct boost_thread_id_hash
{
    size_t operator()(boost::thread::id const& id) const
    {
        std::stringstream ostr;
        ostr << id;
        std::tr1::hash<std::string> h;
        return h(ostr.str());
    }
};

وهذا هو، تسليمها، وتطبيق التجزئة على السلسلة الناتجة. ومع ذلك، يبدو أن هذا أقل كفاءة من استخدام STL فعلا map<boost::thread::id>.

لذلك، أسئلتي: هل تجد طريقة أفضل للقيام بذلك؟ هل هو تناسق واضح في كل من دفعة و TR1 لا يجبر وجود hash<boost::thread::id> صف دراسي؟

شكرا.

Answer 1

النفقات العامة ل thread::id (فقط لحساب سلسلة التجزئة بعد ذلك)، كما قلت نفسك تقريبا، فلكي مقارنة بأي فوائد أداء tr1::unordered_map قد تمنع تجاه std::map. وبعد لذلك ستكون الإجابة القصيرة: عصا مع STD :: خريطة <الموضوع :: ID ...>

اذا أنت إطلاقا يجب استخدام حاويات غير مرضية، حاول استخدامnative_handle_type بدلا من thread::id إذا كان ذلك ممكنا، أي أفضل tr1::unordered_map< thread::native_handle_type, ... >, ، استدعاء thread::native_handle() بدلا من thread::get_id() متي insertجي واو findعمل.

لا تحاول أي شيء مثل ما يلي:

struct boost_thread_id_hash {
   // one and only member of boost::thread::id is boost::thread::id::thread_data
   //   of type boost::detail::thread_data_ptr;
   // boost::thread::id::operator==(const id&) compares boost::thread::id::thread_data's
   size_t operator()(boost::thread::id const& id) const {
      const boost::detail::thread_data_ptr* pptdp = \
        reinterpret_cast< boost::detail::thread_data_ptr* >(&id);
      return h(pptdp->get());
   }
};

يمكن أن تعمل، ولكنه هش للغاية ووقت مضمون تقريبا. يفترض معرفة حميمة بالأعمال الداخلية لل thread::id تطبيق. سوف تحصل على لعن من قبل المطورين الآخرين. لا تفعل ذلك إذا كان الصيانة من أي قلق! حتى الترقيع boost/thread/detail/thread.hpp لإضافة size_t hash_value(const id& tid) كصديق thread::id أفضل". :)

Answer 2

السؤال الواضح هو السبب في أن تريد فعلا استخدام التجزئة؟

أنا أفهم القضية مع map / set للحصول على رمز أساسي للأداء، في الواقع هذه الحاويات ليست صديقة لذاكرة التخزين المؤقت جدا لأن العناصر قد يتم تخصيصها في مواقع ذاكرة مختلفة جدا.

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

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

ومع ذلك، هناك بنية بيانات تحاول ربط الفوائد من الخرائط والمجهدات الفرز: ب + شجرة.

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

للحصول على المزيد من الأداء الذي يمكنك:

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

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

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

Answer 3

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

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

إذا كنت لا تزال بحاجة إلى القيام بذلك، فماذا عن التعامل معها فقط كقرازات (دفعة :: معرف الموضوع: معرف)، والتشغيل على تلك.

يفترض هذا المثال أن حجم Bost :: Thread :: ID هو مضاعف حجم INT، وأنه لا توجد تعبئة، ولا توجد وظائف افتراضية. إذا لم يكن الأمر صحيحا، فسيتعين تعديله، أو لن يعمل على الإطلاق.

تحرير: ألقيت نظرة على boost::thread::id فئة، ولها boost::shared_pointer<> كعضو، لذلك الكود أدناه مكسورة بشكل فظيع. أعتقد أن الحل الوحيد هو الحصول على مؤلفي boost::thread إضافة وظيفة تجزئة. سأترك المثال فقط في حالة فائدة في السياق الآخر.

boost::thread::id id;
unsigned* data;
// The next line doesn't do anything useful in this case.
data = reinterpret_cast<unsigned *>(&id);
unsigned hash = 0;

for (unsigned int i = 0; i < sizeof(boost::thread::id)/4; i++)
  hash ^= data[i];

Answer 4

في وقت متأخر بعد عدة سنوات للإجابة على هذا السؤال، ولكن هذا أظهر أنه الأكثر صلة بالآخر عند محاولة وضع دفعة :: موضوع :: ID في STD :: Unrodered_map كمفتاح. كان الحصول على المقبض الأصلي اقتراحا جيدا في الرد المقبول إلا أنه غير متاح لهذا_thاد.

بدلا من ذلك، يوجد في وقت ما له في وقت ما له Hash_Value للخيط :: معرف، لذلك هذا يعمل بشكل جيد بالنسبة لي:

namespace boost {
  extern std::size_t hash_value(const thread::id &v);
}

namespace std {
  template<>
  struct hash<boost::thread::id> {
    std::size_t operator()(const boost::thread::id& v) const {
      return boost::hash_value(v);
    }
  };
}

بالطبع، تحتاج إلى الارتباط ضد مكتبة libboost_thread.

Answer 5

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