python اوامر - هل لدى بايثون مجموعة مرتبة؟




الدوال في (12)

لدى Python قاموس مرتب . ماذا عن مجموعة مرتبة؟


Answers

إذا كنت تستخدم المجموعة المرتبة للاحتفاظ بترتيب تم الفرز ، ففكر في استخدام تنفيذ مجموعة تم فرزها من PyPI. توفر وحدة SortedSet لهذا الغرض فقط. بعض الفوائد: نقية بيثون ، تطبيقات سريعة C ، تغطية اختبار وحدة 100 ٪ ، ساعات من اختبار الإجهاد.

التثبيت من PyPI سهل مع النقطة:

pip install sortedcontainers

لاحظ أنه إذا لم تتمكن من pip install التطبيق ، فما عليك سوى سحب ملفات sortedlist.py و sortedset.py من المخزون المفتوح المصدر .

بمجرد تثبيت يمكنك ببساطة:

from sortedcontainers import SortedSet
help(SortedSet)

تحتفظ وحدة sortedcontainers أيضًا بمقارنة الأداء مع العديد من التطبيقات البديلة.

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


هناك أربعة أنواع من الطلبات قد يحتاج المرء ، وأعتقد:

  1. أمرت بواسطة المفتاح
  2. مرتبة حسب القيمة (لم اسمع من أي شخص يطلب هذا على الرغم من)
  3. أمرت عن طريق تعديل الوقت
  4. أمرت عن طريق إضافة الوقت

أعتقد أن التحصيلات. أمر تم الحصول عليه # 4. أو يمكنك إزالة مفتاح وإعادة إضافته ، بالنسبة إلى رقم 3.

بالنسبة إلى رقم 1 ، ينبغي لك على الأرجح التحقق من شجرة باللون الأحمر الأسود أو نصها:

تتميز الأشجار باللون الأحمر والأسود بتقلبات منخفضة في أوقات التشغيل (لذا قد يكون أفضل للتطبيقات التفاعلية) ، ولكنها ليست بالسرعة في المتوسط ​​(قد يكون من الأفضل معالجة الدُفعات - لا تحاول treaps إعادة تنظيم نفسها في كثير من الأحيان مما يجعلها سريعة في المتوسط ​​، ولكن عندما يعيدون تنظيمها قد يستغرق وقتًا طويلاً نسبيًا).

كل من هذه هي هياكل البيانات المنشأة مع التطبيقات في العديد من اللغات.


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


مجموعة مرتبة هي وظيفيا حالة خاصة من القاموس المرتب.

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

اعتبارا من بايثون 3.1 هناك collections.OrderedDict . فيما يلي مثال تنفيذ تطبيق OrderedSet. (لاحظ أن هناك طرق قليلة فقط تحتاج إلى تعريف أو تجاوز: collections.OrderedDict ومجموعات collections.MutableSet القيام بالرفع الثقيل.)

import collections

class OrderedSet(collections.OrderedDict, collections.MutableSet):

    def update(self, *args, **kwargs):
        if kwargs:
            raise TypeError("update() takes no keyword arguments")

        for s in args:
            for e in s:
                 self.add(e)

    def add(self, elem):
        self[elem] = None

    def discard(self, elem):
        self.pop(elem, None)

    def __le__(self, other):
        return all(e in other for e in self)

    def __lt__(self, other):
        return self <= other and self != other

    def __ge__(self, other):
        return all(e in self for e in other)

    def __gt__(self, other):
        return self >= other and self != other

    def __repr__(self):
        return 'OrderedSet([%s])' % (', '.join(map(repr, self.keys())))

    def __str__(self):
        return '{%s}' % (', '.join(map(repr, self.keys())))

    difference = property(lambda self: self.__sub__)
    difference_update = property(lambda self: self.__isub__)
    intersection = property(lambda self: self.__and__)
    intersection_update = property(lambda self: self.__iand__)
    issubset = property(lambda self: self.__le__)
    issuperset = property(lambda self: self.__ge__)
    symmetric_difference = property(lambda self: self.__xor__)
    symmetric_difference_update = property(lambda self: self.__ixor__)
    union = property(lambda self: self.__or__)

يمكنني أن أفعل لك أفضل واحد من OrderedSet: يحتوي boltons على نوع IndexedSet نقي بيثون 2/3-متوافق ليس فقط مجموعة مرتبة ، ولكنه يدعم أيضًا الفهرسة (كما هو الحال مع القوائم).

ببساطة pip install boltons (أو قم بنسخ setutils.py في تعليمات البرمجة لديك) ، IndexedSet باستيراد IndexedSet و:

>>> x = IndexedSet(list(range(4)) + list(range(8)))
>>> x
IndexedSet([0, 1, 2, 3, 4, 5, 6, 7])
>>> x - set(range(2))
IndexedSet([2, 3, 4, 5, 6, 7])
>>> x[-1]
7
>>> fcr = IndexedSet('freecreditreport.com')
>>> ''.join(fcr[:fcr.index('.')])
'frecditpo'

كل شيء فريد واحتفظ بالترتيب. الإفصاح الكامل: كتبت " IndexedSet ، ولكن هذا يعني أيضًا أنه يمكنك أن IndexedSet إذا كانت هناك أية مشكلات . :)


تأخرت قليلاً في اللعبة ، ولكني كتبت setlist صفوف كجزء من collections-extended التي تنفذ كلاً من Sequence

>>> from collections_extended import setlist
>>> sl = setlist('abracadabra')
>>> sl
setlist(('a', 'b', 'r', 'c', 'd'))
>>> sl[3]
'c'
>>> sl[-1]
'd'
>>> 'r' in sl  # testing for inclusion is fast
True
>>> sl.index('d')  # so is finding the index of an element
4
>>> sl.insert(1, 'd')  # inserting an element already in raises a ValueError
ValueError
>>> sl.index('d')
4

GitHub: https://github.com/mlenzen/collections-extended

الوثائق: http://collections-extended.lenzm.net/en/latest/

PyPI: https://pypi.python.org/pypi/collections-extended


>>> a = {3, 4, 2, 6, 1, 7}
>>> type(a)
<class 'set'>
>>> sorted(a, reverse=True)
[7, 6, 4, 3, 2, 1]
>>> sorted(a)
[1, 2, 3, 4, 6, 7]

هناك وصفة مرتبة ( الوصلة الجديدة المحتملة) لهذا الأمر والتي يشار إليها من وثائق Python 2 . هذا يعمل على Py2.6 أو أحدث و 3.0 أو أحدث دون أي تعديلات. تتشابه الواجهة تمامًا تمامًا مع المجموعة العادية ، إلا أنه يجب إجراء هذه العملية باستخدام قائمة.

OrderedSet([1, 2, 3])

هذا هو MutableSet ، لذلك لا يتطابق التوقيع الخاص بـ .union مع المجموعة ، ولكن بما أنه يتضمن __or__ يمكن إضافة شيء مشابه بسهولة:

@staticmethod
def union(*sets):
    union = OrderedSet()
    union.union(*sets)
    return union

def union(self, *sets):
    for set in sets:
        self |= set

توفر الحزمة ParallelRegression فئة setList () مرتبة مرتبة أكثر اكتمالاً من الخيارات المستندة إلى وصفة ActiveState. وهو يدعم جميع الطرق المتاحة للقوائم ومعظم إن لم يكن كل الطرق المتاحة للمجموعات.


يمكنك استخدام reduce() للحصول على قائمة بالقيم الفريدة في سطر واحد:

>>> mylist = [4, 1, 2, 1, 3, 2, 4, 1, 3, 2, 3, 1, 3, 2, 4]
>>> reduce(lambda a, b: b[0] in a and a or a + b, [[i] for i in mylist])
[4, 1, 2, 3]

لكثير من الأغراض ، يكفي أن يتم فرز المكالمات. فمثلا

>>> s = set([0, 1, 2, 99, 4, 40, 3, 20, 24, 100, 60])
>>> sorted(s)
[0, 1, 2, 3, 4, 20, 24, 40, 60, 99, 100]

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


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

اتبع الأمثلة:

{'two': True, 'one': {'extra': False}}

يتوقع المرء نتيجة لشيء من هذا القبيل:

x = {'a':1, 'b': 2}
y = {'b':10, 'c': 11}
z = dict(x.items()+y.items())
print(z)

بدلاً من ذلك ، نحصل على هذا:

x = {'a':1, 'b': 2}
y = {'b':10, 'c': 11}
z = dict(x.items()|y.items())
print(z)

يجب أن يكون الإدخال "one" قد يكون "depth_2" و "extra" كعناصر داخل قاموسه إذا كان بالفعل دمجًا.

باستخدام سلسلة أيضا ، لا يعمل:

def merge(*dicts, **kv): 
      return { k:v for d in list(dicts) + [kv] for k,v in d.items() }

النتائج في:

assert (merge({1:11,'a':'aaa'},{1:99, 'b':'bbb'},foo='bar')==\
    {1: 99, 'foo': 'bar', 'b': 'bbb', 'a': 'aaa'})

assert (merge(foo='bar')=={'foo': 'bar'})

assert (merge({1:11},{1:99},foo='bar',baz='quux')==\
    {1: 99, 'foo': 'bar', 'baz':'quux'})

assert (merge({1:11},{1:99})=={1: 99})

الدمج العميق الذي قدمه rcwesick يخلق نفس النتيجة.

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





python set