bisect --- الگوریتم دو نیمهسازی آرایه¶
کد منبع: Lib/bisect.py
این ماژول پشتیبانی از نگهداری یک فهرست به ترتیب مرتبشده بدون نیاز به مرتبسازی فهرست پس از هر درج را فراهم میکند. برای فهرستهای طولانی از آیتمهایی با عملیات مقایسه پرهزینه، این میتواند بهبودی نسبت به جستوجوهای خطی یا مرتبسازی مجدد مکرر باشد.
این ماژول bisect نامیده میشود، زیرا برای انجام کار خود از یک الگوریتم سادهی دو نیمسازی (bisection) استفاده میکند. برخلاف سایر ابزارهای دو نیمسازی که به دنبال یک مقدار مشخص میگردند، توابع این ماژول برای یافتن یک نقطهی درج طراحی شدهاند. بر همین اساس، این توابع هرگز متد __eq__() را برای تعیین اینکه آیا مقداری پیدا شده است فراخوانی نمیکنند. در عوض، توابع فقط متد __lt__() را فراخوانی میکنند و یک نقطهی درج بین مقادیر یک آرایه برمیگردانند.
توجه
توابع این ماژول نخایمن نیستند. اگر چندین نخ بهطور همزمان از توابع bisect روی یک دنباله استفاده کنند، ممکن است منجر به رفتار تعریفنشده شود. به همین ترتیب، اگر در حین کار یک تابع bisect روی دنباله ارائهشده، آن دنباله توسط نخ دیگری تغییر کند، نتیجه تعریفنشده است. برای مثال، استفاده از insort_left() روی یک فهرست مشترک از چندین نخ ممکن است باعث شود فهرست نامرتب شود.
توابع زیر ارائه شدهاند:
- bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)¶
نقطه درج برای x در a را برای حفظ ترتیب مرتبشده پیدا کنید. میتوانید از پارامترهای lo و hi برای مشخص کردن زیرمجموعهای از فهرست که باید در نظر گرفته شود استفاده کنید؛ بهطور پیشفرض، از کل فهرست استفاده میشود. اگر x از قبل در a موجود باشد، نقطه درج پیش از (در سمت چپ) هر ورودی موجود خواهد بود. مقدار برگشتی برای استفاده بهعنوان اولین پارامتر
list.insert()مناسب است، با فرض اینکه a از قبل مرتبشده باشد.نقطه درج بازگشتی ip آرایه a را به دو اسلایس تقسیم میکند، بهگونهای که
all(elem < x for elem in a[lo : ip])برای اسلایس چپ درست است وall(elem >= x for elem in a[ip : hi])برای اسلایس راست درست است.key یک تابع کلید با یک آرگومان را تعیین میکند که برای استخراج یک کلید مقایسه از هر عنصر آرایه استفاده میشود. برای پشتیبانی از جستجوی رکوردهای پیچیده، تابع کلید بر مقدار x اعمال نمیشود.
اگر key برابر
Noneباشد، عناصر بهطور مستقیم مقایسه میشوند و هیچ تابع کلیدی فراخوانی نمیشود.تغییر یافته در نسخهی 3.10: پارامتر key اضافه شد.
- bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)¶
- bisect.bisect(a, x, lo=0, hi=len(a), *, key=None)¶
مشابه
bisect_left()، اما نقطه درجی را برمیگرداند که پس از (در سمت راست) هر آیتم موجود از x در a قرار دارد.نقطهی درج برگرداندهشده ip آرایه a را به دو اسلایس تقسیم میکند، بهطوری که
all(elem <= x for elem in a[lo : ip])برای اسلایس چپ درست است وall(elem > x for elem in a[ip : hi])برای اسلایس راست درست است.تغییر یافته در نسخهی 3.10: پارامتر key اضافه شد.
- bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)¶
x را در a با ترتیب مرتبشده درج کنید.
این تابع ابتدا
bisect_left()را برای یافتن محل درج اجرا میکند. سپس، متدinsert()را روی a اجرا میکند تا x را در جایگاه مناسب برای حفظ ترتیب مرتبسازی درج کند.برای پشتیبانی از درج رکوردها در یک جدول، تابع key (در صورت وجود) برای مرحله جستوجو به x اعمال میشود، اما برای مرحله درج اعمال نمیشود.
در نظر داشته باشید که جستجوی O(log n) تحتالشعاع گام کند درج O(n) قرار میگیرد.
تغییر یافته در نسخهی 3.10: پارامتر key اضافه شد.
- bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)¶
- bisect.insort(a, x, lo=0, hi=len(a), *, key=None)¶
مشابه
insort_left()، اما x را پس از هر آیتم موجود از x در a درج میکند.این تابع ابتدا
bisect_right()را برای یافتن نقطه درج اجرا میکند. سپس، متدinsert()را روی a اجرا میکند تا x را در جایگاه مناسب برای حفظ ترتیب مرتبسازی درج کند.برای پشتیبانی از درج رکوردها در یک جدول، تابع key (در صورت وجود) برای مرحله جستوجو به x اعمال میشود، اما برای مرحله درج اعمال نمیشود.
در نظر داشته باشید که جستجوی O(log n) تحتالشعاع گام کند درج O(n) قرار میگیرد.
تغییر یافته در نسخهی 3.10: پارامتر key اضافه شد.
یادداشتهای عملکرد¶
هنگام نوشتن کد حساس به زمان با استفاده از bisect() و insort()، این نکات را در نظر داشته باشید:
جستجوی دودویی برای جستجوی بازههایی از مقادیر مؤثر است. برای یافتن مقادیر مشخص، دیکشنریها کارآمدتر هستند.
توابع insort() از مرتبهی O(n) هستند، زیرا مرحلهی جستجوی لگاریتمی تحت سلطهی مرحلهی درج با زمان خطی است.
توابع جستجو فاقد وضعیت هستند و نتایج تابع کلید را پس از استفاده دور میاندازند. در نتیجه، اگر از توابع جستجو در یک حلقه استفاده شود، ممکن است تابع کلید بارها و بارها برای همان عناصر آرایه فراخوانی شود. اگر تابع کلید سریع نیست، استفاده از
@functools.cacheبهعنوان پوشش برای آن را در نظر بگیرید تا از محاسبات تکراری اجتناب شود. بهعنوان جایگزین، در نظر بگیرید که در یک آرایه از کلیدهای از پیش محاسبهشده جستجو کنید تا نقطه درج را بیابید (همانطور که در بخش مثالهای زیر نشان داده شده است).
همچنین ملاحظه نمائید
Sorted Collections یک ماژول با کارایی بالا است که از bisect برای مدیریت مجموعههای مرتبشده از داده استفاده میکند.
SortedCollection recipe از bisect برای ساختن یک کلاس مجموعه با امکانات کامل، همراه با متدهای جستجوی ساده و مستقیم و پشتیبانی از تابع کلید استفاده میکند. کلیدها از پیش محاسبه میشوند تا از فراخوانیهای غیرضروری تابع کلید در حین جستجوها جلوگیری شود.
جستجو در فهرستهای مرتبشده¶
توابع bisect functions فوق برای یافتن نقاط درج مفید هستند، اما ممکن است استفاده از آنها برای کارهای جستجوی رایج دشوار یا نامناسب باشد. پنج تابع زیر نشان میدهند که چگونه میتوان آنها را به جستجوهای استاندارد برای فهرستهای مرتب تبدیل کرد:
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
def find_lt(a, x):
'Find rightmost value less than x'
i = bisect_left(a, x)
if i:
return a[i-1]
raise ValueError
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
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
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() میتواند برای جستجو در جدولهای عددی مفید باشد. این مثال از bisect() برای جستجوی نمرهی الفبایی یک نمرهی امتحان (مثلاً) بر اساس مجموعهای از نقاط شکست عددی مرتبشده استفاده میکند: ۹۰ به بالا 'A' است، ۸۰ تا ۸۹ 'B' است، و به همین ترتیب:
>>> def grade(score):
... i = bisect([60, 70, 80, 90], score)
... return "FDCBA"[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']
توابع bisect() و insort() همچنین با فهرستهایی از تاپلها کار میکنند. آرگومان key میتواند برای استخراج فیلدی که برای مرتبسازی رکوردها در یک جدول استفاده میشود، بهکار رود:
>>> from collections import namedtuple
>>> from operator import attrgetter
>>> from bisect import bisect, insort
>>> from pprint import pprint
>>> Movie = namedtuple('Movie', ('name', 'released', 'director'))
>>> movies = [
... Movie('Jaws', 1975, 'Spielberg'),
... Movie('Titanic', 1997, 'Cameron'),
... Movie('The Birds', 1963, 'Hitchcock'),
... Movie('Aliens', 1986, 'Cameron')
... ]
>>> # Find the first movie released after 1960
>>> by_year = attrgetter('released')
>>> movies.sort(key=by_year)
>>> movies[bisect(movies, 1960, key=by_year)]
Movie(name='The Birds', released=1963, director='Hitchcock')
>>> # Insert a movie while maintaining sort order
>>> romance = Movie('Love Story', 1970, 'Hiller')
>>> insort(movies, romance, key=by_year)
>>> pprint(movies)
[Movie(name='The Birds', released=1963, director='Hitchcock'),
Movie(name='Love Story', released=1970, director='Hiller'),
Movie(name='Jaws', released=1975, director='Spielberg'),
Movie(name='Aliens', released=1986, director='Cameron'),
Movie(name='Titanic', released=1997, director='Cameron')]
اگر تابع کلید پرهزینه باشد، میتوان با جستجو در فهرستی از کلیدهای از پیش محاسبهشده برای یافتن اندیس یک رکورد، از فراخوانیهای مکرر تابع اجتناب کرد:
>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1]) # Or use operator.itemgetter(1).
>>> keys = [r[1] for r in data] # Precompute a list of keys.
>>> 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)