ما الذي يمكن استخدامه في "TreeDict" (أو Treemap) عمليًا؟

Question

أقوم بتطوير فئة "TreeDict" في لغة بايثون.هذا في الأساس عبارة عن أمر يسمح لك باسترداد أزواج القيمة الرئيسية الخاصة به بترتيب مفروز، تمامًا مثل فئة مجموعة Treemap في Java.

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

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

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

Answer 1

وانها مفيدة عندما كنت في حاجة للذهاب من خلال قاموس في ترتيب المفاتيح. والتي تأتي في بعض الأحيان. لقد وجدت في الواقع لها بلا حدود أكثر شيوعا في بعض مسابقات البرمجة ثم أي شيء آخر (اعتقد ACM، الخ).

والميزة مفيدة للغاية لTreeMap هي عندما تريد العثور بسرعة على دقيقة أو ماكس مفتاح. باستخدام القاموس فرز هذا غالبا ما يكون استدعاء أسلوب واحد. وحسابيا يمكن القيام به في O (سجل (ن)) مرة، بالمقارنة مع بالتكرار عبر كل مفتاح تبحث عن دقيقة / ماكس إذا جمع هو لم يتم فرزها. في الأساس، واجهة ودية من ذلك بكثير.

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

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

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

Answer 2

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

وعلى سبيل المثال (وهذا جاء في الآونة الأخيرة الإجابة SO)، ويقول كنت تريد توليد القيم شبه عشوائي مع الترددات النسبية معين - أي بمعنى، كنت أنت معين، ويقول، d ديكت:

{'wolf': 42, 'sheep': 15, 'dog': 23, 'goat': 15, 'cat': 5}

ووبحاجة إلى وسيلة لتوليد "الذئب" مع احتمال 42 من أصل 100 (منذ 100 هو مجموع الترددات النسبية معين)، "الخراف" 15 من أصل 100، وهلم جرا؛ وعدد من قيم مميزة يمكن أن تكون كبيرة جدا، كما يمكن الترددات النسبية.

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

def preprocess(d):
    tot = 0
    for v in d:
        tot += d[v]
        treemap.insert(key=tot, value=v)
    return tot, treemap

والآن، وتوليد القيمة التي يمكن أن تكون سريعة جدا (O(log(len(d))))، كما يلي:

def generate(tot, treemap, r=random):
    n = r.randrange(tot)
    return treemap.firstGTkey(n).value

وحيث firstGTKey هو أسلوب يقوم بإرجاع الإدخال الأول (مع .key و.value الصفات، في هذا المثال الافتراضي) مع مفتاح> حجة معينة. لقد استعملت هذا النهج مع الملفات الكبيرة المخزنة على B-الأشجار، على سبيل المثال (باستخدام مثل bsddb.bt_open وطريقة set_location).

Answer 3

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

Answer 4

وأنا غالبا ما تستخدم Dict<DateTime, someClassOrValue> عند العمل مع العمليات الصناعية data-- صمام فتح / إغلاق، والآلات بدء / إيقاف، وما إلى ذلك.

وبعد فرز مفاتيح مفيد خصوصا عندما كنت في حاجة للمقارنة بين فترات زمنية بين بدء / إيقاف أو أحداث فتح / وثيقة في مبلغ محترم من الوقت.

ولكن، منذ أن كنت قادرا على استخدام LINQ في C # لقد وجدت أنه في كثير من الأحيان أسهل للعمل فقط مع IEnumerables واستخدام طرق الإرشاد IQueryable للحصول على المعلومات أحتاج.

Answer 5

وتقريبا جميع "GROUP BY" التقارير تتطلب القاموس فرزها.

summary = sortedDefaultDict()
for row in somePileOfData:
    summary[row.group_by] += row.balance
for k in sorted(summary.keys()):
    print k, summary[k]

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

إذا استدعاء دالة sorted يفعل أي عمل، فإنه يحفظ طن من الوقت على المدى الطويل.

Answer 6

هل رأيت أن: http://code.activestate.com/recipes/576998/ ?

zuo

Answer 7

ويمكن أن تجعل خوارزميات مختلفة أسهل للتنفيذ.