Python/bisect

تقدّم هذه الوحدة وسيلة للتعامل مع القوائم وفرزها بصورة تلقائية، وبذلك يمكن تجنب إعادة فرز القائمة بعد كل عملية إدراج للعناصر فيها. وتظهر فائدة هذه الوحدة بجلاء عند التعامل مع القوائم الطويلة والتي تؤدي عمليات مقارنة مكثّفة. تحمل هذه الوحدة اسم bisect لأنّها تستخدم خوارزمية التنصيف البسيطة bisection algorithm لإنجاز عملها.

دوال الوحدة bisect

تقدّم الوحدة bisect الدوال التالية:

الدالة bisect_left()‎

تحدّد الدالة موقع إدراج العنصر المحدد في المصفوفة المعطاة.

الدالتان bisect_right()‎ و bisect()‎

تعيدان موقع الإدراج الذي يأتي بعد (إلى الجانب الأيمن) العناصر المماثلة للعنصر المضاف في المصفوفة المعطاة.

الدالة insort_left()‎

تدرج الدالة العنصر المحدد في المصفوفة المعطاة بترتيب مفروز.

الدالتان insort_right()‎ و insort()‎

تدرجان العنصر المحدّد في المصفوفة المعطاة بعد العناصر المماثلة للعنصر المعطى والموجودة أصلًا في المصفوفة.

البحث في القوائم المفروزة

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

تبيّن الشيفرة التالية طريقة تحويل خمس دوال لإيجاد موقع الإدراج إلى دوال للبحث في القوائم المفروزة:

# تحديد موقع العنصر في أقصى اليسار والمساوي بالضبط للعنصر x
def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

# العثور على القيمة في أقصى اليمين والتي تكون أصغر من x
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

# العثور على القيمة في أقصى اليمين والتي تكون أصغر من أو تساوي x
def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

# العثور على القيمة في أقصى اليسار والتي تكون أكبر من x
def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

# العثور على العنصر في أقصى اليسار والذي يكون أكبر من أو يساوي x
def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

أمثلة

يمكن الاستفادة من دالة bisect()‎ لإجراء عمليات البحث في الجداول الرقمية numeric table. يستخدم المثال التالي الدالة bisect()‎ للعثور على الدرجة الحرفية المقابلة لدرجة امتحان على سبيل المثال وذلك باستخدام مجموعة من النقاط الثابتة والمرتبة: 90 فما فوق تمثّل درجة 'A'، و 80 إلى 89 تمثّل درجة 'B'، وهكذا.

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
...     i = bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

بخلاف الدالة sorted()‎ فإنّه ليس من المنطقي أن تمتلك دوال bisect()‎ معاملات مثل key أو reversed لأنّ ذلك سيجعل الدالة تعمل بصورة غير فعّالة (فالاستدعاءات المتعاقبة لدوال bisect لن تتذكر جميع المفاتيح السابقة).

لهذا يفضّل -عوضًا عما سبق- البحث في قائمة من مفاتيح معدّة مسبقًا للعثور على موقع العنصر المطلوب:

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # قائمة من المفاتيح المعدّة مسبقًا
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)

مصادر

• صفحة Array bisection algorithm في توثيق بايثون الرسمي.