هل تريد تسمية بنية القاموس التي تخزن المفاتيح بترتيب يمكن التنبؤ به؟

Question

ملحوظة: على الرغم من أن السياق الخاص بي هو Objective-C، فإن سؤالي يتجاوز في الواقع اختيار لغة البرمجة.كما أنني وصفته بأنه "ذاتي" نظرًا لأن الشخص لا بد أن يشكو بخلاف ذلك، لكنني شخصيًا أعتقد أنه موضوعي تمامًا تقريبًا.أيضا، أنا على علم هذا السؤال ذو الصلة بـ SO, ، ولكن نظرًا لأن هذه مشكلة أكبر، فقد اعتقدت أنه من الأفضل أن أجعل هذا سؤالًا منفصلاً.من فضلك لا تنتقد السؤال دون قراءته وفهمه بشكل كامل.شكرًا!

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

1. يتم الوصول إلى القيم عن طريق المفتاح (بدلاً من الفهرس، مثل المصفوفة).
2. يرتبط كل مفتاح بقيمة.
3. يجب أن يكون كل مفتاح فريدًا.

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

بالنسبة لسؤالي فإن الملاحظة الأهم هي ذلك لم يتم تحديد الترتيب الذي يتم تعداد المفاتيح به - قد يوفر القاموس المفاتيح بالترتيب الذي يراه أكثر ملاءمة، والأمر متروك للعميل لتنظيمها حسب الرغبة.

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

LinkedHashMap تم تسميته وفقًا للتنفيذ في تقليد مجموعات Java - "مرتبط" لأنه يستخدم قائمة مرتبطة بشكل مزدوج لتتبع ترتيب الإدراج، و"hash" لأنه يصنف فئات فرعية HashMap.إلى جانب حقيقة أن المستخدم لا داعي للقلق بشأن ذلك، فإن اسم الفئة لا يشير حقًا إلى ما يفعله.استخدام أمر يبدو وكأنه إجماع بين التعليمات البرمجية الموجودة، ولكن عمليات البحث على الويب حول هذا الموضوع كشفت أيضًا عن ارتباك مفهوم بين "مرتبة" و"مرتبة"، وأنا أشعر بنفس الشيء.يحتوي تطبيق .NET أيضًا على تعليق حول التسمية الخاطئة الواضحة، ويقترح أنه يجب أن يكون "IndexedDictionary" بدلاً من ذلك، نظرًا لحقيقة أنه يمكنك استرداد الكائنات وإدراجها عند نقطة معينة في الترتيب.

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

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

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

Answer 1

أصوت لـ OrderedDictionary للأسباب التالية:

لا يتم استخدام "مفهرس" أبدًا في فئات الكاكاو، إلا في حالة واحدة.يظهر دائمًا كاسم (NSIndexSet، NSIndexPath، objectAtIndex:، إلخ).هناك حالة واحدة فقط عندما يظهر "الفهرس" كفعل، وهو موجود في الخاصية "المفهرسة" الخاصة بـ NSPropertyDescription:تم فهرسته وضبطه.يشبه NSPropertyDescription تقريبًا عمود جدول في قاعدة البيانات، حيث تشير كلمة "الفهرسة" إلى التحسين لتسريع أوقات البحث.لذلك سيكون من المنطقي أنه مع كون NSPropertyDescription جزءًا من إطار عمل البيانات الأساسية، فإن "isIndexed" و"setIndexed" سيكونان مكافئين لفهرس في قاعدة بيانات SQL.لذلك، فإن تسميتها "IndexedDictionary" قد تبدو زائدة عن الحاجة، حيث يتم إنشاء الفهارس في قواعد البيانات لتسريع وقت البحث، ولكن القاموس بالفعل لديه O(1) وقت البحث.ومع ذلك، فإن تسميتها "IndexDictionary" ستكون أيضًا تسمية خاطئة، نظرًا لأن "الفهرس" في الكاكاو يشير إلى الموضع، وليس الترتيب.وهما مختلفان لغويا.

أتفهم قلقك بشأن "OrderedDictionary"، ولكن تم بالفعل وضع السابقة في Cocoa.عندما يريد المستخدمون الحفاظ على تسلسل معين، يستخدمون "مرتب":-[NSApplicationorderDocuments]، -[NSWindoworderIndex]، -[NSApplicationorderWindows]، وما إلى ذلك.لذا، فإن جون بيري لديه الفكرة الصحيحة في الغالب.

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

لذلك، أوصي بجعل OrderedDictonary عبارة عن مجموعة فئات، مع فئات فرعية خاصة من InsertionOrderDictionary وNaturalOrderDictionary وCustomOrderDictionary.بعد ذلك، يقوم المستخدم ببساطة بإنشاء OrderedDictionary كما يلي:

OrderedDictionary * dict = [[OrderedDictionary alloc] initWithOrder:kInsertionOrder];
//or kNaturalOrder, etc

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

Answer 2

أنا التصويت ل InsertionOrderDictionary.لقد فعلتها.

Answer 3

تصويت قوي لـ OrderedDictionary.

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

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

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

Answer 4

منذ أن نشرت هذا السؤال، بدأت أميل نحو شيء مثل قاموس مفهرس أو قاموس قابل للفهرسة.على الرغم من أنه من المفيد أن تكون قادرًا على الحفاظ على ترتيب عشوائي للمفاتيح، إلا أن قصر ذلك على ترتيب الإدراج فقط يبدو وكأنه تقييد لا داعي له.بالإضافة إلى ذلك، يدعم صفي بالفعل indexOfKey: و keyAtIndex:, ، والتي تشبه (عمدًا) NSArray indexOfObject: و objectAtIndex:.أنا أفكر بشدة في الإضافة insertObject:forKey:atIndex: الذي يتطابق مع NSMutableArray insertObject:atIndex:.

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

السؤال الكبير:هل "مفهرسة" أو "قابلة للفهرسة" غامضة أو من المحتمل أن تكون مربكة مثل "مرتبة"؟هل يفكر الناس في فهارس قاعدة البيانات، أو فهارس الكتب، وما إلى ذلك؟هل سيكون ضارًا إذا افترضوا أنه تم تنفيذه باستخدام مصفوفة، أم أن ذلك قد يبسط فهم المستخدم للوظيفة؟

---

يحرر: يبدو هذا الاسم أكثر منطقية نظرًا لحقيقة أنني أفكر في إضافة طرق تعمل مع NSIndexSet فى المستقبل.(NSArray لديه -objectsAtIndexes: بالإضافة إلى طرق إضافة/إزالة مراقبين للكائنات في فهارس معينة.)

Answer 5

ماذا عن KeyedArray؟

Answer 6

كما قلت في فقرتك الأخيرة، أعتقد أن InsertionOrder(ed)Dict(ionary) لا لبس فيه إلى حد ما؛لا أرى كيف يمكن تفسير ذلك بأي طريقة بخلاف إعادة المفاتيح بالترتيب الذي تم إدراجها به.

Answer 7

من خلال فصل الترتيب المفهرس عن ترتيب الإدراج، ألا يتلخص هذا ببساطة في الاحتفاظ بمصفوفة وقاموس في كائن واحد؟أعتقد أن تصويتي لهذا النوع من الكائنات هو IndexedKeyDictionary

شركة#:

public class IndexedKeyDictionary<TKey, TValue> { 

  List<TKey> _keys;
  Dictionary<TKey, TValue> _dictionary;
  ...

  public GetValueAtIndex(int index) {
    return _dictionary[_keys[index]];
  }

  public Insert(TKey key, TValue val, int index) {
    _dictionary.Add(key, val);

    // do some array massaging (splice, etc.) to fit the new key
    _keys[index] = key;
  }

  public SwapKeyIndexes(TKey k1, TKey k2) {
    // swap the indexes of k1 and k2, assuming they exist in _keys
  }
}

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

Answer 8

للوهلة الأولى، أنا مع الرد الأول - InsertionOrderDictionary، على الرغم من أنه غامض بعض الشيء فيما يتعلق بما يعنيه "InsertionOrder" للوهلة الأولى.

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

على الرغم من أن "CHMap" قد لا يكون خيارًا سيئًا بعد الاطلاع على رابط التوثيق الخاص بك.

ربما "CHMappedDictionary"؟=)

حظا سعيدا.

يحرر:شكرا على التوضيح، كل يوم تتعلم شيئا جديدا.=)

Answer 9

هو الفرق الوحيد الذي allKeys إرجاع المفاتيح بترتيب معين؟إذا كان الأمر كذلك، أود ببساطة أن أضيف allKeysSorted و allKeysOrderdByInsertion أساليب للمعيار NSDictionary واجهة برمجة التطبيقات.

ما هو الهدف من قاموس ترتيب الإدراج هذا؟ما هي الفوائد التي يقدمها للمبرمج مقابل؟مجموعة؟