باستخدام تجزئة خرائط لتمثيل كبيرة للغاية مصدر البيانات
https://stackoverflow.com/questions/837203
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لدي مجموعة كبيرة جدا ممكن مجموعة البيانات التي أحاول أن تصور في وقت واحد.مجموعة نفسها تتكون من مئات الآلاف من قطاعات كل منها تعيين معرف.
وقد تلقيت الثاني مصدر البيانات أن يعطي المزيد من المعلومات في الوقت الحقيقي عن كل قطعة ، ولكن هذا الرقم لا تتوافق مع الهوية لدي.
لدي 1:1 تعيين البيانات معرف (9-سلاسل الأحرف) الحالي id (أعداد صحيحة طويلة).المشكلة هي أن هناك الكثير من معرف و البيانات التي تأتي في أي ترتيب معين.
الحل خطرت لي هو أن يكون هناك تجزئة-خريطة خرائط السلاسل إلى الطريق الهوية.المشكلة هي أنني لا أعرف إذا كان تجزئة الخريطة سوف تكون فعالة بما فيه الكفاية أن يكون كل 166k إدخالات البيانات.
هل من أحد لديه أي اقتراحات و/أو خوارزميات التجزئة التي يمكن استخدامها من أجل هذا ؟
المحلول
إذا كنت تتعامل فقط مع مئات الآلاف من datapoints، فإنه من المحتمل أن لا يكون مشكلة للذهاب مع طريقة ساذجة ومجرد عصا مع تجزئة خريطة.
وحتى إذا كان لديك 500000 سلاسل 9-حرف وعدد مماثل من longs، أن بايت فقط لا تزال 16ish لكل بند، أو 8،000،000 بايت المجموع. حتى لو كنت مضاعفة هذا عن النفقات العامة، 16 MB بالكاد أكبر من أن يكون في الذاكرة في وقت واحد.
وأساسا، في محاولة الطريقة السهلة أولا، وتقلق فقط عن ذلك عندما التنميط يخبرك انه أخذ وقتا طويلا.
نصائح أخرى
صالحة جودي مصممة لهذا النوع من الشيء: "الفوائد الرئيسية جودي هي التدرجية، والأداء الرفيع، وكفاءة الذاكرة. [...] جودي يمكن أن تحل محل العديد من هياكل البيانات المشتركة، مثل المصفوفات، مصفوفات متفرق، الجداول التجزئة، B-الأشجار، شجرة ثنائية، والقوائم الخطية، skiplists، وغيرها من نوع وخوارزميات البحث، وظائف العد ".
منذ التعليقات على السؤال تبين الشاغل قد يكون استخدام الذاكرة:
- استخدام تجميع أو الصغيرة الأخرى-كائن-محسن مخصص;على افتراض لديك حق الوصول إلى دفعة ربما يمكنك أن تجد قطرة في استبدال في بركة.باستخدام أفضل صغير كائن مخصص هو على الأرجح واحدة من أكبر ذاكرة الفوز سوف تجد.
- إذا كنت تعرف سلاسل الخاص بك يتم عرض ثابت, قد ترغب في التأكد من أنك تخصيص مساحة كافية فقط لتخزينها.على سبيل المثال البنية ملفوفة حول طول ثابت char[] مع العرف عامل المقارنة قد تعمل على نحو أفضل من std::string.std::string يأتي مع إضافية التخصيص الديناميكي (ويستخدم الفضاء المقابلة المؤشر) وبعض حجم وقدرة تتبع النفقات العامة.(عموما ، في محاولة والحد من عدد من المخصصات التي تلتصق حولها ؛ فإنه يقلل من النفقات العامة.)
- (على افتراض STL) انظر النفقات العامة الفرق بين std::خريطة std::unordered_map (وهذه الأخيرة قد تكون أو لا تكون متاحة لك في هذه اللحظة);وهو RBtree القائم على std::خريطة قد تكون قريبة بما فيه الكفاية إلى بحث خصائص الأداء من "hashmap" و (أو لا) تكون أكثر كفاءة الذاكرة اعتمادا على معيار مكتبة التنفيذ.
ما الطريق الذي ينبغي أن تتأثر يمكنك جمع-محاولة الحصول على صورة عدد من allocs و الوك حجم/محاذاة النفقات العامة.
يمكنك إما الصك الخاص بك مخصص أو إدراج بعض العناصر و انظر كيف حالك مقارنة كيف كنت تعتقد أنك يجب أن تقوم به في مجال استخدام الذاكرة.
ومنذ سلاسل الخاص بك معروفة مقدما ولها طول ثابت، نظريا وعمليا الحل الأفضل هو مثالية التجزئة. هل يمكن استخدام cmph لتوليد ذلك.
ووفقا لويكيبيديا، فستبحث المفاتيح الخاصة بك تأخذ 2.5 بت / المفتاح، أو حول 50KB. هذا negligable مقارنة 664KB للقيم.
على الرغم من أن 166k إدخالات البيانات الصغيرة بدلا من المنظمة البحرية الدولية يمكن أن يكون لديك نظرة على جوجل-sparsehash
